Аритметични прогресии, подборен кръг България 2008

[drago]

Съществуват ли 2008 безкрайни аритметични прогресии със следните свойства?
(i) Всеки 2 от тях нямат общо число.
(i) Всяко число, с изключение на краен брой числа, попада в някоя от аритметичните прогресии.
(iii) Всяка аритметична прогресия съдържа просто число по-голямо от 2008.

[ptj]

Не съществуват. Първите 2 условия са несъвместими.

Следствие е от една по обща задача, която публикувах тук, но не успях да докажа:

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

Мартин Николов я доказа с пораждащи функции:

...
Ако аритметичните прогресии са [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] получаваме, че дясната страна клони към крайно число, а лявата, ако разликите са различни ще има точно една фунция клоняща към безкрайност. Което е противоречие, следователно не могат всичките разлики да са различни.

[drago]

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

[ptj]

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

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

[drago]

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

Тогава е достататъчно да изберем разликата на всички прогресии да е 2008, а съответно началните членове естествените числа от 1 до 2008.

...Не бързай да пишеш нещо, премисли го още един път...

Аз ли да ти кажа къде куца това, което си написал или ще се сетиш ?

[ptj]

Чакай малко де, разбрах веднага.

[nikko]

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

Я пак? А прогресията [tex]2+2d, d\in\mathbb{N}[/tex]?

[Xixibg]

Ако изберем прогресиите с начален елемент нечетните числа от 1 до 4015 и разлика 4016 то остава само да докажем (III)

[ptj]

Ако изберем прогресиите с начален елемент нечетните числа от 1 до 4015 и разлика 4016 то остава само да докажем (III)

Поне да беше чел моите глупости.

[tex]4016k[/tex] е безкрайно множество.

--------------------------

Освен 2-те точки по-горе, може да се използва и следното:

Ако съществуват две прогресии с взаимно прости разлики [tex](d_1;d_2)=1[/tex], то съществуват цели числа [tex]m,n[/tex], за които [tex]md_1+nd_2=1[/tex] или .
Тогава [tex](a_1-a_2)md_1+(a_1-a_2)nd_2=a_1-a_2[/tex], т.е. двете прогресии ще имат общ член.
Последното е в противоречие с условие(i) и в крайна сметка води, че всички разлики на прогресиите са кратни на едно също число по-голямо от 1.

Нека това число е [tex]p[/tex]. Тогава за да имат различни елементи всички прогресии, техните начални членове [tex]a_i[/tex] трябва да дават различни остатъци при деление на [tex]p[/tex].

По-горе обясних защо [tex](a_i;p)=1[/tex] (Теорема на Дирихле).
Това води, че нито един член на безкрайната редица {[tex]kp[/tex]} няма да се покрива от множеството на прогресиите.

Т.е. задачата няма решение.

[Xixibg]

Съществуват ли 2008 безкрайни аритметични прогресии със следните свойства?
(i) Всеки 2 от тях нямат общо число.
(i) Всяко число, с изключение на краен брой числа, попада в някоя от аритметичните прогресии.
(iii) Всяка аритметична прогресия съдържа просто число по-голямо от 2008.

Не съм разбрал условието.Задачката трябва да се мисли

[drago]

...Последното е в противоречие с условие(i) и в крайна сметка води, че всички разлики на прогресиите са кратни на едно също число по-голямо от 1.

Нека това число е [tex]p[/tex]...

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

Например 6, 10, 15

[drago]

Решението:
Нека означим прогресиите с [tex]P_i,\, i=1,2,\cdots,2008 , P_i = \left\{a_i + kd_i \right\}_{k=0}^{\infty}[/tex]. Нека за определеност [tex]d_1 \leq d_2 \leq \cdots \leq d_{2008}[/tex].

[tex]P_i \cap P_j = \empty \, <=> \, \not\exists n,m \in \mathbb{N}, \, a_i - a_j = n d_j - m d_i[/tex]

<=> (1) [tex]\gcd(d_i, d_j)[/tex] не дели [tex]a_i - a_j[/tex]

в частност [tex]\gcd(d_i, d_j) > 1 , \, \forall i,j \, i \neq j[/tex].

Сега да вземем числата [tex]\{kd_1\}_{k=1}^{\infty}[/tex]. От (ii) следва че от някое място нантатък всяко от тези числа попада в някоя(възможно различни) прогресия.

Нека [tex]k d_1 \in P_j[/tex] <=>

(2) [tex]k d_1 = a_j + n d_j[/tex].

Нека [tex]d=\gcd(d_1, d_j)[/tex] Oт (1) следва [tex]d>1[/tex]. От (2) => [tex]d/a_j[/tex]. Но [tex]d/a_j[/tex] и [tex]d/d_j[/tex] противоречи на (iii).