Перед экстрасенсом лежит колода из 36 карт рубашкой вверх (4 масти, по 9 карт каждой масти). Он называет масть верхней карты, после чего карту открывают и показывают ему. После этого экстрасенс называет масть следующей карты и т. д. Задача экстрасенса – угадать масть как можно большее число раз. Рубашки карт несимметричны, и экстрасенс видит, в каком из двух положений лежит верхняя карта. Помощник экстрасенса знает порядок карт в колоде, не может менять его, но может расположить рубашку каждой из карт тем или иным образом. Мог ли экстрасенс так договориться с помощником, когда тот ещё не знал порядок карт, чтобы обеспечить угадывание масти не менее чем
  a) 19 карт;
  б) 23 карт?

   Решение

Страница: 1 [Всего задач: 1]      

В некоторых клетках квадратной таблицы n×n стоят звёздочки. Известно, что если вычеркнуть любой набор строк (только не все), то найдётся столбец ровно с одной невычеркнутой звёздочкой. (В частности, если строки совсем не вычёркивать, то столбец ровно с одной звёздочкой существует.) Доказать, что если вычеркнуть любой набор столбцов (только не все), то найдётся строка ровно с одной невычеркнутой звёздочкой.

Прислать комментарий

Решение

Страница: 1 [Всего задач: 1]