Задачите от МОМ 2019

[inveidar]

2019_bul.pdf

(183.34 KiB) 128 пъти

Резултатите на нашите (и на огромна част от участниците!) се заформят около нулата на 3-та и 6-та задача, но остава да им се провери четвърта. Иначе временно сме на 17-то място.

[ptj]

На 3-та според мен трудността е да се докаже, че в графа не съществува пълен подграф, чиито върхове нямат свързаност извън него.
Когато това е изпълнено:
Цитираната операция намаля с едно ребрата на графа. Докато има връх свързан с два съседа я прилагаме. Когато няма сме изпълнили искането за край на задачата.

[peyo]

Да пробваме да решим задача 1:

Да намерим всички функции които
f:Z→Z,
f(2a) + 2f(b) =f(f(a+b)).

Да потърсим решение от вида:

f(x) = m*x + n

m*2*a + n + 2*m*b + 2*n = m*( m*(a+b)) + n) + n

2*m*a + n + 2*m*b + 2*n = m*m*a + m*m*b + m*n + n

Приравнявайки коефицентите пред a, b и константите, получаваме 3 уравнения:
2*m = m*m
2*m = m*m
2*n + n = m*n + n

Решаваме и:
m = 2

2*n + n = 2*n + n

Или n може да е всяко число.

и така нашата търсена функция е:

f(x) = 2*x + n

Но друга функция която очевидно също ни върши работа е:

f(x) = 0

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

[peyo]

Май ми хрумна лесно решение на задача 4:

Търсим естествени k,n :
$k! = (2^n−1)(2^n−2)(2^n−4)···(2^n−2^{n−1})$

Като проверяваме малките числа виждаме, че решения са:
1, 1
3, 2

И крайното решение е, че това са всички решения защото дясната страна може да съдържа числото 3 само когато n=2 , тогава 3 е първия член на поредицата. Няма други случаи на n да може да се образува 3. Първия член ще по-голям от 3, а останалите ще са четни.

[pal702004]

И какво им пречи на четните числа да се делят на 3?
Всъщност 4-та задача наистина не е много трудна...но не и чак толкова лесна. Като се изнесе макс. степен на 2 в дясната страна се получава

$2^{\frac{n(n-1)}{2}}(2^1-1)(2^2-1)\cdots(2^n-1)$

Тук вече има много продълнения - да се сравни степента на 2 със тази на 3, например. Моето решение е със сравнение на степента на 31 със степента на 29 (всяко 5-то число се дели на 31 и едва всяко 28-мо на 29, така че в дясната част, при $n\ge 5$, в разложението на прости 31 ще е в по-голяма степен, отколкото 29, което при факториал е невъзможно.

[peyo]

И какво им пречи на четните числа да се делят на 3?...

Да, моя подход не работи. Разлики от степени на двойката спокойно може да се делят на 3.

[georgi111]

Първо нека да запишем израза вдясно като: $(2^n-1)(2^n-2)\cdots(2^n-2^{n-1})$ = $\frac{(2^n -1)!}{(2^{n-1}-1)!}$.(Защо е така ?)
Малко теория :
1)$v_a(k)$ = най-високата степен на $a$, която дели $k$.
2)Формула (наготово ще я ползваме): $v_p(n!)=\sum_{i=0}^{\infty}[\frac {n} {p^i}]$ (Ясно е, че сумата ще има събираеми от едно място нататък само нули, нали ?)
3) https://en.wikipedia.org/wiki/Legendre%27s_formula - формулата $v_p(n!)=\frac {n - s_p(n)} {p-1}$ ($s_p(n)$ - записа на числото $n$ в $p$-ична бройна система)

Първо презаписваме : $k!=(2^n-1)(2^n-2)\cdots(2^n-2^{n-1})=\frac{(2^n -1)!}{(2^{n-1}-1)!}$.(Предполагам е ясно защо) Също, $v_2(\frac{(2^n -1)!}{(2^{n-1}-1)!})=v_2(2^n-1)!-v_2(2^{n-1}-1)!$. Но това е равно на: $2^n-1-n-(2^{n-1}-1-n+1)=2^n-2^{n-1}-1$.(Защо ? ползваме 3) от теорията) От друга страна имаме(от даденото условие като извадим общите множители 2-ки пред скобите - $k!=(2^n -1)2^1(2^{n-1}-1)(2^n-3)\cdots2^{n-1}(2-1))$): $v_2(k!)=\frac{n^2-n}{2}$.Така достигаме до: $2^{n}-2^{n-1}-1 = \frac{n^2-n}{2} \implies 2^n-2=n^2-n$, откъдето следва : $2^n-n^2+n=2$. Но това може да се случи за $n=1,2,3$. Когато $n=1, k!=1 \implies (n,k)=(1,1)$ е решение. Когато $n=2, k!=3 \cdot 2 \implies (n,k)=(2,3)$ е друго решение. Когато $n=3, k!=7 \cdot 6 \cdot 5 \cdot 4$ - противоречие. Следователно решенията са: $\boxed{(n,k)=(1,1),(2,3)}$

