Една задача за аритметични прогресии.

[ptj]

Множеството на естествените числа е разбито на краен брой аритметични прогресии (с разлики различни от 1-ца). Да се докаже, че ако те го покриват напълно, то поне 2 са с равни разлики.

П.П. Ако някой копира моето решение от друг форум ще му скъсам ушите.
Има и друго (оригинално), което от своя страна е с много интересна история.

П.ПП. Станислав сега може да се изяви и да докаже, че не приказва само глупости като мен.

[martin.nikolov]

Може да се реши сравнително стандартно с пораждащи функции.

Ако аритметичните прогресии са [tex]a_i+kd_i[/tex] където [tex]a_i[/tex]и [tex]d_i[/tex] са привия член и разликата на [tex]i[/tex]-тата прогресия, разглеждаме фунциите

[tex]f_i(x)=\sum_{k=0}^\infty x^{a_i+kd_i}[/tex].

Сходящи за комплексни числа [tex]|x|<1[/tex] и за тези стойности имаме [tex]f_i(x)=\frac{x^{a_i}}{1-x^{d_i}[/tex]. От друга страна [tex]\sum_i f_i(x)=\sum_{n=0}^\infty x^n=\frac1{1-x}[/tex] за стоиности на [tex]x[/tex] по модул по-малки от 1. Нека [tex]d[/tex] е най-голямото измежду [tex]d_i[/tex] и [tex]\xi[/tex] е примитивен [tex]d[/tex]-ти корен от единицата. При граничен преход [tex]x\rightarrow \xi[/tex] в равенството [tex]\sum_i f_i(x)=\frac1{1-x}[/tex] получаваме, че дясната страна клони към крайно число, а лявата, ако разликите са различни ще има точно една фунция клоняща към безкрайност. Което е противоречие, следователно не могат всичките разлики да са различни.

[ptj]

Мога само да приветсвам бързото решение.
Лошото е, че не мога да кажа дали е вярно или не (липса на знания естесвено). Единственото, което ме съмнява е дали е коректен граничния преход когато прогресиите са краен брой. Не за друго, а защото задачата за първи път е била поставена паралелно на един математичски конгрес и никой от участниците в продължение на 2 дни не успява да я реши.

[martin.nikolov]

За кой конгрес и за конгрес по какво говориш?

Задачата не е трудна, ако човек се сети да пробва с пораждащи функции. Което за подобни задачи е един от стандартните методи.

[allier]

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

Историята за конгреса и мен малко ме съмнява, но като нищо може и да е вярна ...

[ptj]

За кой конгрес и за конгрес по какво говориш?

Задачата не е трудна, ако човек се сети да пробва с пораждащи функции. Което за подобни задачи е един от стандартните методи.

Мисля, че не ме лъже паметта. Четох за нея за първи път в едно юбилейно издание на ФМИ- Пловдив, посветено на конгреса в памет на 100 годишнината от поставянето на Хилбертовите 23 проблема. Бе се появила като странична хипотеза и накрая я решава един студент, който по-късно става доста известен математик.

[ptj]

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

Историята за конгреса и мен малко ме съмнява, но като нищо може и да е вярна ...

Може и да бъркам, разбира се. Иначе аз я видях преди малко повече от седмица в един форум на dir.bg и намерих доказателство свързано с безкрайността на простите числа.

[martin.nikolov]

За кой конгрес и за конгрес по какво говориш?

Задачата не е трудна, ако човек се сети да пробва с пораждащи функции. Което за подобни задачи е един от стандартните методи.

Мисля, че не ме лъже паметта. Четох за нея за първи път в едно юбилейно издание на ФМИ- Пловдив, посветено на конгреса в памет на 100 годишнината от поставянето на Хилбертовите 23 проблема. Бе се появила като странична хипотеза и накрая я решава един студент, който по-късно става доста известен математик.

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

[ptj]

Ако знаех точно нямаше да ви държа в очакване. Освен да се разходя до библиотеката на ПУ някой ден и да видя дали няма някое копие от въпросното издание. Доколкото си спомням там бе с разглеждане на остатъци...

П.П. Моето решение ще го дам по- късно, защото може някой друг да напише подобно.

[martin.nikolov]

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

Историята за конгреса и мен малко ме съмнява, но като нищо може и да е вярна ...

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

[ubuntu]

...то се доказваше също ,че поне две от най-големите разлики са равни,иначе това решение с пораждащи функции май съм го виждал и преди.

[ptj]

1. Лема: Всеки две аритметични прогресии, чиито разлики са прости числа имат поне един общ член. Следствие е от теоремата :

"Необходимото и достатъчно условие диофантово уравнение ax + by = c да има поне едно решение е най-големият общ делител на a и b да дели с."


2. Ще докажем една "по-силна" задача, същата като оригинала , но с разлики за прогресиите прости числа. Да допуснем, че краен брой прогресии с разлики само прости числа покриват напълно N. Тогава съгласно Лема1 съществува число X, през които всички те минават. Очевидно ако P e простo числo по-голямо от X, то X+P не е член на нито една от прогресиите, защото техните членове формално те са от вида X+k.p(i) {p(i) e разликата на i-прогресия, к-естествено}. Поради факта, че едно съставно число може да се представи като сума на едно и също просто (негов делител), всички останали видове разбивания на N на аритметични прогресии ще са подмножество на някое от вече рагледаните с разлики само прости числа.
Полученото противоречие показва, че допускането ни е невярно, т.е. поне две от редиците в оригиналната задача имат обща разлика. От тук нататък няма какво да се изследва повече, защото 2*к и 1+2*к (к=1,2,...) покриват изцяло N.


П.П. Сега остава да е вярно...

[mkmarinov]

Минималният брой на аритметичните прогресии, отговарящи на условието, но за числата от 1 до n (т.е. краен брой числа) ми прилича, че расте логаритмично спрямо n. Някой може ли да повтърди?

[allier]

ptj, това решение нещо не ми харесва въобще. Ти това ли доказваш:

Ако аритметични прогресии с разлики прости числа покриват всички естествени числа, то тогава поне две от простите числа са равни.

После, обаче, като разбиеш съставните на прости, ти очевидно имаш повтарящи се прости - например прогресията с разлика 10, ти я разглеждаш като две прогресии с разлика 5, т.е. автоматично се изпълняа заключението от лемата.

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

Иначе, предполагам, че може лесно да се оправи решението.

[ptj]

...
После, обаче, като разбиеш съставните на прости, ти очевидно имаш повтарящи се прости - например прогресията с разлика 10, ти я разглеждаш като две прогресии с разлика 5, т.е. автоматично се изпълняа заключението от лемата.

Не като две, а като една. Просто тази с разлика 5 се получава от тази с разлика 10 с добавяне на нови членове. Затова казах, че едното множество е подмножество на другото. Иначе казано, тази с разлика 10 е част от някоя с разлика 5. Затова ако множеството М не може да обхване напълно N (естествените числа) , то очевидно кое да е подмножество на М също не обхваща N.

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

Иначе, предполагам, че може лесно да се оправи решението.

Да, прав си че не следва пряко. Но по принцип е вярно. Същественото е, че всички разлики са само от прости числа. Според Лемата формално мога да заменя 2-те прогресии с нови две със същите разлики и общ начален член X (посредством премахване на крaен брой членове по-малки от X). Даже нещо повече мога да взема нова прогресия с начало X и разлика произведение от двете прости разлики. Тя ще е подмножество на всяка от базовите 2 прогресии Освен това според Лемата(*) тя ще има обща точка с коя да е друга прогресия с разлика ново просто число (различно от използваните 2). Т.е. този член ще е общ и за 3-те . Аналогично е за к-на брой прогресии.

П.П. Лемата(*) е добре да се преформулира по следния начин: Всеки две аритметични прогресии, чиито разлики са взаимно прости едно с друго числа имат поне един общ член. Следствие е от теоремата :

"Необходимото и достатъчно условие диофантово уравнение ax + by = c да има поне едно решение е най-големият общ делител на a и b да дели с."

[ptj]

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

[allier]

Разбирам какво си имал предвид. Вярно е, наистина, но има пак един малък проблем. Как избираш точно простите делители? Защото, може да стане следното - да имаш разлика 5000 и разлика 4440 и двете да ги преобразуваш в 5-ци - и тогава може да се получат две прогресии с разлика 5 и за тях вече не можеш да приложиш твърдението, което използваш.

[ptj]

Разбирам какво си имал предвид. Вярно е, наистина, но има пак един малък проблем. Как избираш точно простите делители? Защото, може да стане следното - да имаш разлика 5000 и разлика 4440 и двете да ги преобразуваш в 5-ци - и тогава може да се получат две прогресии с разлика 5 и за тях вече не можеш да приложиш твърдението, което използваш.

Двете ги обединявам в една с разлика 5. Тя реално обхваща и двете, даже малко повече от тях.

[allier]

Ама може едното да води до 5k+1, а другото до 5k+2. Тогава как се обединяват?

[ptj]

Ама може едното да води до 5k+1, а другото до 5k+2. Тогава как се обединяват?

Чакай малко да помисля.

[ptj]

Разбирам какво си имал предвид. Вярно е, наистина, но има пак един малък проблем. Как избираш точно простите делители? Защото, може да стане следното - да имаш разлика 5000 и разлика 4440 и двете да ги преобразуваш в 5-ци - и тогава може да се получат две прогресии с разлика 5 и за тях вече не можеш да приложиш твърдението, което използваш.

Ако имат поне един различен прост делител в различни, иначе... Хм, резонен въпрос, ще ми трябва време...

Ти не се ли сещаш нещо? Въпрoса е как да се излъже случая, когато едната прогресия е например 3k, а другата 9l+1.

[allier]

Да, мислих и аз малко по въпроса. Ако можем да изберем система различни представители от простите делители, тогава е ОК. Въпросът е, че не винаги това е възможно. Другото нещо е например, ако имаме прогресиите:
5k
25k+1
125k+2
625k+3
3125k+4

тогава можем да изберем само делителя 5 и да получим:
5k
5k+1
5k+2
5k+3
5k+4

А тези описват всички естествени числа. Ето това трябва да се избегне някакси, защото иначе нищо няма да се получи с този метод.

[ptj]

Мисля, че се сетих. Разбиваме ги на класове според началния елемент. Всички прогресии започащи от едно и също число ще са в един и същ клас. От това, че обединението на класовете покрива N следва, че поне един от тях е с мощността на N и ще съдържа безброй много прости числа. Очедно ако в него има прогресии от вида [tex]a1+k.p[/tex] и [tex]a1+l.p^n[/tex] то втората е подмножество на първата. Тогава без загуба на общност може да считаме, че всички прогресии имат за разлики само прости числа, а не техните степени. Защото вторите се включват изцяло от първите. Нататък доказателството си остава като вече написаното в предишните ми 2 мнения.

П.П. Чакам коментар от allier и останалите.

[allier]

Добре, а конкретно за тези пет прогресии от по-горния ми пост какво правиш?
5k
25k+1
125k+2
625k+3
3125k+4

[ptj]

Те са в 5 различни класа. Единия от които, съдържа безкрайно много числа от вида Х+p, където p e просто. За него прилагам старите разсъждения.