2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Фишки на шахматной доске
Сообщение16.03.2011, 23:22 


13/03/11

10
На шахматной доске расставлены n фишек так, что в любом квадрате 3*3 находятся ровно 3 фишки.
a) При каком наибольшем n это возможно?
b) При каком наименьшем n это возможно?

 Профиль  
                  
 
 
Сообщение17.03.2011, 02:27 


24/01/11
207
a)
1. Рассмотрим доску 9х9, её можно разбить на непересекающиеся квадраты 3х3, в каждом из которых, по условию, 3 фишки, выходит, максимум для 9х9 — 27
2. Теперь рассмотрим любую валидную доску 8х8, дорисуем справа и снизу рядок, чтобы превратить её в 9х9 (не обязательно валидную).
В каждом квадрате теперь <=3 фишки, т.е. если вдруг n>27, в каком-нибудь квадрате точно больше 3х фишек и получилось противоречие. Выходит, ответ <= 27.
27 достигается, например, так:
Изображение

 Профиль  
                  
 
 
Сообщение17.03.2011, 03:35 


24/01/11
207
б) Первая оценка, которую мы получим — 12, т.к. квадрат 8х8 содержит квадрат 6х6, который можно поделить на квадраты 3х3.

Изображение
Пусть этот квадрат 6х6 будет самым левым верхним (синий).
Рассмотрим теперь квадрат, отмеченный зелёным. Ясно, что от синего он получит не более, чем 1 фишку (она будет на синезелёной клетке), а значит нужны как минимум ещё две. Теперь оценка — 14

Изображение
Рассмотрим теперь 2 квадрата, отмеченных красным (в пересечниях с синим — фиолетовым)
Ясно, что в случае 14-ти фишек все фиолетовые должны быть покрыты. Однако тогда жёлтый квадрат должен покрыть фишками как квадрат между желтым и одним красным, так и между желтым и другим красным, что в сумме — 5 фишек, а можно лишь 3. Значит, в сумме красные квадратики синей областью можно покрыть не более чем на 4 фишки, но т.к. нужно 6 (3+3), придётся добавить ещё две в красную область, не принадлежащую синей. Растянули оценку до 16.

А вот и рисунок для 16:
Изображение

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group