Резултати от международната олимпиада 2020 г.

[Гост]

Какво мислите за резултатите от международната олимпиада от тази година?

https://www.imo-official.org/year_count ... ?year=2020

[drago]

Какво да мисля, слабо е представянето ни за съжаление - 38мо място. Като изключим Мартин Копчев, който е решил 3-та, останалите имат сумарни точки по трите задачи - 2-ра, 3-та и 6-та общо 8т! Да, 6-та е трудна, само 5 състезатели са я решили задоволитено. Може би по 2-ра (неравенството) би трябвало да имаме по-добър резултат, по 3-та също би могло по-добре. Ами каквото, такова, другата година дано повече!
Лично на мене задачите ми харесват, шортлистът за 2019 също. С изключение на 2-ра, явно решили са да има неравенство, поне са пропуснали функционалното уравнение , но пък като за такова не е чак толкова зле. 6-та и 3-та са много хубави! В последните години тенденцията при подбора на задачите ми харесва.

[peyo]

Измислих решение на

Задача 5.Дадено е тесте от n>1 карти. Върху всяка карта е написано естествено число. Тестето има свойството, че средното аритметично на числата върху всяка двойка карти е равно на среднотогеометрично на числата върху група от една или повече карти. За кои n от горното условие следва, че числата върху всички карти са равни?

Случая n =1 не е интересен.

Ако n=2 Как да съставим тесте с 2 различни числа?
к1 к2
x y

Трябва:
(x+y)/2 = x
или
(x+y)/2 = y
или
$(x+y)/2 = \sqrt{xy}$

(x+y)/2 = x
x/2 + y/2 = x
y/2=x/2
y=x

Същото за 2-рото.

За 3-тото уравнение обаче ще смятаме:

$(x+y)/2 = \sqrt{xy}$

$x/2 +y/2 = \sqrt{xy}$

$x^2/4 + xy/2 + y^2/4 = xy$

$x^2/4 + y^2/4 = xy/2$

$x^2 -2xy + y^2= 0$

$(x-y)^2=0$

=>

$x=y$
И така за n=2 доказахме, че е невъзможно да има карти с различни номера.

Сега може би да пробваме да измислим някаква индукция

Ако имаме 3 карти. Тогава ще имаме 3 двойки карти. Ако всички са еднакви няма проблем. Ако имаме 2 различни карти, тогава според случая n = 2, не можем да намерим равенствво с 1 или 2 карти. Значи трябва да са 3 и всички от следните група от уравнения Г3 да валидни:

Г3:
$(x+y)/2 = ({xyz})^{1/3}$
$(x+z)/2 = ({xyz})^{1/3}$
$(y+z)/2 = ({xyz})^{1/3}$

Тогава излиза, че
$x=y=z$

Да видим за n=4

Тогава ще имаме 4!/2 = 12 двойки карти. Ако всички са еднакви няма проблем. Ако имаме 2 различни карти, тогава според случая n=2 и n=3 , не можем да намерим равенствво с 1 или 2 или 3 карти. Значи остава да проверим за n=4 където ще стигнем то подобна група като Г3 само, че ще е Г4 от 12 уравнения

$(x+y)/2 = ({xyzw})^{1/4}$
$(x+z)/2 = ({xyzw})^{1/4}$
...
...

Което явно има единствено решение:
$x=y=z=w$

При n=5 ще знаeм, че няма решения с по малко от 5 карти, а с 5 карти всички трябва да са еднакви.
При n=6 подобно.
...
При n=n ще знаeм, че няма решения с по малко от n карти, а с n карти всички трябва да са еднакви.

И така отговора на

За кои n от горното условие следва, че числата върху всички карти са равни?

За всяко n.

[drago]

Сега може би да пробваме да измислим някаква индукция

Ако имаме 3 карти. Тогава ще имаме 3 двойки карти. Ако всички са еднакви няма проблем. Ако имаме 2 различни карти, тогава според случая n = 2, не можем да намерим равенствво с 1 или 2 карти.

Защо?

[peyo]

Сега може би да пробваме да измислим някаква индукция

Ако имаме 3 карти. Тогава ще имаме 3 двойки карти. Ако всички са еднакви няма проблем. Ако имаме 2 различни карти, тогава според случая n = 2, не можем да намерим равенство с 1 или 2 карти.

Защо?

Мдааааааа. Това ми твърдение не е очевидно. Аз съм го доказал вярно само за случая когато от дясно са същите карти или една карта като от ляво а не всички възможни карти. Ще трябва да помисля повече...

[pal702004]

Мдааааааа. Това ми твърдение не е очевидно.

То е не просто "неочевидно", то е невярно. За 3 карти има например решение
$1,c,c$, където $c=\sqrt 5+2$ е другия положителен корен на уравнението

$\dfrac{c+1}{2}=\sqrt[3]{c\cdot c \cdot 1}$

