Maths Olympiad Prep

Library / /48 of 61

Number theory Difficulty 6.3 National olympiad Prove it Ukraine

A circle is divided into 20062006 equal arcs by 20062006 points. Baron Munchausen claims that he can construct a closed polygonal curve with the set of vertices consisting of these 20062006 points such that amongst its 20062006 edges there cannot be found any two, which are parallel to each other. Is his claim true or false?

Solution

Відповідь: ні, барон помиляється. Позначимо 20062006 точок поділу числами 0,1,2,,20050, 1, 2, \ldots, 2005, записаними послідовно. Ланки ламаної будемо позначати номерами її кінців. Нескладно перевірити, що якщо i+j=k+li + j = k + l (mod 20062006), то ланки iji j та klk l будуть паралельними. Припустимо, що барон Мюнхгаузен правий. Тоді існує така перестановка n1,n2,,n2006n_1, n_2, \ldots, n_{2006} чисел 0,1,2,,20050, 1, 2, \ldots, 2005, що всі суми n1+n2,n2+n3,,n2005+n2006,n2006+n1n_1 + n_2, n_2 + n_3, \ldots, n_{2005} + n_{2006}, n_{2006} + n_1 попарно неконгруентні за mod 20062006. Тоді цей набір також є деякою перестановкою чисел 0,1,2,,20050, 1, 2, \ldots, 2005. Таким чином,
(n1+n2)+(n2+n3)++(n2006+n1)0+1++20051003(mod2006) (n_1 + n_2) + (n_2 + n_3) + \dots + (n_{2006} + n_1) \equiv 0 + 1 + \dots + 2005 \equiv 1003 \pmod{2006}
Але, з іншого боку,
2n1+2n2+2n3++2n20062(0+1+2++2005)0(mod2006). 2n_1 + 2n_2 + 2n_3 + \dots + 2n_{2006} \equiv 2(0 + 1 + 2 + \dots + 2005) \equiv 0 \pmod{2006}.
Одержана суперечність і доводить, що барон Мюнхгаузен помиляється.

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.