Помогите пожалуйста решить задачу!

Среди 9 мушкетеров некоторые поссорились и вызвали друг друга на дуэль.Докажите, что если среди них нет трех, которые должны драться друг с другом, то среди мушкетеров найдутся 4 друзей.

Дарья, вы тоже "Пифагор" решаете?

1) Почему бы не назвать тему "Мушкетёры" или "Мушкетёры поссорились"?

2) Что означают две загадочные английские буквы "r" и "n", с которых
начинается условие задачи. Я перечитываю несколько раз условие, но смысла
этих букв уловить никак не могу, а прежде, чем решать задачу, желательно
условие понять полностью.

3) Нигде в условии не было сказано, что кто-то из мушкетёров с кем-то
дружил. Как же можно доказывать, что "найдутся 4 друзей"?

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

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

R(3,4)=9.

Я вспомнил идею доказательства этого факта из кружка моего сына за восьмой, кажется, класс, но в двух словах этого не рассказать. С другой стороны, GOOGLE вываливает по этой теме ссылки десятками. Посмотрите что-нибудь из них, а потом, если что будет непонятно, я продемонстрирую "каркас" решения.

Подскажите, пожалуйста!

Среди 9 мушкетеров некоторые поссорились и вызвали друг друга на дуэль. Докажите, что если среди низ нет трех которые должны драться друг с другом, то среди мушкетеров найдутся четверо друзей.
я искал в гугле не нашел помогите плиз

Поищите в GOOGLе ссылки на "числа Рамсея". Я ведь об этом писал.

А я как раз нашла информацию про эти числа. Там как раз расказывают про арифметические прогресси и используют цифру 9. осталось только это всё на мушкетёров перенести...

Ну, арифметическая прогрессия — это совсем "боковая" проблема. А вот задачи о знакомых и незнакомых в компании — это самое то.

В отличие от многих разделов современной математики теорию Рамсея можно изложить на интуитивном уровне. В самом деле, привлекательность этой теории отчасти обусловлена той простотой, с которой можно сформулировать её задачи. Например, если из присутствующих на вечеринке случайным образом выбрать шесть человек (скажем, Альфреда, Бетти, Кэлвина, Дебору, Эдварда и Фрэнсис), то верно ли, что либо трое из них друг с другом знакомы, либо трое из них незнакомы друг с другом?

Мы можем решить эту «головоломку о вечеринке» многими способами. Мы могли бы перебрать все мыслимые комбинации и проверить, содержит ли каждая рассматриваемая группа трёх знакомых или трёх незнакомых людей. Но поскольку нам пришлось бы проверить 32 768 (или 215) комбинаций, то такой «метод грубой силы» не является ни практичным, ни поучительным.

К счастью, мы можем отыскать ответ, рассмотрев два простых случая. В первом из них предположим, что Альфред знает трёх (или больше) из числа остальных гостей, скажем, Бетти, Кэлвина и Дебору. Если Бетти и Кэлвин, или Бетти и Дебора, или Кэлвин и Дебора знакомы друг с другом, то Альфред и пара знакомых образуют группу из трёх знакомых людей; в противном случае Бетти, Кэлвин и Дебора друг с другом незнакомы. Во втором случае предположим, что Альфред знает самое большее двух (или меньше) из гостей, скажем, Бетти и Кэлвина. Если Дебора и Эдвард, или Дебора и Фрэнсис, или Эдвард и Фрэнсис незнакомы друг с другом, то Альфред и пара незнакомых между собой гостей образуют группу из трёх человек, незнакомых друг с другом. В противном случае Дебора, Эдвард и Фрэнсис друг с другом знакомы. Всего в шести предложениях мы доказали, почему любая группа из шести человек должна включать или трёх знакомых, или трёх незнакомых людей. Короче говоря, решение «головоломки о вечеринке» есть частный случай теории Рамсея.

А вот это — уже нужный фрагмент.

В "мушкетерских" терминах Вы нашли доказательство того, что из если среди шести мушкетеров не найдется трех, которые вызвали друг друга на дуэль, то в этой компании найдутся трое друзей. В терминах Рамсея:

R (3,3)=6.

А теперь разойдемся до утра и подумаем. Вы — над тем, где искать доказательство исходной задачи или как дойти до решения самостоятельно. Я — о том, как это рассказать Вам по-своему и покороче.

не понимаю вообще как решить эту задачу..

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

При вычислении (или, по крайней мере, оценивании) R(K,N) , на мой взгляд, удобно воспользоваться двумерной таблицей при K,N>=1. Искомые числа будем помещать на пересечении К-ой строки и N-ого столбца.

