Текст задания

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

Пример: если у Маши есть пазл размер 2×2, то наименьшее количество деталей, которые надо вынуть, равно трем.

Решение

Построим решение от обратного: сначала найдем вариант, при котором будет вытащено максимальное количество кусочков и из них не будет создана пара, а потом добавить к нему 1 кусочек, это и будет искомое число.

То есть нужно разбить исходное множество на максимальное количество подмножеств, не касающихся друг друга. Очевидно, что это шахматный порядок. Что-то типа:

Здесь показаны только три строчки, а по условию задачи – их 23. В четных строках (2, 4, 6 … 22) по 9 закрашенных ячеек, а в нечетных – по 10.

Всего четных строк будет 11, а нечетных – 12. Тогда, максимальное число непересекающихся множеств по одному кусочку пазла составит 11*9+12*10=99+230=329 штук.

Если мы добавим 1 кусочек, то он к какому-нибудь кусочку обязательно подойдет. То есть из коробки необходимо достать минимум 330 кусочков, чтобы гарантировано получилась хотя бы одна пара.

Если достать 329, то может получиться шахматный порядок.

Ответ: 330