Browse · MathNet
PrintTeam Selection Test
Turkey counting and probability
Problem
Point on the plane is a primitive point if are integers with . A graph whose vertices are primitive points is constructed as follows: an edge is drawn between points and if and only if or . 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 is connected to points and , so a generic vertex – except finitely many exceptions – of the graph has valency . Now, we observe that for a generic primitive point – except finitely many exceptions – , exactly of the points connected to is closer to the origin than . Indeed, assume without loss of generality that , which one can do unless . Then, one of is greater than and one is less than while both of are greater than . This means that exactly of the points and is closer to the origin than while the remaining points are further.
Let the full sub-graph determined by the -vertex set 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 -cycle joining and four isolated points . Therefore, edge has to be removed in order to obtain a forest and this forest will have trees.
Let the full sub-graph determined by the -vertex set 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 -cycle joining and four isolated points . Therefore, edge has to be removed in order to obtain a forest and this forest will have trees.
Final answer
Remove 1 edge; the resulting forest has 5 trees.
Techniques
OtherIntegers