У волшебных часов, кроме обычной пары стрелок, есть вторая пара, которая в каждый момент времени симметрична первой относительно вертикальной оси. По фотографии часов невозможно определить, какие стрелки настоящие. Кроме этого, по волшебным часам (как и по обычным) нельзя отличить утро от вечера. Поэтому одной и той же фотографии часов могут соответствовать несколько разных времён (например, 1:15, 10:45 и 22:45 на фотографии выглядят так, как показано справа).
Робот делает несколько фотографий часов в течение одних суток (от 0:00 до 24:00). Он запоминает порядок, в котором сделаны фотографии, но не время их выполнения. Иногда по такой серии снимков можно определить, во сколько именно сделаны некоторые из них; такие снимки будем называть «определёнными». Если же для снимка (даже с учётом остальных снимков серии) есть несколько моментов, когда он мог быть сделан, то он неопределённый.
Например, в серии снимков, показанных справа, снимок №2 определённый (он сделан в 9:00), а вот снимок №4 неопределённый (он мог быть сделан как в 16:00, так и в 20:00).
Пусть есть серия из 100 фотографий, сделанных в течение одних суток, никакие две из которых не выглядят одинаково, и ни одна из них не сделана в 0:00, 6:00, 12:00, 18:00 или 24:00. Какое минимальное количество неопределённых фотографий может быть среди них?
(А. А. Теслер)
Рассмотрим следующие фотографии: A — та, которая сделана ближе всего к 6:00; B — сделанная ближе всего к 12:00; C — сделанная ближе всего к 18:00.
Если все эти фотографии различны, то каждую из них можно «симметрично отразить» относительно соответствующего момента времени (например, если первая фотография сделана в 5:50, то она же могла бы быть сделана и в 6:10, что не влияет на корректность последовательности времён). Значит, имеем как минимум три неопределённых фотографии.
Если же какие-то две из них совпадают, то существует 12-часовой промежуток, в который сделана только одна фотография (та самая, которая совпадает): например, если она сделана в момент то на промежутке до других фотографий нет. Тогда можно уместить все фотографии в период 0:00 до 12:00, а можно с 12:00 до 24:00, то есть все фотографии неопределенные.
Схематично эти варианты показаны на графиках. По горизонтали — реальное время создания фотографий; по вертикали — минимальное время, при котором часы выглядят как на фото; красным выделены снимки A, B, C, а стрелками показана их «неопределённость».
Докажем, что в случае, когда не все фотографии неопределённые, неопределённых фотографий всего три. Действительно, три выбранных фотографии (A, B, C) различны. Тогда для каждой из них есть лишь два возможных времени: если у какой-то из них (например, A) хотя бы три возможных момента времени, то между крайними такими моментами не меньше 12 часов, что позволяет уместить все кадры в 12-часовой промежуток (а значит, все снимки неопределённые). Заметим, что все фотографии, сделанные до снимка A, обязательно сделаны до 6:00 (так как остальные допустимые для них времена позже, чем оба допустимых времени для фото A). Аналогично устанавливаем, что фото, идущие между снимками A и B, сделаны между 6 и 12 часами (иначе они либо сняты раньше, чем обе возможности для A, либо позже, чем обе возможности для B), фото между B и C — между 12 и 18 часами, и наконец, фото, идущие после C, сняты позже 18 часов. Итак, все остальные снимки оказались определёнными.
Ответ: 3 или 100.