Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1991 IMO Problems/Problem 4"

(New page: Suppose <math>\,G\,</math> is a connected graph with <math>\,k\,</math> edges. Prove that it is possible to label the edges <math>1,2,\ldots ,k\,</math> in such a way that at each vertex w...)
 
 
Line 12: Line 12:
  
 
Now, all the vertices in <math>V</math> are those whose edges do not matter, while all vertices not in <math>V</math> are those with edges relatively prime.  Thus we have the desired configuration, and we simply distribute the remaining numbers in any way we wish.
 
Now, all the vertices in <math>V</math> are those whose edges do not matter, while all vertices not in <math>V</math> are those with edges relatively prime.  Thus we have the desired configuration, and we simply distribute the remaining numbers in any way we wish.
 +
 +
== See Also == {{IMO box|year=1991|num-b=3|num-a=5}}

Latest revision as of 16:45, 30 January 2021

Suppose $\,G\,$ is a connected graph with $\,k\,$ edges. Prove that it is possible to label the edges $1,2,\ldots ,k\,$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1.


Solution

We provide an algorithmic approach for labelling the edges: We start off with the set $V$ of all vertices in $G$. For each step in the process we remove a number of vertices from the set $V$ if their exists an edge sorrounding it which is labelled. Additionally, we shall use up the numbers $1,2,...,k$ in the order from least to greatest.

Here is the process: Let $u$ be the least number not used yet. Take the longest path that uses any vertex once formed solely by vertices from $V$ and call it path $P=(v_1,v_2,...,v_n)$. If $v_1$ has more than one edge, then since $P$ is maximal, it must be connected to some other edge $v_0$ which could be one of the vertices $v_i$ or one of the vertices not in $V$. Similarly, if $v_n$ has more than one edge, it must be connected to a vertex $v_{n+1}$ which is either one of the $v_i$ or one of the vertices not in $V$. Notice that since $v_1,v_n\in V$ the edge connecting $v_0$ and $v_1$ and the edge connecting $v_n$ and $v_{n+1}$ are not labelled. Now, if $v_0$ exists, we shall label the edge joining $v_i$ and $v_{i+1}$ with the number $u+i$. If $v_0$ does not exist then we shall label the edge joining $v_i$ and $v_{i+1}$ with the number $u+i-1$.

If $v_0$ or $v_{n+1}$ does not exist, then the vertex they should have been connected to has degree 1, and so the labels of the edges sorrounding it do not matter. Otherwise and the case of any other vertex in the path, our process garuntees that the vertex will be sorrounded by two edges labelled by 2 consecutive numbers. Thus, that vertex will be sorrounded by edges whose greates common factor is 1, no matter how the other edges sorrounding it are labelled. Notice that from our definition of $V$, the edges $v_1,v_2,...,v_n$ are removed from $V$. Thus, it is clear that all vertices not in $V$, at any time, have edges sorrounding them that are relatively prime.

We repeat the process described until the only vertices in $V$ are those which are not connected to any other vertices in $V$. Let the least number we have not yet used by $u$. If any of them are of degree 1, we do not care. If there is a vertex $v$ of degree at least 2, then we simply label 2 of its edges $u$ and $u+1$ and now its edges are relatively prime, and we can remove it from $V$. Notice that this doesn't remove any other vertices from $V$ since $v$ is not connected to any vertices from $V$. We continue like this for the other vertices in $V$.

Now, all the vertices in $V$ are those whose edges do not matter, while all vertices not in $V$ are those with edges relatively prime. Thus we have the desired configuration, and we simply distribute the remaining numbers in any way we wish.

See Also

1991 IMO (Problems) • Resources
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 5
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1991_IMO_Problems/Problem_4&oldid=144102"