На прошедшем IZhO по математике дали необычные задачи, многие из которых затроллили большинство участников. P2 решалась трюком, многие не справились. Я тоже не справился, во время тура действовал слишком технично, не помогло. Мое приближение было попыткой зажать искомое число между заданными, что является более сильным утверждением (но как оказалось эквивалентным), которое я смог доказать после тура.
Условие.
Пусть $$$n$$$ — положительное целое число, для которого существуют положительные целые $$$a$$$ и $$$b$$$, такие что
Доказать, что существует положительное целое число $$$c$$$, для которого
Официальное решение
Обозначим
Складывая, имеем
откуда
Мое решение
Идея.
- ищем такие $$$x_c$$$, которые зажаты между $$$a\sqrt{10}$$$ и $$$b\sqrt{11}$$$;
- доказываем, что такое $$$c$$$ существует и единственно;
- показываем, что для остальных $$$c$$$ равенство целых частей невозможно.
Обозначим
Шаг 1. Условие зажатости
Если
то немедленно следует
Это эквивалентно неравенству
Вычислим разности:
Так как знаменатель положителен, получаем эквивалентное условие
Следовательно,
где
Шаг 2. Единственность целого решения
Длина отрезка равна
Из условий имеем
поэтому
Значит, в $$$[L, R]$$$ может лежать не более одного целого числа.
При этом
откуда
Следовательно,
— единственное целое решение, необходимые и достаточные условия проверили.
Шаг 3. Отсутствие других решений
Из неравенства $$$b\sqrt{11} - a\sqrt{10} \lt 1$$$ следует
Тогда
Следовательно,
то есть
Аналогично,
Значит, других значений $$$c$$$ не существует.
Автокомментарий: текст был обновлен пользователем PokemonMaster (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been translated by PokemonMaster (original revision, translated revision, compare)
In the official solution in a couple of places γ and 1/γ are swapped but overall everything is clear
I don't think it's a troll solution as much as exploiting and rewarding certain problem solving techniques. You should always get a feel for a problem by trying to substitute some values that seem like they'd simplify expressions nicely. E.g. substitute $$$c=a$$$, $$$c=b$$$, just to see if the result is too large or too slow — ideally, if you can find a tight interval for the target $$$c$$$, it'll tell you what sort of properties $$$c$$$ could have.
Well, it turns out $$$c=a$$$ and $$$c=b$$$ give something like $$$n/2$$$. What if you add them? Looks like $$$a+b$$$, $$$a+b-1$$$, $$$a+b+1$$$ or something could give the right result.
It's similar to programming competitions. You don't know what you should be proving so you see what happens in some obvious cases and what they say about non-obvious ones. Guessing a construction that often works in construction problems hints that you're moving in the right direction.
You re right. If this was div2A problem it can be solved in a couple of minutes But in the olympiad setting this problem trolled many participants with strong technique and good level of cp. Official solution looks much simpler than how the problem actually felt for most contestants, whether they solved it or not. The solve rate was quite low.
You're reasoning backwards about skill. Having "strong technique and good level of cp" is determined by (average) results, it isn't something you declare and expect results to follow. If someone needs to know the complexity of the solution to solve the problem, that contestant has a lot to learn since that's a strong hint that allows pruning thinking approaches early on.
What you describe sounds more like learning hammers early on and seeing everything as a nail, a common case since there's not all that much time for students to develop enough skills to reach an international olympiad. In programming it often manifests as fitting problems to solutions rather than finding solutions to problems. It shows why fundamentals are necessary.
Totally agree. My coach said about the fundamentals after the contest.