2014 dxdy logo

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

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




 
 Задача про клетки и крестики
Сообщение13.12.2015, 11:44 
В клетках квадрата $7\times 7$ стоит 100 крестиков. Нашлись 3 горизонтали, в клетках которых в сумме содержится не менее 70 крестиков и три аналогичные вертикали. Докажите, что либо в какой-то клетке нет ни одного крестика, либо найдется клетка, в которой стоит не менее 7 крестиков (либо и то, и другое).

У меня такая идея. Попробуем доказать от противного. Пусть это не так. Мне кажется, что утверждение, которое необходимо опровергнуть можно сформулировать так:
Если в каждой клетке стоит хотя бы один крестик, то можно построить квадрат таким образом, чтобы в каждой клетке было не более 6 крестиков (при этом квадрат $7\times 7$ и условия про 3 горизонтали и вертикали выполняются).
Значит, возьмем те три диагонали и те три вертикали. Их объединение содержит 140-9=131 крестиков, при этом объединение состоит из $21\cdot 2-9=33$ клеток. Значит клеток 33, а крестиков 131. Из этого по принципу Дирихле найдется хотя бы одна клетка с 4 крестиками. Но до 6 тут далеко.
Правильно ли я начал доказывать?

 
 
 
 Re: Задача про клетки и крестики
Сообщение13.12.2015, 12:39 
Аватара пользователя
mr.tumkan2015 в сообщении #1081814 писал(а):
Их объединение содержит 140-9=131 крестиков
Нет ли здесь противоречия?

mr.tumkan2015 в сообщении #1081814 писал(а):
Правильно ли я начал доказывать?
Ваша мысль блуждает в нужном направлении. Приложите ещё немного усилий и не забывайте, что в квадрате есть ещё клетки, кроме выделенных линий.

 
 
 
 Re: Задача про клетки и крестики
Сообщение13.12.2015, 14:31 
grizzly в сообщении #1081821 писал(а):
mr.tumkan2015 в сообщении #1081814 писал(а):
Их объединение содержит 140-9=131 крестиков
Нет ли здесь противоречия?

Действительно, есть. Спасибо!

-- 13.12.2015, 14:32 --

grizzly в сообщении #1081821 писал(а):
Ваша мысль блуждает в нужном направлении. Приложите ещё немного усилий и не забывайте, что в квадрате есть ещё клетки, кроме выделенных линий.

Сформулирую более аккуратно утверждение, которое необходимо опровергнуть можно сформулировать так:
В каждой клетке стоит хотя бы один крестик и в каждой клетке не более 6 крестиков (при этом квадрат $7\times 7$ и условия про 3 горизонтали и вертикали выполняются).

А новых идей про доказательство не появилось, к сожалению.

 
 
 
 Re: Задача про клетки и крестики
Сообщение13.12.2015, 16:32 
Аватара пользователя
mr.tumkan2015 в сообщении #1081835 писал(а):
А новых идей про доказательство не появилось, к сожалению.

А новых идей уже и не нужно. Осталось аккуратно пересчитать клетки и кроликов.

 
 
 
 Re: Задача про клетки и крестики
Сообщение17.12.2015, 16:41 
Спасибо, разобрался с задачей!

 
 
 
 Re: Задача про клетки и крестики
Сообщение17.12.2015, 17:18 
Аватара пользователя
mr.tumkan2015 в сообщении #1082989 писал(а):
Спасибо, разобрался с задачей!
Всегда пожалуйста :-)
Я сомневался, а теперь рад, что сильных подсказок не понадобилось. Но Вам не повредило бы рассказать своё решение. Хотя бы чтоб закрыть тему.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group