ПЕРВЫЙ ШАГ (горизонтальная/вертикальная индукция). Очевидно, что R(K,1)=R(1,N) при произвольных K,N. Действительно, среди одного человека всегда можно найти либо одного, знакомого с самим собой, либо попарно незнакомую друг с другом группу из N людей.
Не менее понятно и то, что R(K,2)=R(2,K)=K. Действительно, из К людей либо можно выбрать знакомую пару, либо все К людей будут попарно незнакомы.

ВТОРОЙ ШАГ (диагональная индукция). Начинается с приведенного Наталией доказательства того, что R(3,3)=6. Нетрудно понять, что R(3.3)=R(3,2)+R(2,3). Следующая гипотеза состоит в том, что на самом деле мы имеем дело с треугольником Паскаля, т.е.

R(K,N)=R(K-1,N)+R(K,N-1).

На самом деле все не совсем так. Доказательство со знаком <= проходит "на ура", но в результате мы получаем не точные значения R(K,N), а всего лишь их оценки сверху.

ТРЕТИЙ ШАГ (коррекция). Здесь нам пригодится "нетривиальная олимпиадная идея четности". Действительно, легко можно доказать, что при построении нашей модификации треугольника Паскаля в случае сложения двух четных чисел оценка уменьшается на единицу. Поэтому и R(3,4)=9 (а не 10).

Я надеюсь, что заинтересованные люди смогут сделать самостоятельно хотя бы оставшиеся недоказанными шаги. С другой стороны, я отдаю себе отчет в том, что мы имеем дело с ярко выраженной "лакмусовой" задачей, выявляющей детей, посещающих хорошие математические кружки. Если Дарья, Наталия и Гость не из их числа, то единственное, что я могу посоветовать — это почитать что-либо по указанным ссылкам. При этом времени жалеть не надо. Все-таки задача красивая, а от занятия теорией графов по нынешним временам никто не застрахован.

"Папа, ты с кем сейчас разговаривал?!" [:||||:]

Про Рамсея конечно интересно, но это задача прежде всего не на это. Удивительно, что среди присутствующих здесь нет ни одного грамотного профессионала посещавшего в детстве простой математический кружок. Т. е. они есть, но почему-то молчат или не обратили на эту задачу внимания. Эта устная задача для тех, кто в курсе на раскрашивание графа с 9 вершинами. Требуется доказать, что если в нем нет треугольника одного цвета, то обязательно найдется четырехугольник другого

Просто те, кто посещал кружок, предпочитают, чтобы человек САМ придумывал решения задач олимпиады.

Просто уже прошло 4 дня, а даже никакой разумной подсказки не появилось. А то, что это, оказывается, задача с какой-то олимпиады я пропустил. Увы.

Я посещал математический кружок очень давно. Многие преподаватели столько не живут, и , разумеется, всего, что там было, я не помню. Естественно, кружок моего сына прошел скорее "по касательной". Иногда приходится об это жалеть.

Но, как ни странно, то, что приведенная задача была у него в какой-то серии, я помню. Тогда мы ее не обсуждали, а я сам не смог решить ее "в лоб", пришлось "поднять" 9 до 10, а затем использовать четность.

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

Лемма. Из 6 есть либо трое попарно знакомых, либо трое попарно незнакомых.

Теперь ясно. Если у кого-то есть шестеро знакомых, то среди них есть либо трое незнакомых (победа) либо трое знакомых (тогда победа, если взять первого к ним). Если у кого-то есть четверо незнакомых, то либо они попарно знакомы, либо двое из них вместе с ним образуют незнакомую тройку. Если же у всех ровно по 3 незнакомых и 5 знакомых, то так не бывает по четности.

То есть ,насколько я понял, Вы пишете, что :

а) R(3,3)=6 ;

b) R(4,3)<=R(3,3)+R(4,2)=10;

c) R(4,3)=10-1=9 из соображений четности.

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

Доказать, что среди любых 6 человек найдутся либо трое попарно знакомых, либо трое незнакомых друг с другом. (Задача Рамсея.)
(6—... кл.)

Отрезок [0,1] произвольно разделили на несколько меньших отрезков и некоторые их них покрасили. Общая длина покрашенных отрезков больше 0.5 . Докажите, что на отрезке найдутся две окрашенные точки на расстоянии, равном 0.5 .
(6-...кл.)

В классе 25 учеников. Известно, что среди любых трех из них двое дружат между собой. Докажите, что есть ученик, у которого не менее 12 друзей.

Двое друзей должны поровну разделить 8 мер вина, но у них кроме сосуда, в котором находится вино и емкость которого в точности равна 8 мерам, есть только два других сосуда емкостью в 5 и 3 меры. Как разделить вино?

(да, по-видимому, это для детей...)