задача

Мярна ми се една задача. Ако множеството от естествени числа е разбито на крайно много(и поне две) аритметични прогресии, тогава поне две имат еднаква разлика.

Това звучи повече като твърдение, отколкото като задача.

Задачата е да се докаже твърдението, разбира се.

Требе да е сложно , щом си го турнал тук. Иначе шеше сам да си го решиш , а не да питаш нас брат.

/( . )( . )\

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

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

Я как стигна до този извод, защото и аз мислих, но не измислих решение.

Задачата: Ако множеството от естествени числа е разбито на крайно много(и поне две) аритметични прогресии, тогава поне две имат еднаква разлика.

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

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


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

П.П. Сори за забавянето, но ми беше ясна само общата идея. Малко съм закъсал с техника за времето, което съм далеч от математиката (над 20 години).

Жената е слабо, беззащитно създание, от което няма спасение.

Не съм съгласен с извода.

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

Напротив, ще означава, че простите числа, използвани като разлики на такива прогресии, са по-малки от Х. Ако използваш всички прости числа, а не например 1000 или 1000000, то тогава нарушаваш условието за краен брой прогресии, на които е разбито N.


Ето в каква посока тръгнах аз, но не мога да довърша решението:
Случаят, при който първите членове на крайния брой прогресии са равни на разликите е очевиден. При него всеки член на всяка прогресия може да се представи като произведение на разликата и някакво естествено число. Това е в противоречие с факта, че простите числа са безкрайно много или с условието, че прогресиите са краен брой. Това преполагам си искал да кажеш и ти.
Случаят, при който разликите не е задължително да са равни на първите членове, е по-сложен. При него всяко просто число може да е член на някоя от прогресиите, като това не влиза в противоречие с нищо. Опитах да докажа, че всяко разбиване ще даде поне две прогресии, на които членовете ще дават константни остатъци при делене на някакво число Х, но не успях (това е алтернативна дефиниция на задачата). Например членовете на прогресията S0 дават остатък r-3 при делене на и, на S1 дават r-4 при делене на r. От това следва, че двете прогресии имат еднаква разлика - r.
Опитах и да "разделям постъпково" N на прогресии, като докажа, че е невъзможно да не се получат поне две, на които членовете да не дават един и същ остатък при делене на Х, но там вече ме домързя да мисля, признавам си.

Погледни пак , защото коригирах решението.

Жената е слабо, беззащитно създание, от което няма спасение.

Благодаря, ще го погледна после, че сега ще излизам.

Само да допиша какво мислих аз, когато решавах задачата.

Вземаме N и го разделяме на p прогресии. Членовете на всяка (поотделно) ще дават остатъци от 0 до p-1 при делене на p. това ще наричаме "разделяне от първи ред".
Вземаме някоя от тях и я разделяме на други q прогресии (p и q може и да са равни). Те ще дават остатъци от 0 до q-1 при делене на q. Това ще наричаме "разделяне от втори ред". Ако p=q то всички нови прогресии ще дават един и същ остатък при делене на q, вместо от 0 до q-1.
И така нататък продължаваме ...

След всяко разделяне, ако то е на m нови прогресии, то те ще дават константни остатъци при делене на m (от 0 до m-1) или едни и същи, т.е. ще имат общи разлики.

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

Има малка дупка (неточност в доказателството), но мисля че е поправима. Става въпрос, че аз предполагам всички разлики на прогресиите p(i) делят Х. Довечера ще измисля някой трик.

П.П. Даже вече го имам. Ако P e просто число по-голямо X, то Х+P не е член на нито една от прогресиите.

Кога за първи път е поставена тази задача. Ако не ме лъже паметта, някъде около 2000 година подобен проблем случайно се повдига между участниците на някаква математична конференция в европейска държава (Финландия, Швеция или някоя съседка). Тогава всички си мислят, че решението би трябвало да е лесно, но никой не успява да го намери. Накрая то се удава на един никому неизвестен студент първокурсник. Въпросния студент сега не е случайно име в съвремената математика. Прав ли съм или не?

П.П. Неговото решение май беше по-различно...

Жената е слабо, беззащитно създание, от което няма спасение.