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

[allier]

Добре, напиши цялото разсъждение сега за тези пет прогресии - коя избираш, каква лема прилагаш ... Все едно си пишеш решението за конкретния пример.

[ptj]

Добре, напиши цялото разсъждение сега за тези пет прогресии - коя избираш, каква лема прилагаш ... Все едно си пишеш решението за конкретния пример.

Разбивам ги на 5 класа. Нека X[1],X[2],X[3],X[4] и X[5] са общите членове на прогресиите влизащи във всеки един от тях. Тогава, от факта че обединението на 5-те класа, покрива изцяло N (естествените числа), следва че поне един от класовете съдържа безброй много числа от вида X[i]+p, където p е просто. Вече показах, че всички негови прогресии без загуба на общност могат да се приемат от вида а1+k.p (k=0,1,2,.... ; p- просто). Останалото вече го писах, т.е. трябва да се приложи именно за последния клас.

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

[allier]

Не съм много съгласен - ти казваш, че може да се счита, че поне една от прогресиите има разлика просто число ... което не е достатъчно.

[ptj]

Не съм много съгласен - ти казваш, че може да се счита, че поне една от прогресиите има разлика просто число ... което не е достатъчно.

Не, си ме разбрал. Досега говорих само за прогресиите с разлики прости числа или техни степени. Останалите са им подмножества. Не "поне една", а "всички".

[allier]

Ще напишеш ли в крайна сметка цялото решение?

[ptj]

Да, нали обещах. Само да ми дойде музата.

[ptj]

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

Решение:

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

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


II.) Ще докажем една "по-силна" задача:
Ако обединението на краен брой аритметични прогресии с разлики прости числа съдържа в себе си безброй много прости числа, то поне две от тях(прогресиите) са равни разлики.


Да допуснем, че краен брой прогресии с разлики само прости числа, съдържат в себе си безброй много прости числа.
1.) Ще покажем, че всички те имат поне един общ член [tex]X[/tex].

Д-во:
Нека имаме две прогресии [tex]P_1:[/tex] {[tex]a_1+k_1.p_1[/tex]} и [tex]P_2:[/tex] {[tex]a_2+k_2.p_2[/tex]},
([tex]p_1\ne p_2[/tex]-прости; [tex]k_1,k_2[/tex] цели неотрицателни; [tex]a_1,a_2[/tex] - естествени). Според Лемата те имат общ член [tex]X_{12}[/tex].
Да разгледаме прогресията [tex]S:[/tex]{[tex]X_{12}+t.p_1.p_2[/tex]}, ( t=0,1,2...) . Очевидно [tex]S=P_1\cap P2[/tex].
Тогава съгласно Лемата [tex]S[/tex] ще има общ член с коя да е [tex]P_3:[/tex] {[tex]a_3+k_3.p_3[/tex]} ( [tex]p1\ne p3\ne p2[/tex] - прости), но той ще е общ за [tex]P_1[/tex],[tex]P_2[/tex] и [tex]P3[/tex]. Аналогично се доказва, че краен брои прогресии с прости разлики имат поне един общ член.



Нека [tex]X[/tex] е общия член за всички прогресии (от II.). Очевидно ако [tex]P[/tex] e простo числo по-голямо от [tex]X[/tex] (поне едно съществува според допускането) , то [tex]X+P[/tex] не е член на нито една от прогресиите, защото всички техни членове по-големи от [tex]X[/tex] са формално са от вида [tex]X+k.p_i[/tex]
([tex]p_i[/tex] e разликата на [tex]i[/tex]-тата прогресия, [tex]k[/tex]-естествено). Полученото противоречие показва, че допускането ни е невярно, т.е. поне две от редиците в задача II. имат обща разлика.

III. Ще покажем как оригиналната задача се свежда към II.

