Difference between revisions of "2013 IMO Problems/Problem 6"
Illogical 21 (talk | contribs) |
(→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 be an integer, and consider a circle with equally spaced points marked on it. Consider all labellings of these points with the numbers 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 with , the chord joining the points labelled and does not intersect the chord joining the points labelled and .
Let be the number of beautiful labelings, and let N be the number of ordered pairs of positive integers such that and . Prove that