[drago]

Трудно ми е да разбера защо нашите състезатели (оък и останалите) имат почти пълен брой точки на 5-та задача, а на 3-та само двама имат по 1т. (другите - 0). Не казвам, че 5-та е по-трудна, това е събективно, но пък 3-та не е в никакъв случай извънземна.
Едното обяснение е в номерата - 3-та и 6-та се сичтат за най-трудни (и обикновено е така) и се оставят за най-накрая. Така че може просто време да е нямало.
Другото обяснение е, че в индивидуалната им подготовката не са наблегнали на теория на графите. Като гледам тенденциите, такива задачи ще има и в бъдеще. А това ме радва, защото тази тематика има интерсени комбинаторни идеи.
Ако някой, който се състезава, чете тук (което леко ме съмнява) му препоръчвам книгата на R. Diestel, "Graph Theory". Има я в нета. Първите две глави са задължителни, третата може да се прегледа на идейно ниво. Това е достатъчно като теория за олимпиадно ниво. Не само да се четат теоремите, а да се разберат самите доказателства (и упражненията след тях), защото там са идеите, които се прилагат в нестандартни ситуации, където не можещ да използваш наготово теорема. А в IMO ги подбират такива по дизайн. Никой няма да ви даде задача, която следва веднага от някоя теорема, не и на IMO. Абе иска се бачкане. Разликата да сме в първата двайска и в първата десетка е бачкането. Талантливи ученици има.

Много ме радва също, че се отстъпва от глупавите и тежки функционални у-ния, където основната идея (ако има такава) е да се заместват разни стойности и да се разглеждат безумно количество случаи. Първата задача го потвърждава - едно лесно функц. уравнение, да се разпишат участниците, в което даже има идея.

Та по 3-та задача, @ptj: дяволът е в детайлите. Ето тук е моето прдложение: https://artofproblemsolving.com/communi ... 7p12809310

[georgi111]

Лично мнение - 5тата е доста по-лесна от 3тата в такъв смисъл, че доста по-лесно може да се избута рекурентна релация за б), докато 3тата еми нямаш ли познания по теория на графите си жив умрял

[georgi111]

Аз лично съм много учуден защо имаме пълна нула отборно на 6тата ... Не е много трудна - при добър чертеж става "със СОУ"(подобия само) ...

[drago]

5-та е много хубава и приятна задача. Може да се направи и директно (условие б ) , без рекурсия/индукция. Ако се интерпретира специфично става доста лесна. Ще пусна една такава интерпретация, като имам време. Но не бих казал, че е лесна.
За 3-та - ами виж, на практика никакви познания по теория на графите не се искат. Виж всички решения. Но е много полезно човек да е преживявал такива неща. Точно това написах.

[peyo]

Май измислих смешно много просто решение на задача 4:

Първо ще дефинираме и докажем следната теорема:

Теорема 1:
Две функции всяка от които е навсякъде влъбната или навсякъде изпъкнала се пресичат само в 0, 1, 2 или във всички точки.

Доказателство:

Доказателството е графично и изброява всички интересни възможни случаи, а останалите са симетрични на тези:

variantinakrivinifunkcii.png (7.63 KiB) Прегледано 901 пъти

И сега задача 4:

Търсим естествени k,n :
$k! = (2^n−1)(2^n−2)(2^n−4)···(2^n−2^{n−1})$

Двете навсякъде изпъкнали (мисля е очевидно) функции са:
$f(k) = k!$
$g(n) = (2^n−1)(2^n−2)(2^n−4)···(2^n−2^{n−1})$

И тъй като вече намерихме 2 бързи решения при малките числа:
1, 1
3, 2

Според теорема 1 това са всички решения.

[pal702004]

Теорема 1:
Две функции всяка от които е навсякъде влъбната или навсякъде изпъкнала се пресичат само в 0, 1, 2 или във всички точки.

Това и за функции от еднакви аргументи не е вярно

