сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

У вол­шеб­ных часов, кроме обыч­ной пары стре­лок, есть вто­рая пара, ко­то­рая в каж­дый мо­мент вре­ме­ни сим­мет­рич­на пер­вой от­но­си­тель­но вер­ти­каль­ной оси. По фо­то­гра­фии часов не­воз­мож­но опре­де­лить, какие стрел­ки на­сто­я­щие. Кроме этого, по вол­шеб­ным часам (как и по обыч­ным) нель­зя от­ли­чить утро от ве­че­ра. По­это­му одной и той же фо­то­гра­фии часов могут со­от­вет­ство­вать не­сколь­ко раз­ных времён (на­при­мер, 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-ча­со­вой про­ме­жу­ток, в ко­то­рый сде­ла­на толь­ко одна фо­то­гра­фия (та самая, ко­то­рая сов­па­да­ет): на­при­мер, если она сде­ла­на в мо­мент 6 плюс t_1=12 минус t_2, то на про­ме­жут­ке 6 минус t_1 до 12 плюс t_2 дру­гих фо­то­гра­фий нет. Тогда можно уме­стить все фо­то­гра­фии в пе­ри­од 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.

Спрятать критерии
Критерии проверки:

Пол­ное ре­ше­ние каж­дой за­да­чи оце­ни­ва­ет­ся в 7 бал­лов. За не­ко­то­рые про­дви­же­ния могут ста­вить­ся баллы, а за не­до­стат­ки — сни­мать­ся.

Част­ные кри­те­рии: По од­но­му баллу за до­ка­за­тель­ство воз­мож­но­стей 3 и 100. За до­ка­за­тель­ство того, что мень­ше 3 быть не может, даётся 2 балла.