Коши-Девенпорт

[drago]

Днес попаднах на следващата задача давана на националната олимпиада по математика 2004.(в България)

Задача 6. Нека [tex]p[/tex] е просто число. За произволни цели числа [tex]0 \leq a_1 <a_2< \ldots < a_m < p[/tex] и [tex]0 \leq b_1 < b_2< \ldots < b_n < p[/tex] да означим с [tex]k[/tex] броят на различните остатъци при деление на [tex]p[/tex] на числата [tex]a_i + b_j ,\, 1 \leq i \leq m, \, 1\leq j \leq n[/tex]. Да се докаже, че:
а) ако [tex]m + n > p[/tex], то [tex]k = p[/tex];
б) ако [tex]m + n \leq p[/tex], то [tex]k \geq m + n - 1[/tex].

Отдолу си имаше и автори... Tова е известно като теорема на Коши-Девенпорт.
Подточка а) е лесната част. Интересно ми е колко ли участника са решили б).
Проблемът не е че се дава трудна задача, която има някаква история, а че на финален кръг се дава като задача един много известен резултат, и то директно едно към едно. Което би облагодетелствало ученици, на които това им е известно-примерно правено на школа и т.н. Както и да е, вече не е актуално.
Ето една подобна задача http://www.artofproblemsolving.com/Foru ... 2&t=495629 ,давана на TST в Румъния 2010, но поне е малко по-завоалирана от известната теорема.

[Гост]

http://www.cut-the-knot.org/Curriculum/ ... ions.shtml
това е давано през 76-а на областен кръг. Давани са и неизбрани задачи, предлагани от България за IMO.
Винаги някой ще е облагодетелстван. Това е дъвкана тема и почти се знае кой и кога е облагодетелстван.
Много трудно е да се измислят изцяло нови задачи, а и може хората, които са ги предлагали твърденията
да не са знаели, че са вече известни факти. На мен ми се е случвало да преоткрия вече известни неща.
Ако на олимпиадата се гледа по друг начин - като възможност човек да види красиви задачи и да научи нещо -
това я прави много красива и полезна.

[drago]

Горният Гост много ми прилича в изказа на Боби(Инс).
На олимпиада не се ходи, човек да види красиви задачи и да научи нещо. На олимпиада се ходи, човек да получи колкото може повече точки. За първото са останалите 364 дни.
Не е възможно да не са знаели, че това е Коши-Девенпорт. Това е все едно да дадеш на финален кръг теоремата на Брианшон- как ти се струва. Иначе да-по състезания се дават шортлисти от предна година, по принцип тяхното оповестяване се отлага с година. Обаче според мен пак не е удачно за финален кръг. Виждал съм по форуми изтичане на задачи от предна шортлиста.

[ins-]

Постът действително е мой. Не знам защо, но не вярвам много в случайните неща. Лесно е човек да се окаже малък пред привидно лесни задачи .
Виждам, че всеки плюе НОМ понякога, но никой не предлага нещо по-добро, затова имам едно предложение.
Може да се съберем повече хора - за предпочитане е всеки да е добър в конкретна област и да направим "алтернативна олимпиада" - със същата периодичност като тази на националната, да видим какво ще стане и дали е лесно да се подготви едно състезание, а хората които дават задачите за националната ще казват какви забележки имат
Как Ви се струва тази идея?

[Гост]

pri4inata da se dade zada4ata be6e originalnoto re6enie na vtorata 4ast predlozeno ot avtorite,a 4e zada4ata e izvestna teorema be6e izvestno na komisiqta.

[Гост]

Tova,4e zada4ata e izvestna teorema,ne pomogna na nikoi pri re6avaneto na podto4ka b),vklu4itelno i na gostite ot Ruskiq nazionalen otbor.

[drago]

Просто исках да си кажа мнението, че на такива състезания не е удачно да се дават като задачи известни теореми.
Не съм плюл НОМ, нито пък си мисля, че мога да дам по-добри задачи.

pri4inata da se dade zada4ata be6e originalnoto re6enie na vtorata 4ast predlozeno ot avtorite,a 4e zada4ata e izvestna teorema be6e izvestno na komisiqta.

Ето го официалното решение; от книжката "Bulgarian Mathematical Competitions 2003-2006".

cauchy-davenport.png (66.72 KiB) Прегледано 580 пъти

Ако става въпрос за него, то това е най-известния метод за доказване на тази теорема. Множествата [tex]A[/tex], [tex]B[/tex] се трансформират в [tex]A'[/tex], [tex]B'[/tex], така че [tex]|A|+|B|=|A'|+B'|,\, |A'|<|B'|[/tex] и [tex]A'+B' \subset A+B[/tex], така че доказателството от [tex]A,B[/tex] се прехвърля към [tex]A',B'[/tex], но тази двойка е "по-минимална" от [tex]A,B[/tex]. В случая се прави т.н. Dyson transform, [tex]A,B[/tex] се заместват с [tex]A'=A\cap B,\, B'=A\cup B[/tex],като се внимава за случаите, когато [tex]A\cap B =\emptyset[/tex] или [tex]A\subset B[/tex] . В тези случаи, за да се избегне това, [tex]A[/tex] се транслира подходящо [tex](A\to x+A)[/tex] и точно тук се използва това, че [tex]p[/tex] е просто...
Мисля, че по същество това е и доказателството на Коши.
Същото доказателство може да видите и тук:
http://www.math.cmu.edu/~af1p/Teaching/ ... cs/Tao.pdf
а такова, основаващо се на трансформацията на Девенпорт тук:
http://www.folk.uib.no/nmaoy/papers/sumsetsR.pdf