СПРОСИ ПРОФИ
👍
0
👎 02

Принцип Дирихле

В классе 25 учеников. Среди любых трех из них есть двое друзей. Доказать, что есть ученик, у ктрого не менее 12друзей. Мне сказали, что задача на принцип Дирихле, прочитал, но не пойму, где клетки и где кролики.
математика обучение     #1   29 окт 2012 15:28   Увидели: 1122 клиента, 1 специалист   Ответить
👍
+1
👎 1
Если два ученика не являются друзьями, будем называть их врагами.
Допустим, что утверждение, которое требуется доказать, неверно:
у каждого ученика менее 12 друзей.
Тогда у каждого ученика не менее 13 врагов.
Выберем двух враждующих друг с другом учеников.
Пусть их фамилии — Иванов и Петров.
Наша задача — отыскать среди оставшихся 23 учеников некоторого ученика X,
который является врагом и Иванова, и Петрова.
Если нам удастся отыскать X, то в тройке <Иванов, Петров, X>
не окажется двух друзей, то есть мы придём к противоречию.
Отыскать X нам помогут клетки и кролики.
Изготовим 23 клетки и на клетках напишем фамилии оставшихся 23 учеников.
У Иванова, кроме врага Петрова, имеется ещё 12 врагов — дадим Иванову 12 кроликов.
У Петрова, кроме врага Иванова, имеется ещё 12 врагов — дадим Петрову 12 кроликов.
Прикажем Иванову и Петрову, чтобы каждый из них посадил каждого из своих
кроликов в такую клетку, на которой написана фамилия его врага.
(Но при этом потребуем, чтобы никто из них не сажал более двух СВОИХ кроликов
в одну клетку.)
Количество кроликов равно 24. Количество клеток равно 23.
Обязательно найдётся такая клетка, в которой окажутся два кролика
(посаженных разными хозяинами).
Фамилия ученика, написанная на этой клетке, — это и есть искомый X.
👍
0
👎 0
Спасибо. Здорово понятно. Но для закрепления еще моя задачаю
В классе 25 учеников. Любые три один раз ходили вместеили на футбол, или на волейбол. Доказать, что в классе найдется четверка учеников, любые трое из которых ходили на одну и ту же игру.
  #3   31 окт 2012 11:07   Ответить

Задайте свой вопрос по математике
профессионалам

Сейчас онлайн 75 репетиторов по математике
Получите ответ профи быстро и бесплатно

Другие вопросы на эту тему:

👍
0
👎 02

Математическая задача . Принцип Дирихле .   2 ответа

По краю круглого стола равномерно расставлены таблички с фамилиями дипломатов , участвующих в переговорах. После начала переговора оказалось , что ни один из дипломатов не сидит против своей таблички . Докажите , что можно повернуто свой стол так , чтобы не меньше двух дипломатов сидели против своих табличек.
  21 янв 2015 17:06  
👍
0
👎 04

Математическая задача. Принцип Дирихле   4 ответа

!) Докажите что , среди 65 кубиков , каждый их которых выкрашен в определённый цвет , всегда можно выбрать либо 9 кубиков выкрашенных в разные цвета , либо 9 одного цвета.
2) Сколько кубиков нужно взять , чтобы среди них наверняка нашлось либо 10 разноцветных , либо — 14 одного цвета?
  19 янв 2015 18:33  
👍
0
👎 03

Математическая задача, принцип Дирихле   3 ответа

математическая задача , принцип Дирихле.
У биологов Наташи , Ани , Оли есть 49 лабораторных мышей . Пытливые экспериментаторы поделили мышей между собой . Докажите , что хотя бы у одной из них найдутся или пять одинаковых мышек , или пять разных .
  17 янв 2015 12:22  
👍
0
👎 03

Задача 1181. Решите задачу рациональным способом   3 ответа

Следующая задача 1181.
Решите задачу рациональным способом.
Ученик прочитал книгу за 3 дня. В первый день 0, 2 стр и еще 5 страниц.Во второй 0, 4 оставшихся страниц и еще 7 стр. В 3 день он прочитал 0, 8 остатка и еще остальные 10 стр.Сколько всего стр в книге?
1)
1 — 0, 2 =0, 8 остаток от 1 дня.
2)
0, 4 от 0, 8 ...?
0, 8 -100%
0, 4-х %
Х= 50%.
Далее бред и тупик.Тем более, проценты не проходили.
Помогите, объясните подробнее суть!
👍
0
👎 01

Помогите решить задачу по математике 6 класс   1 ответ

Мальчик прочитал 25% книги, а затем 2/3 оставшейся части. После этого он заметил, что прочитал на 25 страниц больше, чем ему осталось прочитать. Сколько страниц в книге?
👍
0
👎 01

В классе 25 учеников   1 ответ

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