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