В классе 30 учеников, причём каждый дружит не менее, чем с 23 другими. Можно ли утверждать, что найдутся 5 учеников, которые все дружат между собой?

задан 23 Июл '17 17:13

10|600 символов нужно символов осталось
2

Положительный ответ сразу следует из теоремы Турана. Если простой граф с $%n$% вершинами содержит строго больше, чем $%\frac{n^2}2(1-\frac1r)$% рёбер, то в нём имеется полный подграф $%K_{r+1}$%. (Я буду опираться именно на такую удобную в использовании формулировку.)

В данном случае справедливо неравенство $%\frac{23}{30} > \frac34=1-\frac1r$% при $%r=4$%, и число рёбер графа знакомств не меньше $%\frac{30\cdot23}2 > \frac{n^2}2(1-\frac1r)$% при $%n=30$%, откуда всё следует.

Кстати, плавленые сырки "Дружба" я на днях видел в местных магазинах :)

ссылка

отвечен 23 Июл '17 19:40

@falcao, большое спасибо! Если вместо 23 стояло бы 22, ответ был бы иным?

(offtop): Вы не поверите, но сырки "Дружба" продаются даже в Израиле. Я, правда, не знаю, импортируют ли их из России или производят в самом же Израиле по российскому рецепту.

(24 Июл '17 0:38) Аллочка Шакед
1

@Аллочка Шакед: экстремальная теорема Турана, как правило, работает в обе стороны. Для 22 знакомств строится такой контрпример: разбиваем 30 человек на 4 группы примерно одинаковой численности: 7, 7, 8, 8. Пусть каждый знаком со всеми кроме членов своей группы. Тогда у 14 человек будет по 23 знакомых, а у 16 человек по 22. Пятерых попарно знакомых нет: среди пяти есть два члена одной группы, а они не знакомы.

Интересно, сколько стоит сырок в "мировых ценах"? В СССР он стоил 26 коп. :)

(24 Июл '17 7:35) falcao

@falcao, спасибо за красивый пример! Цена "Дружбы" в Израиле, кажется, 3 шекеля с гаком за один сырок. Честно, не помню точно. Но дёшево по израильским меркам. Доступно даже инвалидам. А насчёт 26 советских копеек - так тогда и доллар стоил 58 копеек! Хотя, всё равно почти вдвое дешевле получается...

(24 Июл '17 16:02) Аллочка Шакед
1

@Аллочка Шакед: спасибо за информацию. Сравнивать цены разных мест и разных времён -- это у меня своего рода "хобби" :) Доллар за сырок, imho, многовато.

(24 Июл '17 17:25) falcao
1

В Москве 10 руб (70г). Сам не ем сыр (никакой), но отзывы плохие

(24 Июл '17 17:36) epimkin
1

@epimkin: это "сырный продукт", на нём так написано. Поэтому стоит дешевле.

(25 Июл '17 21:25) falcao

@falcao, не хочу оффтопить, но раз уж пошла такая пьянка, можно узнать, чем "сырный продукт" отличается от сыра?

(26 Июл '17 0:29) Аллочка Шакед
1

@Аллочка Шакед: это когда молочный жир заменяют растительным. По вкусу не каждый отличит, но в таких случаях правила не разрешают называть продукт "сыром".

(26 Июл '17 8:21) falcao
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,254
×1,102
×340
×209
×122

задан
23 Июл '17 17:13

показан
707 раз

обновлен
26 Июл '17 8:21

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru