Разбиване на ест. числа без безкр. прогресии

[drago]

Скоро ми попадна следната задача. Не че е трудна, но ми се стори интересна.

Да се докаже, че естествените числа могат да се разбият на две множества, така че нито едно от двете да не съдържа безкрайна аритметична прогресия.

[pal702004]

Сигурно има много начини, но например: Ако естественото число в двоичен вид има четен брой единици - в едната група, а нечетен - в другата. Тогава всяка безкрайна аритметическа прогресия ще съдържа елементи и от двете групи. Най-малкото, защото
[tex]a+d[/tex] и [tex]a+2^kd[/tex] при достатъчно голямо k ще са от различни групи.

[drago]

... Най-малкото, защото
[tex]a+d[/tex] и [tex]a+2^kd[/tex] при достатъчно голямо k ще са от различни групи.

Като цяло изглежда ОК, но това не е вярно!
[tex]2+1[/tex] и [tex]2 + 2^k[/tex] при [tex]k>1[/tex] са от една и съща група !!

[pal702004]

Така е, Драго. Още като написах съобщението видях, че съм написал глупост. Всъщност a и [tex]a+2^kd[/tex] ще са от различни множества при голямо k, само ако d е от множеството с нечетните единици. Не знам защо избрах този сложен начин, може да се постави като отделна задача. За тази да опитаме нещо по-простичко, например: В едната група числата с нечет брой цифри (в двоична, но май и във всяка бройна система), а в другата - с четен брой. Т.е., последователните числа от [tex]2^n[/tex] до [tex]2^{n+1}-1[/tex] са в една група, следващите в друга. Колкото и да е голяма раликата на прогресията, ще се намери достатъчно дълъг интервал, който няма да може да "прескочи".

Или без бройни системи
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15...
Когато броят на последователниче числа от една група стане повече от разликата на прогресията, мачът свършва.

[drago]

... Колкото и да е голяма раликата на прогресията, ще се намери достатъчно дълъг интервал, който няма да може да "прескочи"....
...Когато броят на последователниче числа от една група стане повече от разликата на прогресията, мачът свършва.

Да, това е една от идеите, която може да се използва. Видях тази задача някъде из арт-а. Една от конструкциите се основаваше на тази идея и тя е много естествена. Всички доказателсва бяха с директна конструкция, в която експлицитно се посочва как точно да се направи разбиването. Сега накратко и моето решение:
Нека подредим всички аритметични прогресии в редица: [tex]P_1, P_2,\ldots[/tex]. Множествата [tex]A[/tex] и [tex]B[/tex] в началото са празни.
1. Полагаме [tex]i:=1[/tex], Вземаме [tex]P_i[/tex], избираме два произволни нейни члена и единия пресъединяваме към [tex]A[/tex], другия към [tex]B[/tex]. Увеличаваме [tex]i[/tex] с единица и минаваме към точка 2.
2. Вземаме два произволни члена на [tex]P_i[/tex], така че да не принадлежат към [tex]A\cup B[/tex] и добавяме единия към [tex]A[/tex], другия към [tex]B[/tex]. Увеличаваме [tex]i[/tex] с единица и минаваме към т.2.

Тези, естествени числа, които остават неприсъединени нито към A, нито към B, слагаме произволно в в някоя от тези групи.