For integers $a, b$, call the lattice point with coordinates $(a,b)$ basic if $gcd(a,b)=1$. A graph takes the basic points as vertices and the edges are drawn in such way: There is an edge between $(a_1,b_1)$ and $(a_2,b_2)$ if and only if $2a_1=2a_2\in \{b_1-b_2, b_2-b_1\}$ or $2b_1=2b_2\in\{a_1-a_2, a_2-a_1\}$. Some of the edges will be erased, such that the remaining graph is a forest. At least how many edges must be erased to obtain this forest? At least how many trees exist in such a forest?
Problem
Source: Turkey Team Selection Test 2018 P7
Tags: combinatorics, graph theory, number theory, GCD, Trees
28.03.2018 13:01
Proof by Halil Ozkan during the exam: First, we should prove that any point $(x, y)$ is connected to exactly one of the points $(1, 1), (1, 0), (0, 1), (-1, 0)$ or $(0, -1)$. Secondly, we should prove that the only cycle is $(1, 1), (1, -1), (-1, -1), (-1, 1)$. And we can assume that there exist another cycle other than this. We use $the$ $distance$ between the $(0, 0)$ and a point $(x, y)$ as $\sqrt{x^{2}+y^{2}}$ and we prove that $the$ $distance$ decreases in at most one edge when we travel through the edges. We find a contradiction and this ends the proof.
21.04.2018 10:41
@above, can you show how to prove there aren’t any other cycles? Oops, I came up with the idea: let line $y=x, y=-x$ dissect the plane into four part called left, right, up, down area. Consider the point on a cycle as a starting point, if the sum of the absolute value of its two coordinates achieve minimum(if it is $(1,1)$, we consider the vertice next to it). We can easily induct that walking along with the cycle, we alway “go up(down,etc) to the up(down,etc) area. Thus consider the path back to the starting point we find: if the cycle contains $(1,1)$, since we can never reach the boundary of the area, we can’t go back. If it doesn’t, we can find the cycle contains infinite vertices(using the previous fact), a contradiction.
19.05.2018 14:19
liekkas wrote: @above, can you show how to prove there aren’t any other cycles? Consider a cycle and look at coordinates of points on it. Take the furthest point to the (0, 0). We know there exists at least one point with that condition. Call this point $A$. We can travel to four points from point $A$. Two of them are on cycle and their distance are smaller than point $A$. But we know that the distance decreases at most one of them, contradiction.