Комбинаторика. Решение задач

КОМБИНАТОРИКА

Контакты.
Зенович Андрей Васильевич.
Почта [e-mail]
Группа в контакте https://vk.com/public201279088
Телефон [phone]

Задача 1.
Девять лыжников ушли со старта по очереди и прошли дистанцию — каждый со своей постоянной скоростью. Могло ли оказаться, что каждый лыжник участвовал ровно в четырёх обгонах? (В каждом обгоне участвуют ровно два лыжника — тот, кто обгоняет, и тот, кого обгоняют.)

Задача 1. Решение.
Ответ. Не могло.
Решение. Предположим, что это возможно. Так как скорости постоянны, каждые два лыжника встречались не более одного раза. Тогда лыжник, стартовавший первым, не мог никого обогнать; значит, его обогнали четверо, и он пришел пятым. С другой стороны, лыжника, стартовавшего последним, никто не мог обогнать, поэтому он сам обогнал четверых и также пришел пятым. Противоречие.

Задача 2.
В компании из семи человек любые шесть могут сесть за круглый стол так, что каждые два соседа окажутся знакомыми. Докажите, что и всю компанию можно усадить за круглый стол
так, что каждые два соседа окажутся знакомыми.

Задача 2. Решение.
У каждого в компании не менее трёх знакомых. Если бы X был знаком менее, чем с тремя, то, исключив из компании одного из его знакомых, мы получили бы шестёрку людей, в которой у X не более одного знакомого, посадить их за круглый стол невозможно. Если бы у каждого было ровно по три знакомых, то число пар знакомых людей было бы равно 7 · 3/2 = 21/2 , что невозможно. Значит, у какого-то человека X хотя бы 4 знакомых. Рассадим всех, кроме X, за круглый стол. Тогда из четырёх его знакомых хотя бы двое сидят рядом. Посадим X между ними.

Задача 3.
Два бегуна стартовали одновременно из одной точки. Сначала они бежали по улице до стадиона, а потом до финиша — три круга по стадиону. Всю дистанцию оба бежали с постоянными скоростями, и в ходе забега первый бегун дважды обогнал второго. Докажите, что первый бежал по крайней мере вдвое быстрее, чем второй.

Задача 3. Решение.
Первый мог обогнать второго только на кольцевой дорожке стадиона. Так как он вбежал на стадион первым, на своём первом круге он обогнать второго не мог. Стало быть, обгоны случились, когда первый бежал по стадиону свои второй и третий круги. Пока первый бежал эти два круга, он обогнал второго по крайней мере на круг. Следовательно, второй за это время пробежал не больше одного круга, откуда и вытекает требуемое утверждение.

Задача 4.
Имеются 2013 карточек, на которых написана цифра 1, и 2013 карточек, на которых написана цифра 2. Вася складывает из этих карточек 4026-значное число. За один ход Петя может поменять местами некоторые две карточки и заплатить Васе 1 рубль. Процесс заканчивается, когда у Пети получается число, делящееся на 11. Какую наибольшую сумму может заработать Вася, если Петя стремится заплатить как можно меньше?

Задача 4. Решение.
Ответ. 5 рублей.
Оценка. Рассмотрим 4026-значное число A, состоящее из 2013 единиц и 2013 двоек. Пусть в этом числе в нечётных разрядах стоит k единиц и ℓ = 2013−k двоек, тогда в чётных разрядах будет k двоек и ℓ единиц. Разность сумм цифр в нечётных и чётных разрядах (k+2ℓ)−(2k+ℓ) = ℓ−k = 2013−2k. K должно делиться на 11. За один ход k изменяется не более чем на 1. Поэтому, если Вася изначально сложит число A, для которого k = 5, то Пете потребуется не менее 5 раз изменить k на 1, чтобы впервые получить число, для которого k кратно 11.

Задача 4. Продолжение решения.
Пяти ходов хватит. За один ход Петя может увеличить или уменьшить k на 1 за один ход. Пусть начальное Васино число давало остаток r при делении на 11. Если r = 0, то исходное число уже делится на 11, и ничего делать не нужно.
Если 1 ≤ r ≤ 5, то за r операций Петя может уменьшить k на r до ближайшего числа, кратного 11. Если же 6 ≤ r ≤10, то за 11−r ≤ 5 операций Петя может увеличить k на 11 − r до ближайшего числа кратного 11 (это возможно, так как наибольшее возможное значение k = 2013 кратно 11).

