Задачка

[luboslav_p]

Възможно ли е множеството на естествените числа да се разбие на 2 множества A и B, за които A не съдържа 3-членна аритметична прогресия, а B не съдържа безкрайна аритметична прогресия?

[Реклама]

[allier]

Хубава задача. Имаш ли някакво по-кратко решение защото моето използва доста сериозна теория и е доста дълго? Има теорема даже, която казва че множество с положителна горна плътност съдържа безкрайна прогресия, и това тук се прилага директно тъй като двете множества се допълват до N.

[Baronov]

Теоремата, която цитираш (предполагам е http://en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem) казва, че в множество с положителна плътност има произволно дълга аритметична прогресия, а не безкрайна.

[allier]

Ne govorya za taya teorema, za neshto podobno stava vupros razraboteno prez 2000 i nqkoq si godina kato dopulnenie kum Szemeredi, kudeto direktno si stava vupros za bezkraina a ne proizvolno dulga progresiya.

[luboslav_p]

Ще скицирам накратко решението, което аз знам. Първо на всяка аритметична прогресия с първи член а и разлика d можем да съпоставим целочислена точка в първи квадрант (без двете оси) с кординати (а,d). Сега множеството от тези точки е изброимо т.е. можем да си ги подредим в редичка и да ги номерираме с числата 1,2,... Конструираме множеството А с елементи а1,а2,... по следния начин: а1=1 ; а_n+1≥2a_n и а_n+1 е от n+1-та аритметична прогресия. Избираме B да допълва A до N. Оттук е ясно, че А и B изпълняват условието.