А за различни фунции от различни аргументи $f(k),g(n)$ направо безсмислено.

[peyo]

Теорема 1:
Две функции всяка от които е навсякъде влъбната или навсякъде изпъкнала се пресичат само в 0, 1, 2 или във всички точки.

Това и за функции от еднакви аргументи не е вярно

А за различни фунции от различни аргументи $f(k),g(n)$ направо безсмислено.

Ok. Коригирам по следния начин:

Теорема 1:
Две монотонни функции всяка от които е навсякъде вдлъбната или навсякъде изпъкнала се пресичат само в 0, 1, 2 или във всички точки.

Така мисля, че е по-добре.

За различните параметри май си прав, като се замисля повече, не виждам как може да се сведе по пресичане на криви. Ще трябва да помисля повече.

[georgi111]

@peyo виж моето решение на зад. 4 - обосновано "със СОУ" алгебра и малко теория на числата ... На зад. 3 Драго е дал линк към арт-а с изключително добра идея (и на практика решение), Задачи 2, 6 са много много добър избор ... Скоро като имам време ще пусна решение на зад.6 "със СОУ"

[drago]

Първо нека да запишем израза вдясно като: $(2^n-1)(2^n-2)\cdots(2^n-2^{n-1})$ = $\frac{(2^n -1)!}{(2^{n-1}-1)!}$.(Защо е така ?)...

Георги, не си прочел добре условието.

Problem 4. Find all pairs $(k, n)$ of positive integers such that
$$k! = (2^n − 1)(2^n − 2)(2^n − 4)\cdots (2^n − 2^{n−1}).$$

В дясната страна имаш $n$ множителя, а не $2^{n-1}$. Така че си решил друга задача.
Но така или иначе, подходът е подобен.

[georgi111]

@drago правилната зад, 4 съм решил ... Имаш съмнения защо израза е равен на частното на двата факториела ? За упражнение може да си го докажеш по индукция като не вярваш, че е така

[drago]

Хм, като не можеш да го вденеш по-абстрактно, ще ти демонстрирам конкретно за $n=4$.
$$(2^4-1)(2^4-2^1)(2^4-2^2)(2^4-2^3)= 15\cdot 14\cdot 12\cdot 8 \neq \frac{15!}{7!}=15\cdot 14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8$$
Сега ясно ли е?

[georgi111]

Пффф верно не е така - прекалено хубаво излезна, за да е истина

[georgi111]

Вече решението на 4-та зад :
$v_2((2^n-1)(2^n-2)(2^n-2^2)\cdots(2^n-2^{n-1}))=1+2+\cdots+(n-1)=\dfrac{n(n-1)}{2},$От Legendre formula, $v_2(k!)=\sum\limits_{j=1}^{+\infty}[\dfrac{k}{2^j}]<k(\dfrac{1}{2}+\dfrac{1}{4}+\cdots)=k$.

Ясно е , че $3 \mid 2^x-1 \Leftrightarrow 2|x$,тогава: $v_3(4^x-1)=1+v_3(x)$. Забелязваме,че (Тогава $v_3(дясна-страна)$=
$\sum_{i = 1}^{\lfloor \frac{n}{2} \rfloor} 1 + v_3(2i)$):
$v_3((2^n-1)(2^{n-1}-1)\cdots(2-1)) =[\frac{n}{2}]+v_3([\frac{n}{2}]!) <[\frac{n}{2}]+[\frac{n}{2}](\dfrac{1}{3}+\dfrac{1}{9}+\cdots) =\dfrac{3}{2}[\frac{n}{2}]$.$v_3(k!) \geq [\dfrac{k}{3}]>\dfrac{k}{3}-1.$Тогава, $\dfrac{k}{3}-1<\dfrac{3}{2}[\frac{n}{2}] \leq \dfrac{3}{4}n$, имаме и $\dfrac{n(n-1)}{2}<k$: $\dfrac{n(n-1)}{2}<k<\dfrac{9}{4}n+3$, $2n^2-11n-12<0$, $1 \leq n<6$, нататък с непосредствена проверка.

[drago]

Моето предложение за задача 4. https://artofproblemsolving.com/communi ... 2p12825010

а също и за 5-та(The Bank of Bath): https://artofproblemsolving.com/communi ... 2p12836613

[drago]

Интерсна история има зад. 5. Как е била създадена, разказано от нейния автор тук...
Написах малко коментари... лека-полека. Още не е довърщено, но можи на някой да му е интересно.