Question

Маше подарили большую коробку с пазлом. Но Маша абсолютно точно не хочет вынимать все-все-все кусочки из коробки и все их переворачивать. Она решила не глядя вынуть наименьшее количество кусочков, при котором гарантированно найдется хотя бы одна пара кусочков, которая состыкуется правильно. Размер Машиного пазла 13 × 31. В качестве ответа укажите одно целое число — искомое количество кусочков. Пример: если у Маши есть пазл размер 2×2, то наименьшее количество деталей, которые надо вынуть, равно трем.

Answer 1

Максимальное кол-во кусочков, при котором они в шахматном порядке могут расположиться,  не совпав друг с другом, 202. Маша должна взять на 1 больше- 203. Вертикальных 13 рядов, горизонтальных 31. Вертикальный ряд можно заполнить "шахматным порядком" или 6 или 7 закрашенными клетками. Мы выберем 7, что бы получилось максимальное количество "закрашенных клеток" (кусочков пазла). Следующий ряд будет уже 6( что бы получились "шахматы"). (6+7)*15+7

Answer 2

Маше подарили большую коробку с пазлом размером 13 × 31. Она хочет вынуть наименьшее количество кусочков, при котором гарантированно найдется хотя бы одна пара кусочков, которая состыкуется правильно.

Чтобы решить эту задачу, мы можем использовать принцип Дирихле, который утверждает, что если n + 1 объектов распределить по n контейнерам, то хотя бы в одном контейнере будет находиться не менее двух объектов.

В данном случае, каждый кусочек пазла может быть рассмотрен как объект, а каждая горизонтальная или вертикальная линия может быть рассмотрена как контейнер. Мы хотим найти наименьшее количество кусочков, при котором гарантированно найдется хотя бы одна пара кусочков, которая состыкуется правильно.

Чтобы найти это количество, мы можем рассмотреть самую длинную сторону пазла (31) и разделить ее пополам. Это даст нам 15,5, но так как мы ищем целое число, мы округлим его вверх до 16. Таким образом, наименьшее количество кусочков, которые нужно вынуть, равно 16.

Ответ: 16.

Источник: Russian | PDF - Notes. 1) This list was created using public/free subtitles, from opensubtitles in particular. The order is based on the number of occurrences of...