Задача 5.
После просмотра фильма зрители по очереди оценивали фильм целым числом баллов от 0 до 10. В каждый момент времени рейтинг фильма вычислялся как сумма всех выставленных оценок, делённая на их количество. В некоторый момент времени T рейтинг оказался целым числом, а затем с каждым новым проголосовавшим зрителем он уменьшался на единицу. Какое наибольшее количество зрителей могло проголосовать после момента T?

Задача 5. Решение.
Ответ. 5.
Пусть рейтинг уменьшился на 1. Перед этим проголосовало n человек, рейтинг был x. Значит, сумма баллов была nx. Пусть следующий зритель выставил y баллов. Тогда сумма баллов стала nx+y = (n+1)(x−1), откуда y = x−n−1. Наибольшее x равно 10, а наименьшее n равно 1; значит, наибольшее y (на первом таком шаге) равно 8. С каждым следующим шагом x уменьшается на 1, а n увеличивается на 1. Следовательно, на втором шаге значение y ≤ 6, на третьем y ≤4, и т.д. Любая оценка не меньше 0, число шагов не превосходит 5.

Задача 5. Решение. Продолжение.
Пример. Осталось показать, что пять шагов возможны. Пусть рейтинг в момент T равен 10 (при 1 проголосовавшем), затем второй зритель выставляет 8 баллов, третий — 6, четвёртый — 4, пятый — 2, а шестой — 0. Тогда рейтинг последовательно принимает значения 9, 8, 7, 6 и 5.

Задача 6.
У царя Гиерона есть 11 металлических слитков, неразличимых на вид; царь знает, что их веса (в некотором порядке) равны 1, 2, . . . , 11 кг. Ещё у него есть мешок, который порвётся, если в него положить больше 11 кг. Архимед узнал веса всех слитков и хочет доказать Гиерону, что первый слиток имеет вес 1 кг. За один шаг он может загрузить несколько слитков в мешок и продемонстрировать Гиерону, что мешок не порвался (рвать мешок нельзя!). За какое наименьшее число загрузок мешка Архимед может добиться требуемого?

Задача 6. Решение.
Ответ. За 2 загрузки.
Сначала кладем в мешок слитки 1, 2, 3 и 5 кг, а потом — слитки 1, 4 и 6 кг. В обоих случаях мешок не порвётся. Докажем, тогда дважды был использован слиток 1 кг. Если бы использовали слитки с весами w1, . . . , w6 кг, то получили бы w1 + w2 + w3 + w5 ≤ 11, w1 + w4 + w6 ≤ 11. Отсюда w1 + (w1 + w2 + . . . + w6) ≤ 22. В скобках стоит сумма шести различных натуральных чисел, она не меньше 1 + 2 + . . . + 6 = 21. Т.е. w1 ≥ 22 − 21 = 1. Значит, w1 = 1.

Задача 7.
В классе учится 23 человека. В течение года каждый ученик этого класса один раз праздновал день рождения, на который пришли некоторые (хотя бы один, но не все) его одноклассники. Могло ли оказаться, что каждые два ученика этого класса встретились на таких празднованиях одинаковое число раз? (Считается, что на каждом празднике встретились любые два гостя, а также именинник встретился со всеми гостями.)

Задача 8.
Вася задумал 8 клеток шахматной доски, никакие две из которых не лежат в одной строке или в одном столбце. За ход Петя выставляет на доску 8 ладей, не бьющих друг друга, а затем Вася указывает все ладьи, стоящие на задуманных клетках. Если количество ладей, указанных Васей на этом ходе, чётно (т.е. 0, 2, 4, 6 или 8), то Петя выигрывает; иначе все фигуры снимаются с доски и Петя делает следующий ход. За какое наименьшее число ходов Петя сможет гарантированно выиграть?

Координаты ИМИТ в Интернете
Web-site: mf.volsu.ru
Социальная сеть Вконтакте:
vk.com/fmit_abiturient
E-mail: [e-mail]