и само това, че е ирационално разваля нещата. Всъщност тук най-важното условие е, че числата трябва да са естествени (може и рационални, условието не се променя при умножение/деление на едно и също число). Неприятна задача, свързана с теория на числата.

[georgi111]

Много красива задачка по теория на числата ... Ще докажем, че решенията са всички естествени числа > 1. Ето и моето решение:
Нека числата , написани върху картите са [tex]a_1 \dots a_n[/tex].Без ограничение можем да считаме, че [tex]gcd(a_1,...,a_n)=1[/tex](ако не е 1 разглеждаме числата [tex]\frac{a_1}{d},...,\frac{a_n}{d}[/tex], където [tex]d=gcd(a_1,...,a_n)[/tex] и задачата не се променя). Също без ограничение можем да считаме, че [tex]a_1 \le a_2 \le... \le a_n[/tex].
Случай 1) [tex]a_n=1[/tex] - ясно , защото тогава всички числа са равни на 1.
Случай 2) [tex]a_n \ge 2[/tex]
Нека [tex]p[/tex] е прост делител на [tex]a_n[/tex]. От [tex]gcd(a_1,...,a_n)=1[/tex] следва, че съществуват числа измежду дадените, които не се делят на [tex]p[/tex] и нека да вземем най-големия такъв индекс [tex]k[/tex]. От условието имаме:[tex]a_k \le \frac{a_n + a_k}{2}=\sqrt[t]{a_{b_1} \dots a_{b_t}}[/tex]. Ясно е , че [tex]p[/tex] не дели [tex]\frac{a_n+a_k}{2}[/tex], в частност имаме [tex]a_n \ne a_k[/tex]. Оттози факт и последното равенство имаме, че никое от числата [tex]a_{b_1} \dots a_{b_t}[/tex] не се дели на [tex]p[/tex] и трябва да е изпълнено [tex]a_k \ge a_{b_i}[/tex](от максималността на [tex]k[/tex]),[tex]i=1, \dots t[/tex]. Тогава от последното равенство имаме, че [tex]a_{b_1}=a_{b_2}=\dots=a_{b_t}=a_k=a_n[/tex].Последното равенството от веригата е противоречие с [tex]a_k \ne a_n[/tex]. Тогава [tex]a_1=\dots a_n=1[/tex].

[georgi111]

Случая с рационалните числа, изписани върху картите не е по-различен, понеже умножаваме числата с произведението на знаменателите и сме в случая с целите числа. За реални числа, изписани върху картите и [tex]n \ge 3[/tex], може да напишем на някоя карта [tex]x[/tex] и на [tex]n-1[/tex] карти [tex]y[/tex], където [tex]\frac{x+y}{2}=\sqrt[3]{xy^2}[/tex] (такива числа съществуват, например [tex]y=1, x=\sqrt{5}-2[/tex]). Сега видях, че последното за реалните числа pal702004 вече го е посочил уравнението с единствената разлика, че при мен [tex]y=1[/tex], при него [tex]x=1[/tex]

[georgi111]

Иначе и моето мнение за задачите - 1ва - лесна, 2ра - изглежда лесна, но лесно може да забиеш, 3та - много добра и не трудна, 4та - много добра и лесна, 5та - най-красивата в темата , 6та - много трудна. Някак си липсват трудна геометрия, функционално уравнение, трудна теория на числата, но това е изцяло лично мнение ... Но истината е, че и с 0 на зад.6 пак преспокойно си се прави златен медал...

[drago]

Много красива задачка по теория на числата ...

Да, хубава е и е по теория на числата. Щото имаше спорове дали не е комбинаторика. Ама то като няма малката теорема на Ферма и модулна аритметика и някои хора вече го пишат комбинаторика. Всички решения, които съм виждал използват една и съща идея. Твоето решение сякаш най-добре формализира нещата, абсолютно същото е и решението на Evan Chen във AoPS. Ако имаш желание, може да погледнеш и моя коментар в блога ми, ако ти се чете бла-бла (няма нищо съществено).

... Някак си липсват трудна геометрия, функционално уравнение, трудна теория на числата, но това е изцяло лично мнение ...

Ами ето, тази задача е теория на числата и от българския отбор са я решили само трима, т.е. половината. Т.е. не бих казал, че е лесна! Но да, не използва някакви дълбоки факти по ТЧ, само неща, които се учат в 6-ти клас.
3-та задача не бих казал, че не е трудна, като гледам резултатите на отбора ни - само 1 решение. Ами даже отбора на САЩ има успех 50% по нея. 6-та може да я коментирам по-късно.

[grav]

Много красива задачка по теория на числата ...

Да, хубава е и е по теория на числата. Щото имаше спорове дали не е комбинаторика.

А какво е определението за теория на числата?

[georgi111]

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

[georgi111]

