IMO shortlist 1999, C6

[drago]

Нека всяко цяло число е оцветено в един от следните четири цвята: червено, синьо, зелено, жълто.
Дадени са две нечетни цели числа [tex]x,\, y\,, \,|x|\,\neq \,|y|[/tex] .
Докажете, че съществуват две цели числа, оцветени в един и същи цвят, така че тяхната разлика е едно от числата: [tex]x,\,y,\,x+y,\,x-y[/tex] .

[drago]

Разбира се, всеки може да намери официалното решение на този проблем. Причината да постна задачата, е че намерих интересно (поне на мен) доказателство основаващо се на дискретната трансформация на Фурие. То не е по-кратко от оригиналното, както и от останалите решения, които съм виждал. Поне не е по-кратко да се изложи цялостно. Обачe e интересно като друга гледна точка.

[Knowledge Greedy]

Звучи интригуващо! Давай!

[drago]

Да допуснем противното. Тогава съществува оцветяване, такова че за всяко [tex]n \in \mathbb{Z} \,,\Rightarrow \,n, n+x, n+y, n+x+y[/tex] всичките са в различен цвят. Това означава, че ако с [tex]f(n)[/tex] означим характеристичнат функция на червените числа ([tex]1[/tex]-ца , когато [tex]n[/tex] е червено и нула, когато не е), то е в сила:

[tex]\forall n \in \mathbb{Z}\,,\, f(n)+f(n-x)+f(n-y)+f(n-x-y)=1[/tex]

Доказателството по-нататък може да проследите тук: http://www.artofproblemsolving.com/Foru ... 6#p3375556

Като мотивация: Да се мине на "брега" на Фурие е логично, тъй като отместването на функция на единия бряг, от другата страна е умножаване с едно фазово отместване. Функцията тъждествено равна на единица отива в един пик в нулата и другаде 0. Пък и съм виждал много примери на приложението на дискретната трансформация на Фурие в т.н. адитивна комбинаторика. Така че, нямах съмнения, че този подход ще работи, оставаше само техническата страна.