Difference between revisions of "2013 IMO Problems/Problem 6"

(Problem)
Line 3: Line 3:
  
 
Let <math>M</math> be the number of beautiful labelings, and let N be the number of ordered pairs <math>(x, y)</math> of positive integers such that <math>x + y \le n</math> and <math>\gcd(x, y) = 1</math>. Prove that <cmath>M = N + 1.</cmath>
 
Let <math>M</math> be the number of beautiful labelings, and let N be the number of ordered pairs <math>(x, y)</math> of positive integers such that <math>x + y \le n</math> and <math>\gcd(x, y) = 1</math>. Prove that <cmath>M = N + 1.</cmath>
 +
 +
==Solution==
 +
 +
{{solutions}}

Revision as of 16:25, 14 September 2023

Problem

Let $n \ge 3$ be an integer, and consider a circle with $n + 1$ equally spaced points marked on it. Consider all labellings of these points with the numbers $0, 1, ... , n$ such that each label is used exactly once; two such labellings are considered to be the same if one can be obtained from the other by a rotation of the circle. A labelling is called beautiful if, for any four labels $a < b < c < d$ with $a + d = b + c$, the chord joining the points labelled $a$ and $d$ does not intersect the chord joining the points labelled $b$ and $c$.

Let $M$ be the number of beautiful labelings, and let N be the number of ordered pairs $(x, y)$ of positive integers such that $x + y \le n$ and $\gcd(x, y) = 1$. Prove that \[M = N + 1.\]

Solution

Template:Solutions