Нека разделим прогресиите от първата задача (с произволни разлики) на класове, според началния им член, т.е. тези с еднакъв да са от един и същи клас. Понеже обединеннието на тези класове покрива цялото [tex]N[/tex] и те са краен брой (съдържат краен брой прогресии), то поне един от тях включва в себе си безброй много прости числа. Ще разгледаме именно него -[tex]K_d[/tex].
Очевидно за всяка прогресия от споменатия клас [tex]R_i:[/tex]{[tex]a+t_i.d_i[/tex]} ([tex]a, d_i[/tex] - естествени; [tex]t_i[/tex]- цяло неотрицателно) съществува прогресия [tex]P_i:[/tex]{[tex]a+k.p_i[/tex]} ([tex]k[/tex] - неотрицателно цяло, [tex]p_i[/tex]- просто, [tex]p_i/d_i[/tex]) с проста разлика, която я съдържа.
T.e. [tex]R_i[/tex] е подмножество на [tex]P_i[/tex]. Тогава целия клас от прогресии с различни произволни разлики [tex]K_d[/tex] ще е подклас на прогресии с различни прости разлики [tex]K_p[/tex] (прогресиите с вече срещаща се разлика не ги добавяме отново). От това, че класа [tex]K_d[/tex] съдържа безброй много прости числа и от това, че [tex]K_d[/tex] е подмножество на [tex]K_p[/tex], следва че класа [tex]K_p[/tex] съдържа безброй много прости числа. Но това е невъзможно съгласно II. Получихме противоречие, което е следствие от допускането ни, че множеството на естествените числа може да се покрие с краен брой прогресии, никои две от които са с еднаква разлика.
С други думи, ако множеството на естествените числа се покрива с краен брой аритметични прогресии, то поне 2 от тях са с еднаква разлика.

[allier]

Дотук е отлично.

[ptj]

Това е. Промених само формулировката на т.II.

[allier]

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

[ptj]

Голяма драка си, пак ще ме караш да го доуточнявам.

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

[allier]

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

[allier]

Нищо не те карам да доуточняваш. Напиши ми за конкретните 5 прогресии по горе (с разлики 5, 25, и т.н.) как ти върви разсъждението ...

[ptj]

Трай малко със забележките.

[allier]

Добре, ще трая ...

[Станислав]

Задачата ми е интересна, но до момента не съм видял пълно и вярно решение от ptj. До allier - теоремата е на Дирихле Чакаме решението!

[allier]

На мен ми харесва идеята на ptj, и смятам, че може да се довърши някакси.

[ptj]

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

Решение:

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

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


II.) Ще докажем едно помощно твърдение:
Краен брой аритметичнии прогресии с прости разлики има поне един общ член.

Д-во:
Нека имаме две прогресии [tex]P_1:[/tex] {[tex]a_1+k_1.p_1[/tex]} и [tex]P_2:[/tex] {[tex]a_2+k_2.p_2[/tex]},
([tex]p_1\ne p_2[/tex]-прости; [tex]k_1,k_2[/tex] цели неотрицателни; [tex]a_1,a_2[/tex] - естествени). Според Лемата те имат общ член [tex]X_{12}[/tex].
Да разгледаме прогресията [tex]S:[/tex]{[tex]X_{12}+t.p_1.p_2[/tex]}, ( t=0,1,2...) . Очевидно [tex]S=P_1\cap P2[/tex].
Тогава съгласно Лемата [tex]S[/tex] ще има общ член с коя да е [tex]P_3:[/tex] {[tex]a_3+k_3.p_3[/tex]} ( [tex]p1\ne p3\ne p2[/tex] - прости), но той ще е общ за [tex]P_1[/tex],[tex]P_2[/tex] и [tex]P3[/tex]. Аналогично се доказва, че краен брои прогресии с прости разлики имат поне един общ член.


III. Една "странична" Теорема:
Ако обединението на краен брой аритметични прогресии с разлики прости съдържа безброй много числа от вида X+P, където X е най-малкия общ (фиксиран) за всички член, а P e просто, то поне две от тях(прогресиите) са с равни разлики.

Д-во:
Нека [tex]X[/tex] е най-малкият общ член за всички прогресии (от II.). Очевидно ако [tex]P[/tex] e някое простo числo по-голямо от [tex]X[/tex] (поне едно съществува според условието на Теоремата) , то [tex]X+P[/tex] не е член на нито една от прогресиите, защото всички техни членове по-големи от [tex]X[/tex] са формално са от вида [tex]X+k.p_i[/tex]
([tex]p_i[/tex] e разликата на [tex]i[/tex]-тата прогресия, [tex]k[/tex]-естествено). Полученото противоречие показва, че допускането ни е невярно, т.е. поне две от прогресиите от II.) имат обща разлика.

IV. Ще покажем как оригиналната задача се свежда към III.

