TST България 2003

[drago]

Във всеки възел на безкрайната целочислена решетка в равнината е записано реално число между [tex]0[/tex] и [tex]1[/tex].
Известно е, че числото записано във всеки възел [tex](i,j)[/tex] е равно на средноаритметичното на [tex]4[/tex]-те съседни числа записани в [tex](i-1,j), (i, j-1), (i+1,j), (i,j+1)[/tex].
Да се докаже, че всички записани числа са равни.

[grav]

Ето първото което ми хрумва. При дадена точка и естествено n разглеждаме точките, които могат да се достигнат от дадената с по-малко от n стъпки т.е. кълбото относно таксиметровата (или манхатъновата) метрика. Средноаритметияното свойство важи и ако вместо непосредствените съседи разглеждаме и кълбо с произволен радиус. При дадени две точки разглеждаме кълба с центрове точките и радиус n. При голямо n двете кълба се покриват много и следователно разликата в стойностите е само по точките извън сечението на двете кълба. От това, че стойностите са ограничени и от това, че точките извън сечението разделени на броя на точките в кълбото клони към нула когато n клони към безкрайност следва исканото.

[inveidar]

re6enie.JPG (158.2 KiB) Прегледано 490 пъти

Някой може ли да "преведе" това решение на нормален език?

[Гост]

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

[Гост]

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

Откъде знаем, че има най-малко число?

[mkmarinov]

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

[drago]

Ето първото което ми хрумва. При дадена точка и естествено n разглеждаме точките, които могат да се достигнат от дадената с по-малко от n стъпки т.е. кълбото относно таксиметровата (или манхатъновата) метрика. Средноаритметияното свойство важи и ако вместо непосредствените съседи разглеждаме и кълбо с произволен радиус. При дадени две точки разглеждаме кълба с центрове точките и радиус n. При голямо n двете кълба се покриват много и следователно разликата в стойностите е само по точките извън сечението на двете кълба. От това, че стойностите са ограничени и от това, че точките извън сечението разделени на броя на точките в кълбото клони към нула когато n клони към безкрайност следва исканото.

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

[drago]

Благодаря Емо,
това е официалното решение предполагам. Постнах я в този форум с надеждата, че колкото и постен да е станал, все може да я прочете някой, участвал в това контролно или както в случая да разполага с тези материали.
Иначе задачата ми стана известна преди около 2-3 месеца, когато излезе като ъпдейт на пост в арт-а. Ето препратката, за който има интерес: http://www.artofproblemsolving.com/Foru ... =41&t=5327
И така прочитам заглавието на темата ("Very hard"), чета и условието и си мисля "Я че това не трябва да е трудна задача за контролно за МОМ". След това почвам да чета коментарите отдолу (те са над 70 поста) и разбирам, че няма дадено решение с елементарни средства, т.е. с това, което се учи в училище, колкото и широко понятие да е.
В началото е дадено някакво решение, по скоро скица, при това много наедро, която използва свойства на изпъкналостта в определени топологични пространства- някаква вариация на теоремата на Крейн-Милман. След това има цяла поредица от вероятностни интерпретации.
Ето това е причината да ме заинтересува и започнах да мисля върху нея. Функции с това свойство се наричат дискретни хармонични, по подобие с непрекъснатия вариант, където това твърдение е известно и се нарична теорема на Лиувил (по-скоро някакъв по-слаб неин вариант). Та близко е до ума да се пробва да се докаже по същата схема- това, което grav е написал по-горе. Обаче уви, свойствата на дискретните хармонични функции не са същите, като непрекъснатия им аналог. Все пак този подход може да доведе до резултат.
Сега по официалното решение и по въпроса на Емо- "какво става тук..."

Те въвеждат първата крайна разлика [tex]g(x,y)= f(x+1,y)-f(x,y)[/tex]. Aко допуснем, че [tex]f[/tex] не е константа то [tex]g[/tex] няма да е тъждествено [tex]0[/tex] и [tex]M= \sup \, g[/tex], няма да е [tex]0[/tex].
Проверява се, че [tex]g[/tex] също е хармонична, т.е. удовлетворява условието, че стойността и във всяка точка е равна на усреднената стойност в съседните точки. Поради тази причина, ако вземем стойност [tex]g(x,y)[/tex] близка на тази на супремума (на [tex]M[/tex]) т.е [tex]g(x,y) > M-\varepsilon[/tex], то във всяка от четерите съседни точки стойността на функцията не може да бяга много от M. т.е.
[tex]g(x+1,y) > M-4 \varepsilon[/tex] или като приложим няколко пъти това съображение:
[tex]g(x+n,y) > M - 4^n \varepsilon[/tex].
Сега от дефиницията на g имаме, че:

[tex]f(x+n,y)-f(x,y) = \sum_{k=1}^{n-1} g(x+k,y)[/tex].

И сега тук е гвоздея- лявата част е между 0 и 1, а всеки член на дясната е близък до M (M>0). Tъй като тази близост може да я нагодим колкото искаме точно(избираме [tex]\varepsilon[/tex] произволно близко до 0) и колкото и малко да е M, може да изберем дост. голямо n така че дясната страна да стане колкото искаме голяма. Другото е рутина да нагласим формално тези избори на [tex]n[/tex] и [tex]\varepsilon[/tex].

[grav]

Да, точно това беше идеята. Жалко, че не става, може би трябваше да го разпиша подробно и да видя, че не работи. Сега се разрових из нета, както и очаквах, има доста интересни неща за дискретни хармонични функции.

[drago]

Между другото официалното решение може да се обобщи, със същите хватки, и за [tex]n[/tex]-мерния случай на дискретна хармонична функция при това решението е доста кратко.
Така де, това дава отговор и на цитирания по-горе пост в арт-а. Там има доказателство на това обобщение, но е много по-дълго.