ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64451
Темы:    [ Математическая логика (прочее) ]
[ Объединение, пересечение и разность множеств ]
[ Шахматные доски и шахматные фигуры ]
Сложность: 4-
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Петя нарисовал на плоскости квадрат, разделил на 64 одинаковых квадратика и раскрасил их в шахматном порядке в чёрный и белый цвета. После этого он загадал точку, находящуюся строго внутри одного из этих квадратиков. Вася может начертить на плоскости любую замкнутую ломаную без самопересечений и получить ответ на вопрос, находится ли загаданная точка строго внутри ломаной или нет. За какое наименьшее количество таких вопросов Вася может узнать, какого цвета загаданная точка – белого или чёрного?


Решение

  Чтобы определить цвет точки за один вопрос, нужна ломаная, по отношению к которой все квадратики одного цвета лежат внутри, а другого – снаружи. Но тогда она содержит все отрезки, разделяющие соседние квадратики, и значит, самопересекается.
  Покажем, как отгадать цвет точки за два вопроса. Построим ломаную, внутрь которой попадут все нечётные горизонтали квадрата и только они (см. рис.).

  Тогда первым вопросом мы узнаем чётность горизонтали, содержащей загаданную точку. Аналогичным вторым вопросом узнаем чётность содержащей её вертикали. Осталось заметить, что цвет квадратика определяется чётностью суммы его "координат".


Ответ

За два вопроса.

Замечания

  1. Можно ограничиться ломаными, не выходящими за пределы Петиного квадрата. Первую ломаную проведём, как на рис. слева.

                   

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

  2. Баллы: 8-9 кл. – 7, 10-11 кл. – 5.

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

олимпиада
Название Турнир городов
Турнир
Номер 35
Дата 2013/2014
вариант
Вариант осенний тур, сложный вариант, 8-9 класс
задача
Номер 4
олимпиада
Название Турнир городов
Турнир
Номер 35
Дата 2013/2014
вариант
Вариант осенний тур, сложный вариант, 10-11 класс
задача
Номер 1

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .