FAQ по форумуНовые сообщения на Форуме
  • Страница 1 из 1
  • 1
Задачка на принцип Дирихле
IQFunДата: Чт, 06.07.17, 10:32 | Сообщение # 1
Просветленный
Сообщений: 671
Награды: 39
Совы: 30
В продолжение темы неверности принципа Дирихле по памяти привожу задачку повышенной сложности с одной Всемирной математической олимпиады школьников: в одном математическом конгрессе участвовало 1979 учёных из 6-ти стран. Они были перенумерованы от 1 до 1979. Доказать, что найдутся 3 учёных из одной страны таких, что сумма номеров двух из них равна номеру 3-го, или найдутся два таких из одной страны, что удвоенный номер одного равен номеру второго.

Т.к. уже есть подсказка, что теорема доказывается последовательным применением принципа Дирихле, то остаётся пожелать успехов. :)


IQFun.ru - играем и растём над собой. Авторские игры, головоломки, кроссворды онлайн, интересные статьи.


Сообщение отредактировал IQFun - Чт, 06.07.17, 10:33
 
никникДата: Вс, 09.07.17, 02:32 | Сообщение # 2
Высший разум
Сообщений: 2770
Награды: 406
Совы: 15
да, ответа нема. потом еще подумаю
Каждый ученный участвует в 1978 тройках, составленных таким образом, что сумма номеров 2х участников = номеру 3....
Есть 660 ученных из одной страны у которых.... 
1 990-1979 Англия 1, 
2 445-889
3 223-444
4 112-222

14691114161921242629
23781213171822232728
520304555708095
10154050608590
25356575
100


Между своеобразной логикой и откровенной глупостью иногда очень тонкая грань.
 
IQFunДата: Ср, 13.12.17, 13:46 | Сообщение # 3
Просветленный
Сообщений: 671
Награды: 39
Совы: 30
Это что, дневник сумасшедшего математика? :)

Добавлено (13.12.2017, 13:46)
---------------------------------------------
Нашёл вчера эту задачку и её решение в задачнике "Кванта". Она была отмечена звёздочкой, как с повышенной трудностью, но решение у неё короткое и простое. Просто, надо рассуждать логически и всё! :) Она была на XX Международной математической олимпиаде для школьников в Бухаресте в 1978 г. Поэтому в условии должно быть 1978 участников, а не 1979, что несущественно.

Идея решения: просто 5 раз используем принцип Дирихле и готово! И ещё надо сначала предположить что-нибудь противное, напр., что таких участников не найдётся, а потом это опровергнуть!

По принципу Дирихле, найдётся такая страна, из котрой будет не менее ]1978/6[ = 330 чел. Пусть их номера будут a1, a2, ..., a330. По противному предположению, номера a2-a1, a3-a1, ..., a330-a1 должны принадлежать участникам из остальных 5-ти стран. Из этих 329 номеров найдётся ]329/5[ = 66 номеров, которые должны принадлежать участникам из одной и той же страны, пусть эти номера будут b1, b2, ..., b66. Тогда 65 номеров b2-b1, b3-b1, ..., b66-b1 должны принадлежать участникам из оставшихся 4-х стран. Из них найдётся ]65/4[ = 17 номеров, которые принадлежат участникам одной и той же страны, пусть они будут c1, c2, ..., c17. Тогда 16 номеров c2-c1, c3-c1, ..., c17-c1 принадлежат участникам из оставшихся 3-х стран. Из них найдётся ]16/3[ = 6 номеров из одной и той же страны. Пусть эти номера будут d1, d2, ..., d6. Тогда 5 номеров d2-d1, d3-d1, ..., d6-d1 принадлежат участникам оставшихся 2-х стран. Из них найдётся ]5/2[ = 3 номера, которые принадлежат участникам из одной и той же страны. Их разности e2-e1 и e3-e1 не могут быть номерами участника ни одной страны. Противоречие!


IQFun.ru - играем и растём над собой. Авторские игры, головоломки, кроссворды онлайн, интересные статьи.


Сообщение отредактировал IQFun - Ср, 13.12.17, 13:56
 
zhekasДата: Ср, 13.12.17, 15:49 | Сообщение # 4
Гуру
Сообщений: 166
Награды: 43
Совы: 6
Цитата IQFun ()
Тогда 65 номеров b2-b1, b3-b1, ..., b66-b1 должны принадлежать участникам из оставшихся 4-х стран.

А почему эти 65 номеров не могут входить в первую группу (Та где номера a1,...,a330)?
 
IQFunДата: Ср, 13.12.17, 16:02 | Сообщение # 5
Просветленный
Сообщений: 671
Награды: 39
Совы: 30
По противному предположению. :) Например: b3-b1-(b2-b1)=b3-b2=a3-a1-(a2-a1)=a3-a2.

IQFun.ru - играем и растём над собой. Авторские игры, головоломки, кроссворды онлайн, интересные статьи.
 
  • Страница 1 из 1
  • 1
Поиск:

Интересная информация
Последние задачи Сообщество эрудитов ВКонтакте Рейтинг сообщений Совиный рейтинг
1.Арнольд, да не тот77
2.Простенький вопросик9
3.Гидродинамика14
4.Быстрая река.24
5.А попробуйте ещё это опро...6
6.Задача по логике7
7.Головоломка без ключа2
8.Задача о парадоксе Петров...11
9.Напрасно ли ожидание7
10.Чудо-Юдо и три головы12
1.Rostislav5379
2.Lexx4728
3.nebo3639
4.Иван3061
5.никник2770
6.Kreativshik2472
7.Гретхен1807
8.Vita1578
9.erudite-man1378
10.Valet937
1.nebo123
2.Kreativshik113
3.sovetnik49
4.MrCredo38
5.IQFun30
6.Pro100_Artyom27
7.marutand20
8.хан20
9.никник15
10.Фигаро15

ГлавнаяГостевая книгаFAQОбратная связьКоллегиФорум Эрудитов