# 0708-1300/Just for Fun10

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
First label the edges of the tree with ones. Then, for any edge not belonging to the tree, not already labeled and such that a contiguous square has the rest of the edges labeled, label it with the sum of those edges. Observe that in this process the labeling of all the edges will be well defined and every edge will be labeled since we started from a tree that was maximal. The non selected edges form like passages on a labyrinth through which you can move along. Observe that there are at least one edge in the boundary of the square that is not part of the tree. Consider the numbers on those edges (the ones in the boundary of the square and not on the tree). Let's assume that all of these edges has label strictly less than $n$. Observe that when you move one step along the labyrinth then the number in the edge you are on can be reduced by at least two units. Then none of the passages starting outside te square reach the center of it. Remove from the figure all those passages and the edges that are common to two passages. Then you get a non-empty (contains some squares) part of the square that is completely surrounded by the tree. But this is a contradiction because this would be a cycle in the tree.