задача про минимальные блоки

[2old]

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

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

[ИСН]

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

[2old]

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

-- 08.10.2015, 19:43 --

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

[provincialka]

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

-- 08.10.2015, 19:06 --

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

[iancaple]

2old в сообщении #1060546 писал(а):

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

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

[2old]

iancaple
И значит блоков 6. Это понятно, спасибо. Я не понимаю как указать на противоречие, если взять что государства участвуют не менее, чем в 2х блоках.

[iancaple]

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