0708-1300/Just for Fun10

From Drorbn
Revision as of 13:45, 8 March 2008 by Oantolin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

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 . 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.

If this solution is correct and you already read it it doesn't means that the fun is over because this problem is certainly here because it can be solved with the aid of homology theory. So, we still need to find that proof.

Note: this proof is incorrect. It does show one of the numbers assigned to the edges is at least n, so to complete the proof we need to show that those numbers are the distances along the tree or at least bounded above by them. Unfortunately that is not true, those numbers are generally larger than the distance along the tree (see the red edge in the following figure).

Maze.png