Ниже — аккуратно оформленная версия для блога Codeforces: Markdown + LaTeX, живой человеческий стиль, структура сохранена, правки минимальные (в основном — адаптация под формат CF и читабельность).
IZhO P2: как одна строка «затроллила» почти всех
На прошедшей IZhO по математике дали очень необычный сет задач. Несколько из них оказались настоящими ловушками — формально простые, но концептуально нестандартные. Особенно P2: она решалась одним коротким трюком, но именно поэтому почти всех и «съела».
Я тоже не справился во время тура. Действовал слишком технично, пытался доказывать более сильное утверждение (зажимал выражение между двумя другими), что в итоге оказалось эквивалентным… но понял это уже после тура.
Ниже — полное изложение задачи, официального решения и моего альтернативного подхода.
Условие
Пусть ( n ) — положительное целое число, для которого существуют положительные целые ( a ) и ( b ), такие что
[ \lfloor a\sqrt{10} \rfloor = n = \lfloor b\sqrt{11} \rfloor. ]
Доказать, что существует положительное целое число ( c ), для которого
[ n = \left\lfloor c,(11\sqrt{10} — 10\sqrt{11}) \right\rfloor. ]
Официальное решение (тот самый «трюк»)
Обозначим: [ \alpha = \sqrt{10}, \quad \beta = \sqrt{11}, \quad \gamma = 11\sqrt{10} — 10\sqrt{11}. ]
Заметим ключевое: [ \gamma = \frac{\sqrt{110}}{\sqrt{10} + \sqrt{11}} = \frac{1}{\alpha} + \frac{1}{\beta}. ]
Из условий: [ n \le a\alpha < n+1, \qquad n \le b\beta < n+1 ] получаем: [ \frac{a}{n+1} < \frac{1}{\alpha} \le \frac{a}{n}, \qquad \frac{b}{n+1} < \frac{1}{\beta} \le \frac{b}{n}. ]
Складываем: [ \frac{a+b}{n+1} < \gamma \le \frac{a+b}{n}. ]
Умножаем на ( n(n+1) ): [ n \le (a+b)\gamma < n+1. ]
Отсюда сразу: [ \boxed{ n = \left\lfloor (a+b)(11\sqrt{10} — 10\sqrt{11}) \right\rfloor } ]
Одна строка, одна идея, одно наблюдение. Именно это и делало задачу такой коварной.
Альтернативное решение (как я думал во время тура)
Здесь я не угадываю ( c ), а иду более «силовым» путём.
Идея
- Ищем такие ( x_c ), которые зажаты между ( a\sqrt{10} ) и ( b\sqrt{11} );
- Доказываем, что такое ( c ) существует и единственно;
- Показываем, что для остальных ( c ) равенство целых частей невозможно.
Шаг 0. Исходные неравенства
Из условия: [ n \le a\sqrt{10} < n+1, \qquad n \le b\sqrt{11} < n+1. \tag{1} ]
Определим: [ x_c := c(11\sqrt{10} — 10\sqrt{11}) = \frac{c\sqrt{110}}{\sqrt{10} + \sqrt{11}}. ]
Шаг 1. Условие зажатости
Если [ \min(a\sqrt{10},, b\sqrt{11}) \le x_c \le \max(a\sqrt{10},, b\sqrt{11}), ] то из (1) сразу следует: [ \lfloor x_c \rfloor = n. ]
Это эквивалентно: [ (x_c — a\sqrt{10})(x_c — b\sqrt{11}) \le 0. ]
Считаем разности: [ x_c — a\sqrt{10} = \frac{(c-a)\sqrt{110} — 10a}{\sqrt{10}+\sqrt{11}}, ] [ x_c — b\sqrt{11} = \frac{(c-b)\sqrt{110} — 11b}{\sqrt{10}+\sqrt{11}}. ]
Так как знаменатель положителен, получаем: [ (c — a — a\sqrt{10/11})(c — b — b\sqrt{11/10}) \le 0. ]
Значит, [ c \in [L, R], ] где [ L = \min!\left(a + a\sqrt{\tfrac{10}{11}},; b + b\sqrt{\tfrac{11}{10}}\right), \quad R = \max!\left(a + a\sqrt{\tfrac{10}{11}},; b + b\sqrt{\tfrac{11}{10}}\right). ]
Шаг 2. Единственность целого решения
Длина отрезка: [ R — L = \left(\frac{1}{\sqrt{10}} + \frac{1}{\sqrt{11}}\right) \lvert a\sqrt{10} — b\sqrt{11} \rvert. ]
Из (1): [ \lvert a\sqrt{10} — b\sqrt{11} \rvert < 1, ] поэтому: [ R — L < 1. ]
Следовательно, в отрезке может быть не более одного целого числа.
При этом: [
{L, R}
\left{ a+b — \frac{b\sqrt{11}-a\sqrt{10}}{\sqrt{11}},; a+b — \frac{a\sqrt{10}-b\sqrt{11}}{\sqrt{10}} \right}, ] и отсюда: [ a+b \in [L, R]. ]
Значит, [ \boxed{c = a+b} ] — единственный возможный вариант.
Шаг 3. Почему других решений нет
Проверяем ( c = a+b \pm 1 ).
Из ( b\sqrt{11} — a\sqrt{10} < 1 ) следует: [ b\sqrt{110} — 10a < \sqrt{10}. ]
Отсюда: [ (a+b)\frac{\sqrt{110}}{\sqrt{10}+\sqrt{11}} — a\sqrt{10} < \frac{\sqrt{10}}{\sqrt{10}+\sqrt{11}}. ]
Следовательно: [ \left\lfloor x_{a+b-1} \right\rfloor \le n-1, \qquad \left\lfloor x_{a+b+1} \right\rfloor \ge n+1. ]
Других вариантов нет.
Итог
[ \boxed{ n = \left\lfloor (a+b)(11\sqrt{10} — 10\sqrt{11}) \right\rfloor } ]