Нека разделим прогресиите от първата задача (с произволни разлики) на класове, според началния им член, т.е. тези с еднакъв да са от един и същи клас.
Нека също формално да ги номерираме - [tex]K_1,K_2,...,K_j[/tex] ([tex]j[/tex] - броя различни начални членове).
Очевидно за всяка прогресия [tex]R_i[/tex]от кой да е клас [tex]K_l[/tex] (1?l?j), където [tex]R_i:[/tex]{[tex]a+t_i.d_i[/tex]} ([tex]a, d_i[/tex] - естествени; [tex]t_i[/tex]- цяло неотрицателно) съществува прогресия [tex]P_i:[/tex]{[tex]a+k.p_i[/tex]} ([tex]k[/tex] - неотрицателно цяло, [tex]p_i[/tex]- просто, [tex]p_i/d_i[/tex]) с проста разлика, която я съдържа.
T.e. [tex]R_i[/tex] е подмножество на [tex]P_i[/tex]. Тогава целия клас от прогресии с различни произволни разлики [tex]K_l[/tex] ще е подклас на клас от прогресии с различни прости разлики [tex]P_l[/tex] (прогресиите с вече срещаща се разлика не ги добавяме отново).
В II.) вече доказахме съществуването на съответния най-малък общ член [tex]X[/tex] за произволен такъв клас, респективно и [tex]X_l[/tex] за [tex]K_l[/tex].

Понеже обединението на класовете [tex]K_l[/tex] покрива изцяло [tex]N[/tex] (условие на оригиналната задача) и обединението на [tex]K_l[/tex] е подмножество на обединеннието на класовете [tex]P_l[/tex], то последното (обединение) включва в себе си цялото [tex]N[/tex].

Тъй като самото обединение на класове [tex]P_l[/tex] е с краен брой елементи, то поне един (примерно [tex]P_m[/tex]) от тях ще съдържа безброй много числа от вида [tex]X_m + p[/tex], където [tex]X_m[/tex] e най-малкия общ (фиксиран) член за прогресите в [tex]P_m[/tex], а [tex]p[/tex] - просто. Тогава съгласно III.) в класа [tex]P_m[/tex] има поне две прогресии с еднакви прости разлики, но това е в разрез с конструкцията на самия клас. Получихме противоречие, дължащо се на предположението, че обединението на класовете [tex]K_l[/tex] покрива изцяло [tex]N[/tex].
С други думи, ако множеството на естествените числа се покрива с краен брой аритметични прогресии, то поне две от тях са с еднаква разлика.

П.П. Малко е като един анекдот за Айнщайн : "След като написал общата теория на относителността, на първо четене и сам не я разбрал",
но този път има добър шанс да е вярно...

[allier]

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

[ptj]

Важното е, че останалите влизат в нея, т.е. те са нейно подмножество. Един вид минимизирам класа (от към брой излишни повторения) , но въпреки всичко той обхваща съответния с произволни разлики. Това е съществено.

[allier]

Друго имам предвид. Да кажем, че първият ти клас съдържа разлики 10,15, например, и от тях ти конструираш една прогесия с разлика 5, която ги съдържа. Вторият ти клас също съдържа една с по 10 и една с 15, и пак конструираш една прогресия с разлика 5. Сега не можеш да приложиш лемата ти, защото вече имаш две прогресии с равни разлики.

И още нещо, ако в един клас имаш например 5к+1 и 7к+1, коя прогресия с разлика просто число ги съдържа и двете?

[ptj]

Друго имам предвид. Да кажем, че първият ти клас съдържа разлики 10,15, например, и от тях ти конструираш една прогесия с разлика 5, която ги съдържа. Вторият ти клас също съдържа една с по 10 и една с 15, и пак конструираш една прогресия с разлика 5. Сега не можеш да приложиш лемата ти, защото вече имаш две прогресии с равни разлики.

И още нещо, ако в един клас имаш например 5к+1 и 7к+1, коя прогресия с разлика просто число ги съдържа и двете?

На първaта част: Не ме интересуват всички класове, а само този съдържащ безброй много числа от вида Х+p.

Втория ти въпрос е некоректен или по-точно не е свързан с моето доказателство. Ако питаш коя е сечение и на двете 35к+1, т.е. за тях X=36.

Виж послеписа - не е случаен.

[allier]

Добре, да допуснем, че е вярно (въпреки, че не е). Хайде сега приложи разсъжденията си за прогресиите, за които ти казах да ги приложиш (тези с разлики 5, 25, 125, ... от преди няколко поста) и покажи откъде излиза, че те не могат да покрият естествените числа.

[allier]

5k
25k+1
125k+2
625k+3
3125k+4

ето преписах ги за по-лесно. Влизаме директно в стъпка 3 на решението ти и какво правим по-точно кажи.

[ptj]

Нали ти казах, те са в различни класове (различен начален член).

Кажи ми само кой от класовете съдържа безброй много числа от вида [tex]X+P[/tex], (фиксирано [tex]X[/tex] съгласно моите означения и просто [tex]P[/tex]) и ще ти покажа противоречието.