Вроде бы простая комбинаторика

[mr.tumkan]

1) Докажите, что в подразделении из 18 спартанцев всегда есть либо четверо спартанцев, которые знают друг друга, либо четверо попарно незнакомых спартанцев.

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

А как строить промежуточные случаи? (кажется, что их очень много) Их нужно по пальцам перебирать?

2) Можно ли натуральные числа от 1 до 20 разбить на 10 пар так, чтобы разность чисел в первой паре была равна 1, во второй паре 2, ... , в 10 паре 10?

Попытка 1:

$$20-19, 18-16, 17-14, 15-11, 14-9, 13-7, 12-6, 10 (proval)$$

Попытка 2:

$$20-10 (10),19-11 (8), 18-12(6), 17-13 (4), 16-14(2), 15-6 (9), 9-2(7), 8-3(5), 7-4(3), 1 (gluk)$$

Как тут быть, подскажите, плиз?

[Утундрий]

Копайте в сторону теории Рамсея.

[AV_77]

mr.tumkan в сообщении #895912 писал(а):

2)

Обратите внимание на сумму всех заданных чисел и на сумму разностей пар. Там не сложно получится.

[mr.tumkan]

Сумма всех числе 210, а сумма разностей пар 55. То есть в 4 раза отличается. А как это может помочь?

[ИСН]

Никак. Да и не в 4. Смотрите. Сумма разностей пар - это фактически сумма десяти чисел минус сумма других десяти. А сумма чисел - это что?

-- менее минуты назад --

Теперь отдельный, умеренно интересный вопрос - для каких чисел (вместо 20) это всё-таки возможно.

[mr.tumkan]

ИСН в сообщении #896039 писал(а):

Никак. Да и не в 4. Смотрите. Сумма разностей пар - это фактически сумма десяти чисел минус сумма других десяти. А сумма чисел - это что?

-- менее минуты назад --

Теперь отдельный, умеренно интересный вопрос - для каких чисел (вместо 20) это всё-таки возможно.

В смысле -- сумма чисел -- это что? Сумма, это сумма. Не очень понятен вопрос.

А это понял "Сумма разностей пар - это фактически сумма десяти чисел минус сумма других десяти."

[ИСН]

Я плохо сформулировал. Это умышленно, потому что если сформулировать то же самое хорошо, вопрос начинает звучать дебильно. Итак, ещё раз: сумма разностей пар - это фактически сумма десяти чисел (скажем, A) минус сумма других десяти (B). ОК. Теперь как выразить сумму всех чисел через эти A и B?

[mr.tumkan]

ИСН в сообщении #896095 писал(а):

Я плохо сформулировал. Это умышленно, потому что если сформулировать то же самое хорошо, вопрос начинает звучать дебильно. Итак, ещё раз: сумма разностей пар - это фактически сумма десяти чисел (скажем, A) минус сумма других десяти (B). ОК. Теперь как выразить сумму всех чисел через эти A и B?

$A-B=55; A+B=210$

$2A=265$

То есть $A$ не является натуральным числом, получаем противоречие, значит нельзя так разбить. Верно?

-- 14.08.2014, 13:45 --

А как подступиться к первой задаче?

[ИСН]

Выходит, так.
С первой сложно. Докажите сначала то же самое, только вместо чисел 18 и 4 возьмите соответстевнно 6 и 3.

[mr.tumkan]

ИСН в сообщении #896108 писал(а):

Выходит, так.
С первой сложно. Докажите сначала то же самое, только вместо чисел 18 и 4 возьмите соответстевнно 6 и 3.

Спасибо! То есть нужно пронумеровать всех спартанцев?

[ИСН]

Это как хотите.

[mr.tumkan]

ИСН в сообщении #896116 писал(а):

Это как хотите.

Пока что не ясно -- с чего начать. Если разбить на 9 пар, то разве будет толк? Всевозможных пар же будет гораздо больше.... $C_{18}^2=153$ пар будет, да? Или нужно разбивать на группы по 4 человека $C_{18}^4=3060$?

[ИСН]

18 - это очень много, совершенно за пределами воображения. Докажите сначала для других чисел, поменьше.

[mr.tumkan]

А сколько лучше для начала взять человек? А может ли так быть, что Вася знает Петю, но Петя не знает Васю?

Получается, если хотя бы один человек, не знает никого, то он попарно ни с кем не знаком, а значит найдутся 4 попарно незнакомых человека, то есть получается скорее знакомства могут быть односторонними?

[ИСН]

Я не буду Вам больше говорить, сколько человек лучше взять для начала. Вообще бросьте эту задачу. У Вашего ружья согнулся ствол, и оно стреляет за угол. Ничего понять нельзя.