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


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

16 кар­то­чек с це­лы­ми чис­ла­ми от 1 до 16 раз­ло­же­ны ли­це­вой сто­ро­ной вниз в виде таб­ли­цы 4 × 4 так, что кар­точ­ки, на ко­то­рых за­пи­са­ны со­сед­ние числа, лежат рядом (со­при­ка­са­ют­ся по сто­ро­не). Какое наи­мень­шее число кар­то­чек нужно од­но­вре­мен­но пе­ре­вер­нуть, чтобы на­вер­ня­ка опре­де­лить ме­сто­по­ло­же­ние всех чисел (как бы ни были раз­ло­же­ны кар­точ­ки)?

Спрятать решение

Ре­ше­ние.

Оцен­ка. За­ну­ме­ру­ем клет­ки, как по­ка­за­но на ри­сун­ке 1. За­ме­тим, что одна из кле­ток с но­ме­ром 1 долж­на быть от­кры­та, иначе крас­ный и синий спо­со­бы за­пол­не­ния таб­ли­цы на ри­сун­ке 2 были бы не­раз­ли­чи­мы. Одна из кле­ток с но­ме­ром 2 также долж­на быть от­кры­та, иначе крас­ный и синий спо­со­бы за­пол­не­ния таб­ли­цы на ри­сун­ке 3 были бы не­раз­ли­чи­мы.

Ана­ло­гич­но, долж­ны быть от­кры­ты хотя бы по одной из кле­ток с но­ме­ра­ми 3, 4, 5, 6, 7, 8, то есть долж­но быть от­кры­то не менее 8 кар­то­чек.

Рис. 1.

Рис. 2.

Рис. 3.

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

За­ме­тим, что если в угол ведёт ребро, то мы вос­ста­но­вим число в нём. Если же в уг­ло­вую клет­ку не ведёт ребро, то в ней стоит край­нее число, то есть 1 или 16, а так как мы знаем чётность числа в каж­дой клет­ке, то в этом слу­чае мы тоже вос­ста­но­вим число в углу. Итак, числа в углах за­ве­до­мо вос­ста­нов­ле­ны.

Если среди уг­ло­вых есть клет­ки, для ко­то­рых не все со­сед­ние числа от­кры­ты, из каж­до­го та­ко­го угла про­ведём ребро в не­пе­ревёрну­тую со­сед­нюю клет­ку и од­но­знач­но вос­ста­но­вим число в ней. Оста­лись не вос­ста­нов­лен­ны­ми разве что числа в не­уг­ло­вых клет­ках пер­во­го и четвёртого столб­ца. Рас­смот­рим любую из них. В неё не ведёт ребро ни из со­сед­не­го столб­ца, ни из угла, а тогда в этой клет­ке точно край­нее число (так как у неё оста­лась мак­си­мум одна клет­ка с со­сед­ним чис­лом). По чётно­сти легко узнаём, какое край­нее число там долж­но сто­ять.

Таким об­ра­зом, мы вос­ста­но­ви­ли числа во всех клет­ках.

 

Ответ: во­семь кар­то­чек.