2014 dxdy logo

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

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




 
 задача про минимальные блоки
Сообщение08.10.2015, 17:26 
На планете Марс 100 государств объединены в блоки, в каждом из которых не больше 50 государств. Известно, что любые два государства состоят вместе хотя бы в одном блоке. Найдите минимально возможное число блоков.

Составим таблицу, где строки занумерованы как государства, а столбцы как блоки, максимальный номер столбца $s$. В каждом блоке участвует не более 50 государств, значит всего галочек будет $\leq 50s$, но это не очень полезно. Теперь из фразы "любые два государства состоят вместе хотя бы в одном блоке" надо что-нибудь понять, но я не могу сообразить что. Блоков точно больше $2$.

 
 
 
 Re: задача про минимальные блоки
Сообщение08.10.2015, 18:25 
Аватара пользователя
Сколотим все государства в четыре кучи по 25 штук и назовём их 1, 2, 3, 4.
Теперь вот блоки: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4).
По-моему, этого хватит. Теперь надо подумать, почему нельзя меньше.

 
 
 
 Re: задача про минимальные блоки
Сообщение08.10.2015, 18:26 
Пусть каждое государство участвует в одном блоке. Тогда они все участвуют в одном и том же, в блоке больше 50 государств, противоречие.
Пусть каждое государство участвует в не менее чем двух блоках, тогда число "галочек" $\geq 200$ и $\leq 50s$. Т.к. мы ищем минимальное число блоках, то каждое государство участвует ровно в двух блоках, число блоков при этом $4$. Тут кажется и настанет проблема, когда мы попытаемся заполнить таблицу так, чтобы любые два государства были в одном блоке, то один из столбцов будет пустым, а значит в какому-то из блоков окажется больше $50$ государств. Но четко сформулировать этот принцип я не могу

-- 08.10.2015, 19:43 --

ИСН
Вот, т.е. надо доказать, что каждое государство должно участвовать в трех блоках. Меньше не получается из-за "любые два государства состоят вместе хотя бы в одном блоке" -- блоки начинают переполнятся за $50$. Но почему так происходит я не понимаю

 
 
 
 Re: задача про минимальные блоки
Сообщение08.10.2015, 18:57 
Аватара пользователя
Пока не решала задачу, но, может, стоит попробовать еще такое описание: считать не галочки (государство-блок) а ребра (государство-государство). Изобразим каждое государство в виде точки на плоскости. Каждые два государства, входящие в блок номер $i$ соединим ребром $i$-го цвета. Можно посчитать ребра по цветам и всего...

-- 08.10.2015, 19:06 --

(оценка получается, но, похоже, недостаточно точная :-( )

 
 
 
 Re: задача про минимальные блоки
Сообщение08.10.2015, 19:26 
Аватара пользователя
2old в сообщении #1060546 писал(а):
ИСН
Вот, т.е. надо доказать, что каждое государство должно участвовать в трех блоках. Меньше не получается из-за "любые два государства состоят вместе хотя бы в одном блоке" -- блоки начинают переполнятся за $50$. Но почему так происходит я не понимаю

Вы были в одной фразе от решения. Но я обойдусь тремя , и то не своими. Каждый блок дает каждому своему участнику конфетку. Значит, всего дано не менее $3\times 100$ конфеток. Но каждый блок дал не более 50 конфеток.

 
 
 
 Re: задача про минимальные блоки
Сообщение08.10.2015, 19:57 
iancaple
И значит блоков 6. Это понятно, спасибо. Я не понимаю как указать на противоречие, если взять что государства участвуют не менее, чем в 2х блоках.

 
 
 
 Re: задача про минимальные блоки
Сообщение08.10.2015, 20:48 
Аватара пользователя
Я не мог в это поверить. Государство А участвует в блоке, которому присвоим номер 1, в нем, кроме А, еще не более 49. Значит, есть блок номер 2, в котором А и еще какие-то не более 49. Возьмем В, не перечисленное здесь, оно вместе с А входит в блок номер 3

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


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