Warning: Spoiler![ Click to expand ][ Click to hide ]
Левая часть инвариантна относительно оператора (x,y,z) => (x+1,y+1,z+1)
Все дополнительные слагаемые сокращаются
(x+y)(x-y)+(y+z)(y-z)+(z+x)(z-x)+(x-y)+(y-z)+(z-x)=0
А значит надо найти хотя бы одно решение (x,y,z) и вуаля
Насчет спортивности согласен, а доказательством является. Там уравнение прямой с решениями приведено. Но на самом деле, все просто:
xy(x-y)+yz(y-z)+zx(z-x)=xy(x-y)-z(x2-y2)+z2(x-y)=(x-y)[xy-z(x+y)+z2]=
(x-y)(x-z)(y-z)
Мы же ищем целочисленные решения (x-y)(x-z)(y-z)=2*3. Поэтому их надо искать в виде решения системы вида x-y=2, x-z=3,тогда y-z=1. Получается уравнение одной из прямых в решении Wolfram.
Вчера для разминки рассмотрел на компьютере два алгоритма.
1. Сначала попробовал положить каждый билет в ящик с минимально возможным номером. Получилось плохо: задействуются все 100 ящиков. То же с максимально возможным номером.
2. Затем попробовал сначала задействовать все ящики, в номерах которых цифры совпадают (00, 11, ..., 99), все равно ведь они будут задействованы в любом случае. И только потом, если не получилось, перейти к алгоритму 1. Получилось немного лучше: 90 ящиков.
Да нет, задачу предлагается решить без компьютера. Это я поразминался на компьютере. Компьютер может проверить и проконтролировать ваше решение. Пишут, что это довольно старая задача, докомпьютерная, так сказать.
Я сделал выборку в файл таблицы "# БИЛЕТ принадлежит к # ЯЩИКА". Алгоритм раскидал все билеты в 100 ящиков.
все ящики, в номерах которых цифры совпадают (00, 11, ..., 99), все равно ведь они будут задействованы в любом случае.
Чем ближе номер ящика к сотне, тем меньше в нём окажется билетов.
Оказалось, что начиная с 900 и до 999 по возрастанию, каждый билет кладётся в номер ящика согласно двум последним цифрам билета.
И здесь ничего не поделаешь.
Оказалось, что начиная с 900 и до 999 по возрастанию, каждый билет кладётся в номер ящика согласно двум последним цифрам билета.
И здесь ничего не поделаешь.
Оптимальное количество ящиков находим по формуле треугольных чисел
N*(N+1)/2, где N=10 (число цифр в позиции и 100 ящиков по условию).
Удаляем все номера ящиков у которых цифра десятков больше цифры единиц.
И что получится?
Попробовал улучшить рекорд методом Монте Карло. Раньше я просматривал ящики последовательно (чтобы поместить туда очередной билет), начиная с ящиков 00, ..., 99, а теперь решил просматривать их в случайном порядке, но в одном и том же для всех билетов и тоже начиная с ящиков 00, ..., 99. Рассмотрев 100 000 случайных порядков (за 25 минут на моем компьютере), я установил новый рекорд: 72 ящика (вместо 90).
Решающая идея! Никто ведь не подскажет, до всего приходится самому доходить.
Пусть порядок просмотра ящиков остается случайным, но как только ящик окажется (впервые) занятым, мы сделаем его первым по порядку, все равно ведь теперь его не сэкономишь. Это сразу сокращает время работы компьютера вдвое и дает - после просмотра 100 000 случайных порядков - новый рекорд: 51 ящик! Думаю, если просмотреть миллион случайных порядков, то получится и неулучшаемый, окончательный результат. Но нужны 2 часа работы компьютера.
Нет, не совсем так. По факту я делал ящик первым по порядку всякий раз, когда он пополнялся, а не только, когда от занимался впервые. Если же делать, как было указано, то дольше получается.