Задача на знакомства

[PWT]

Здравствуйте! Помогите, пожалуйста, разобраться в задаче.

В далекой галактике есть планета Иноландия, на которой располагается некоторые 4 государства. Представители каждого государства отправляют своих послов в другие государства. Всего послов на этой планете -- ровно 77, среди которых нет знакомых изначально. Государства располагаются в вершинах квадрата. Целый год (земной год, 365 дней), каждый день знакомились какие-то два представителя разных государств. После того как истекли 365 дней, оказалось, что из соседних государств не осталось тех, кто был бы не был знаком. Докажите, что есть знакомые послы из противоположных государств.

Моя попытка:
Допустим обратное – все знакомства происходили только между послами из соседних государств. Этого добиться проще, если послы сконцентрированы в 3х подряд идущих государствах, например $A,B,C$,так что возможности знакомиться согласно нашему допущению максимальны. В четвертом государстве живет 1 посол, в первом – $y$, во 2-м $x$, а в 3-м $76-x-y$. Тогда количество возможных знакомств $\dfrac{xy+ x(76-x-y)}{2}\ne38x - x^2$ . Максимум этой функции достигается при х = 19 и равен $19\cdot 19 = 361$. Но в году 365 дней, вариантов знакомств не хватает, так что мы пришли к противоречию.

Можно ли считать это решением, правильно ли?

[svv]

PWT в сообщении #1252744 писал(а):

Этого добиться проще, если послы сконцентрированы в 3х подряд идущих государствах, например $A,B,C$,так что возможности знакомиться согласно нашему допущению максимальны.

Тут надо описать рассуждение более чётко.

[PWT]

svv в сообщении #1252761 писал(а):

PWT в сообщении #1252744 писал(а):

Этого добиться проще, если послы сконцентрированы в 3х подряд идущих государствах, например $A,B,C$,так что возможности знакомиться согласно нашему допущению максимальны.

Тут надо описать рассуждение более чётко.

Спасибо за ответ. А что значит более четко?

[svv]

Надо пояснить, почему достаточно рассмотреть случай, когда одно из государств прислало лишь одного посла.
Почему из того, что в этом случае обязательно будут «диагональные» знакомства, следует, что они будут и в общем случае.

[EUgeneUS]

Насколько понял условие, попытка ТС вообще не засчитывается.

Нумеруем государства по кругу.
В государство 1 остальные три государства посылают своих послов. В государстве 1 послы 2 и 4 знакомятся с послами 3, но не друг с другом.
То же самое происходит в остальных трех государствах.
Итого у нас 12 переменных, а не четыре, как у ТС. Путем простых преобразований получаем систему из двух уравнений на восемь переменных. Надо доказать, что она не решается в целых числах.

[PWT]

То есть это задача вообще не решается?

[atlakatl]

PWT
Если доказать, что решений системы в целых числах нет, то мы задачу решили.

[atlakatl]

$x, y, z, t$ - количества послов в странах по кругу.
Тогда $xy+yz+zt+tx=365$ (1)
Т.к. $x+y+z+t=77$, то нечётных количеств послов будет одно или три.
Рассмотрите (1) на предмет чётности для каждого случая.

[EUgeneUS]

atlakatl
Если трактовать условия так, что послы каждого государства весь год не сидят на месте (в государстве, куда послали), а ездят по планете, то да:
а) переменных - четыре.
б) и получаются два этих уравнения.

Но далее лучше не рассматривать на предмет четности\нечетности. А выразить $t$ из второго и подставить в первое. Все сведется к квадратному уравнению, у которого нет решений в целых числах.

[atlakatl]

EUgeneUS
А чем лучше? С чётностью все выкладки в уме, никаких бумажек не надо.

[EUgeneUS]

atlakatl
1. Про выкладки в уме для данного случая - согласен. Пытался анализировать четность для более сложного варианта условия, когда послы никуда не ездят. Ничего хорошего не смог получить. Для простого случая даже не пытался.
2. А если послов 76? (нельзя). Или 78? (можно). А если количество дней 361, сколько послов было? (362). Брутфорс лучше тем, что сразу дает ответ для любого количества послов и любого количества дней.

[atlakatl]

EUgeneUS в сообщении #1252956 писал(а):

если количество дней 361, сколько послов было? (362)

Так и не понял, что за задачу с переездами Вы решаете.
Я считаю, что послы одного государства изначально знают друг друга, и их отношения в расчёт не принимаем.

[EUgeneUS]

atlakatl

Все зависит, как трактовать вот эту фразу:

PWT в сообщении #1252744 писал(а):

Представители каждого государства отправляют своих послов в другие государства.

Первый вариант: государство А посылает посла в государство Б, и этот посол сидит там безвыездно, знакомится с послами государств В и Г в этом же государстве (в Б). И у него нет возможности познакомиться с послами любого государства, сидящих в государствах А, В и Г.

Второй вариант: государство А посылает посла в вояж, также поступают и все остальные государства. У всех послов есть возможность встретиться друг с другом. Или, что тоже самое, все послы встречаются на какой-то конференции в местной ООН, длящейся год.

atlakatl в сообщении #1252966 писал(а):

Я считаю, что послы одного государства изначально знают друг друга, и их отношения в расчёт не принимаем.

Не важно, знают они друг друга или нет, их отношения в расчет не принимаем, так как (жирный шрифт мой):

PWT в сообщении #1252744 писал(а):

каждый день знакомились какие-то два представителя разных государств.

[atlakatl]

EUgeneUS в сообщении #1252956 писал(а):

А если количество дней 361, сколько послов было? (362)

Я уточнил именно в связи с этой задачей. Никак не могу сформулировать условия, чтобы получить такой ответ.

[EUgeneUS]

atlakatl

1. Пусть, для определенности, послы собираются в ООН.
2. Каждый день происходит ровно одно знакомство между послами разных государств.
3. Через $N$ дней сложилась такая ситуация, что а) если государства соседние, то все послы перезнакомились, б) если государства "диагональные", то нет ни одного знакомства.
4. Вопрос: сколько всего послов было?

UPD: (удалил, что-то не идут выкладки в уме )