Задача 21979

Темы:    [ Принцип Дирихле (конечное число точек, прямых и т. д.) ] [ Таблицы и турниры (прочее) ] [ Раскраски ] [ Мощность множества. Взаимно-однозначные отображения ] [ Оценка + пример ]

Сложность: 3 Классы: 7,8

Условие

а) Какое наибольшее число полей на доске 8×8 можно закрасить в чёрный цвет так, чтобы в каждом уголке из трёх полей было по крайней мере одно незакрашенное поле?
б) Какое наименьшее число полей на доске 8×8 можно закрасить в чёрный цвет так, чтобы в каждом уголке из трёх полей было по крайней мере одно чёрное поле?

Решение

  а) Пример. 32 поля закрасить можно (например, в полоску).
  Оценка. Разобъём доску на 16 квадратиков 2×2. В каждом из них можно закрасить не более двух полей (иначе получится чёрный уголок). Поэтому всего можно закрасить не более 32 полей.
  б) Задача сводится к а) заменой чёрных полей на незакрашенные и наоборот.

Ответ

а)-б) 32 поля.

Источники и прецеденты использования

Кружок
Название	ВМШ 57 школы
класс
Класс	7
год
Место проведения	57 школа
Год	2005/06
занятие
Номер	3
Название	Принцип Дирихле
Тема	Принцип Дирихле
задача
Номер	5
книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	5
Название	Принцип Дирихле
Тема	Принцип Дирихле
задача
Номер	010