Аритметични прогресии, IMO shortlist 2010

[drago]

Нека [tex]P_1, P_2,\cdots, P_s[/tex] са безкрайни аритметични прогресии от цели числа, удовлетворяващи следните изисквания:

(i) Всяко цяло число принадлежи на поне една от тези прогресии.

(ii) Всяка от тези прогресии съдържа число, непринадлежащо на никоя от останалите прогресии.

Да означим с [tex]n[/tex] най-малкото общо кратно на стъпките(разликите) на тези прогресии и нека [tex]n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}[/tex], където [tex]p_1,\cdots, p_k[/tex] са прости числа.

Докажете, че:

[tex]s \geq 1+ \sum_{i=1}^k \alpha_i (p_i - 1)[/tex].

[drago]

Трудна ли е?

[grav]

За съжаление вече съм я виждал и не мога да се абстрахирам от решението да я мисля самостоятелно.

[drago]

A къде си я виждал решена- в mathlinks или някъде другаде?

[grav]

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

А, забравих, какво е mathlinks?

[inveidar]

Видях двете решения от Шортлиста. Ужас!!!

[drago]

...
А, забравих, какво е mathlinks?

http://www.mathlinks.ro или www.artofproblemsolving.com

[drago]

Видях двете решения от Шортлиста. Ужас!!!

Ако говорим за едно и също, първото е ужасно написано, а второто е препратка към историята на този резултат. Да, в основата е П. Ердьош, но резултатът обобщава една хипотеза на J. Mylcieski and W. Sierpinski, доказана от I. Korec.
Но, когато я решавах не знаех това

[inveidar]

Говоря за това -

Pages from IMO_Shortlist_2010.pdf

(164.58 KiB) 102 пъти

[drago]

Да, трудна си е задачата, и почти невъзможно е да се реши в реално време, затова и е отпаднала от IMO. Това предполагам са официалните решения?

Аз имах предвид проекта на mathlinks за събиране онлайн на всички шортлисти: http://www.artofproblemsolving.com/Foru ... db4dda52c5
2010 г., Combinatorics, 7 зад.

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