Maths Olympiad Prep

Library / /30 of 33

Combinatorics Difficulty 8.7 Shortlist Prove it Turkey

Point (a,b)(a, b) on the plane is a primitive point if a,ba, b are integers with gcd(a,b)=1\gcd(a, b) = 1. A graph whose vertices are primitive points is constructed as follows: an edge is drawn between points (a1,b1)(a_1, b_1) and (a2,b2)(a_2, b_2) if and only if 2a1=2a2{b1b2,b2b1}2a_1 = 2a_2 \in \{b_1 - b_2, b_2 - b_1\} or 2b1=2b2{a1a2,a2a1}2b_1 = 2b_2 \in \{a_1 - a_2, a_2 - a_1\}. Later, some edges of this graph will be removed until a forest is obtained. At least how many edges must be removed from the graph? At least how many trees will be found in the forest?

Solution

First, note that point (a,b)(a, b) is connected to points (a,b±2a)(a, b \pm 2a) and (a±2b,b)(a \pm 2b, b), so a generic vertex – except finitely many exceptions – of the graph has valency 44. Now, we observe that for a generic primitive point – except finitely many exceptions – (a,b)(a, b), exactly 11 of the 44 points connected to (a,b)(a, b) is closer to the origin than (a,b)(a, b). Indeed, assume without loss of generality that 0<a<b0 < |a| < |b|, which one can do unless (a,b){(±1,±1),(0,±1),(±1,0)}(a, b) \in \{(\pm 1, \pm 1), (0, \pm 1), (\pm 1, 0)\}. Then, one of b±2a|b \pm 2a| is greater than b|b| and one is less than b|b| while both of a±2b|a \pm 2b| are greater than a|a|. This means that exactly 11 of the 44 points (a,b±2a)(a, b \pm 2a) and (a±2b,b)(a \pm 2b, b) is closer to the origin than (a,b)(a, b) while the remaining 33 points are further.

Let the full sub-graph determined by the 88-vertex set {(±1,±1),(0,±1),(±1,0)}\{(\pm 1, \pm 1), (0, \pm 1), (\pm 1, 0)\} be called the root. The observation in the previous paragraph implies that any vertex of the graph outside the root is connected to the root by a unique path. Therefore, the graph will be a forest – after removal of some edges – if and only if the root becomes a forest, thus one never has to remove edges outside the root in order to make the graph a forest. In case no edge outside the root is removed, the number of trees in the graph will be the same as the number of trees in the root. The root consists of one 44-cycle joining (±1,±1)(\pm 1, \pm 1) and four isolated points (0,±1),(±1,0)(0, \pm 1), (\pm 1, 0). Therefore, 11 edge has to be removed in order to obtain a forest and this forest will have 55 trees.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.