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

[PWT]

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

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

Спасибо! Все стало очень понятно, просто очень емко и по сути! Очень хорошая идея, я кажется до конца разобрался (по-крайней мере надеюсь на это).
Пусть $t$ -- нечетное количество послов, а остальные -- четные. Тогда в (1) сумма четырех четных чисел есть 365, что невозможно, противоречие.

Пусть только $t$ -- четное количество послов, а остальные -- нечетные. Тогда в (1) будет сумма двух четных и двух нечетных чисел, что должно стать четным числом, а там 365, значит опять невозможно, значит противоречие. Из этого следует, что есть еще диагональные знакомства, что и доказывает исходное утверждение в задаче. Верно ли это?

-- 05.10.2017, 13:16 --

(но утверждение "После того как истекли 365 дней, оказалось, что из соседних государств не осталось тех, кто был бы не был знаком." все равно мне кажется неосуществимым, как бы не интерпретировалось условие или я не прав?)

[EUgeneUS]

PWT
(1) можно преобразовать так:
$xy+yz+zt+tx=(x+z)(y+t)=kl=365$
Тогда второе уравнение:
$k+l=77$

Тогда сразу очевидно, что количество послов - это сумма множителей количества дней, для 365 два варианта:
$1+365 = 366$ (но одно государство никого не посылает).
$5+73 = 78$
Другие количества послов, в том числе 77, не подходят.

[atlakatl]

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

но утверждение "После того как истекли 365 дней, оказалось, что из соседних государств не осталось тех, кто был бы не был знаком." все равно мне кажется неосуществимым, как бы не интерпретировалось условие

Почему "но"? Вы в своём последнем комменте только что доказали, что это невозможно. Расскажите его преподавателю и сдадите зачёт.

[PWT]

Ааа, не я кажется понял.

Здесь учитывались только знакоства по кругу. $xy+yz+zt+tx=365$ и $x+y+z+t=77$

Если были диагональные знакомства, то $xy+yz+zt+tx<365$ и $x+y+z+t=77$. Но в таком случае должен быть пример, который доказывает это, но какой? Или я что-то не так понял?

[atlakatl]

PWT
Если разрешить и диагональные знакомства, то логично требовать знакомства всех-со-всеми. Т.е. в (1) добавляются ещё два произведения. Запишем его в виде $f=t(x+y+z)+x(y+z)+yz$. Так как $72 \cdot 5 = 360$, а $71 \cdot 6 = 426$, то имеем только два набора $f(72,2,2,1)=368$, $f(72,3,1,1)=367$, примерно попадающих в район $365$. Т.е. опять не повезло.

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

Если были диагональные знакомства, то $xy+yz+zt+tx=365$ и $x+y+z+t=77$. Но в таком случае должен быть пример, который доказывает это, но какой?

Я исправил "<" на "=". Как видим, нет.

[PWT]

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

PWT
Если разрешить и диагональные знакомства, то логично требовать знакомства всех-со-всеми. Т.е. в (1) добавляются ещё два произведения. Запишем его в виде $f=t(x+y+z)+x(y+z)+yz$. Так как $72 \cdot 5 = 360$, а $71 \cdot 6 = 426$, то имеем только два набора $f(72,2,2,1)=368$, $f(72,3,1,1)=367$, примерно попадающих в район $365$. Т.е. опять не повезло.

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

Если были диагональные знакомства, то $xy+yz+zt+tx=365$ и $x+y+z+t=77$. Но в таком случае должен быть пример, который доказывает это, но какой?

Я исправил "<" на "=". Как видим, нет.

Но не обязательно же всевозможные диагональные знакомства включать в уравнение?))

По условию задачи имеется ввиду, что хотя бы одно диагональное знакомство должно иметь место и это нужно доказать. Мы по сути сделали оценку, доказав, что если условия задачи выполнимы, то диагональные знакомства неминуемы, ввиду того, что придем к противоречию, организовав только знакомства по кругу. Из этого следует, что осталось только привести пример, в котором будет хотя бы одно диагональное знакомство.

Опираясь на это

Цитата:

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

и это

Цитата:

можно преобразовать так:
$xy+yz+zt+tx=(x+z)(y+t)=kl=365$
Тогда второе уравнение:
$k+l=77$

В тех же обозначениях я добавлю диагональные знакомства. Пусть их было, например, $m$.

$kl+m=365$, $k+l=77$.

Нужно решить эту систему в натуральных числах. Выразим отсюда $m=365-kl=365-k(77-k)$, тогда $m=365-77k+k^2$

Дальше закончилось мое терпение, я воспользовался вольфрамом, которые подтвердил, что знакомств по кругу организовать не получится даже при наличии диагональных знакомств.http://www.wolframalpha.com/input/?i=solve+k*l%2Bm%3D365+and+k%2Bl%3D77+and+k>0,m>0,l>0+in+integers

А понял я это из того, что разница между $k$ и $l$ слишком велика (минимум 67), а при таком раскладе не получится организвать знакомства по кругу.

Правильно ли я понимаю, что условия задачи противоречивы?

[atlakatl]

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

Но не обязательно же всевозможные диагональные знакомства включать в уравнение?))

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

при таком раскладе не получится организовать знакомства по кругу.

Если допускать "не всевозможные диагональные", то возможных сочетаний тысячи.
Самый легкосчитаемый случай: $f(72,3,1,1)=360+4 ( - мы реализовали все круговые знакомства, но оставили незнакомыми двух послов из $x$ и посла $z$.

[PWT]

Хорошо, спасибо за помощь! Ваш пример понял. Можно ли считать, что я понял задачу?)))