О и аз не бих казал, че е лесна ... Доста и то добри състезатели може да подхлъзне ...

[mariq.Ivanova@abv.bg]

Какво мислите за резултатите от международната олимпиада от тази година?

https://www.imo-official.org/year_count ... ?year=2020

Не е лесна..

[Гост]

Какво мислите за резултатите от международната олимпиада от тази година?

https://www.imo-official.org/year_count ... ?year=2020

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

[Гост]

IMO 2020, задача 4.
Според мен отговорът е [tex]n^{2}[/tex]-n+1.

[Гост]

IMO 2020, задача 4.
Да продължа по темата.
В условието на задачата е писано:
"Всички k въжени линии на A тръгват от k различни начални станции и стигат
до k различни крайни станции, при това въжена линия, която тръгва от по-­висока начална станция
стига до по-­висока крайна станция."
Да наречем горните условия за прекарване на въжени линии в задачата правило 1.
Максималният брой линии, които могат да се прекарат при спазване на правило 1 е [tex]n^{2}[/tex]-1. (Макар че за последното в задачата не се пита.) Минималната стойност за k е е [tex]n^{2}[/tex]-n+1.
При това може да се обобщи. Анализът на ситуацията показва, че отговорите и на двата въпроса (за максималния брой линии, които могат да се прекарат и за минимална стойност на числото k) остават същите дори когато правилата за прекарване на въжени линии в определено отношение се либерализират.
Разглеждаме твърдението (да го наречем правило 2): "За всеки две станции, ако са свързани от една компания, то съществува единствен начин за придвижване от едната до другата с въжените линии само на тази компания, при положение, че пътуващият ползва всяка въжена линия не повече от веднъж." Тук под "начин за придвижване" се разбира последователността от въжени линии, по които се придвижва пътуващият. Ясно е, че ако системата от въжени линии на една компания отговаря на правило 1, тя отговаря и на правило 2. Обратното не е вярно, т.е. може да се посочат примери на система от въжени линии, отговаряща на правило 2, но неотговаряща на правило 1.
И така. Ако системите от въжени линии на компаниите А и В отговарят на правило 2, то отговорите и на двата въпроса (за максималния брой линии, които могат да се прекарат и за минимална стойност на числото k) остават същите.
Може да изкажем формулировки в термини на графи.
Свързан връх в граф ще наречем такъв връх, който има прилежащо поне едно ребро. Два върха ще наречем едносвързани, ако има поне един път, свързващ двата върха. Област на едносвързаност в граф ще наречем всяко подмножество на множеството на всички върхове на графа, за което за всеки връх x е вярно, че ако областта съдържа върха x, то областта съдържа и всеки друг връх y, който е едносвързан с върха x. Затворен път ще наричаме цикъл. Граф, несъдържащ нито един цикъл, ще наричаме ацикличен граф. Граф, съдържащ краен брой върхове, ще наричаме краен граф.
----------------------------------------------------------------
Твърдение 1. В краен ацикличен граф броят на свързани върхове е равен на сбора от броя на ребрата и броя на областите на едносвързаност.
----------------------------------------------------------------
Твърдение 2. Дадено е цяло число n, n≥2. Най-голямата стойност на цялото число k, за която съществува ацикличен граф с n върха и k ребра, е n-1.
----------------------------------------------------------------
Твърдение 3. Дадени са цели числа n, x и y, n≥1. Минималната стойност на израза x+y-x*y при всвъзможните стойности на x и y, когато 1≤x≤n и 1≤y≤n, се достига при x=n и y=n.
----------------------------------------------------------------
Твърдение 4. Дадени са цели числа n и k, n≥2, k≥1 и множество S от [tex]n^{2}[/tex] на брой точки. A и B са два ациклични графа с върхове от S, всеки с по k ребра. Тогава минималната стойност на k, за която е вярно, че съществува поне една двойка различни точки от S, които са едносвързани и в A и в B, е [tex]n^{2}[/tex]-n+1.
----------------------------------------------------------------
Твърдение 4 дава решение на задачата.

[Гост]

IMO 2020, задача2.
Намерих тук някакво решение:

https://m.youtube.com/watch?v=z8h8nnao9VI

[drago]

Що се мъчиш да търсиш в youtube? Отиди тук:
https://artofproblemsolving.com/community/c1306546_2020imo
кликай вдясно, дето пише "view topic", и се наслаждавай на решения колкото искаш. Малко трябва да се внимава все пак, щото и грешки стават. И това в препратката към youtube го има. Всъщност то май е най-логичното.

[drago]

Това е, което написах по IMO 2020, зад. 4. Същността на творението накратко е: защо просто, като може сложно.

[drago]

IMO 2020, задача 6.

[georgi111]

IMO 2020, задача 6.

Уникално ... Евала Драго само това мога да кажа ... Дано повече състезатели видят твоето решение и поне го прочетат с разбиране ...