Страница:
<< 4 5 6 7 8 9 10 >> [Всего задач: 326]
|
|
|
Сложность: 4-
Классы: 8,9,10,11
|
В шахматном турнире каждый участник сыграл с каждым из остальных одну партию.
Доказать, что участников можно так занумеровать, что окажется, что ни один
участник не проиграл непосредственно за ним следующему.
Подсказка
Примените индукцию по числу участников турнира.
Решение
Применим индукцию по числу n участников турнира. База (два участника) очевидна.
Шаг индукции. Рассмотрим некоторый турнир с n + 1 участником. Выделим одного из участников – C, все встречи между остальными участниками образуют турнир для n участников. Согласно предположению индукции, этих n участников можно обозначить A1, A2, ..., An так, что участник Ai не проиграл Ai+1 (для всех i = 1, 2, ..., n – 1). Пусть m – наибольший номер, для которого участник С проиграл участникам A1, A2, ..., Am (если C выиграл у участника A1, то полагаем m = 0). Тогда C не проиграл участнику Am+1 (кроме случая m = n). Поэтому ряд A1, A2, ..., Am, C, Am+1, Am+2, ..., An удовлетворяет условию (если m = 0, то ряд начинается с С, если m = n, то ряд заканчивается на C).
|
|
|
Сложность: 4-
Классы: 8,9,10,11
|
В n мензурок налиты n разных жидкостей, кроме того, имеется одна пустая мензурка. Можно ли за конечное число операций составить равномерные смеси
в каждой мензурке, то есть сделать так, чтобы в каждой мензурке было равно
1/n от начального количества каждой жидкости, и при этом одна мензурка была бы пустой. (Мензурки одинаковые, но количества жидкостей в них могут быть разными; предполагается, что можно отмерять любой объём жидкости.)
Решение
Докажем, что это возможно, индукцией по n. При n = 1 доказывать нечего – мы уже имеем в первой мензурке
равномерную смесь из одной жидкости.
Шаг индукции. Пусть мензурка M1 – пустая, а M2, ..., Mn+2 – полные. Вначале отложим в сторону мензурку Mn+2. Воспользовавшись предположением индукции, сделаем так, чтобы в каждой из мензурок M2, ..., Mn+1 была равномерная смесь первых n жидкостей, а мензурка M1 была пустой.
Разольём жидкость из M2, ..., Mn+1 поровну в M1, ..., Mn+1. После этого перельём в каждую из этих мензурок по 1/n+1 жидкости из Mn+2.
Ответ
Можно
|
|
|
Сложность: 4-
Классы: 8,9,10
|
Натуральные числа a1, a2, ..., an таковы, что каждое не превышает своего номера (ak ≤ k) и сумма всех чисел – чётное число.
Доказать, что одна из сумм a1 ± a2 ± ... ± an равна нулю.
Решение
Докажем это утверждение индукцией по n.
База (n = 2) очевидна, так как единственный возможный набор a1 = a2 = 1.
Шаг индукции. Возьмём удовлетворяющий условию набор a1, a2, ..., an, an+1. Если an = an+1, то сумма a1 + ... + an–1 чётна; учитывая предположение индукции, заключаем, что одна из сумм a1 ± a2 ± ... ± an–1 + an − an+1 равна нулю.
Если же an ≠ an+1, заменим данный набор набором a1, a2,..., an–1, |an − an+1|. Для нового набора выполнены все условия: число |an − an+1| имеет
ту же чётность, что и an + an+1; из an ≠ an+1, 1 ≤ an ≤ n и 1 ≤ an+1 ≤ n + 1 вытекает 1 ≤ |an − an+1|. По предположению индукции одна из сумм
a1 ± a2 ± ... ± |an − an+1| равна нулю. Остаётся "раскрыть модуль": |an − an+1| = ± (an − an+1).
|
|
|
Сложность: 4
Классы: 6,7,8,9
|
В поселке 100 домов. Какое наибольшее число замкнутых не пересекающихся заборов можно построить, чтобы каждый забор огораживал хотя бы один дом и никакие два забора не огораживали бы одну и ту же совокупность домов?
Решение
В максимальном наборе заборов есть забор, ограничивающий ровно два дома. Объединив эти два дома в один, мы уменьшим количество домов на 1, а количество заборов на 2. При этом оба условия задачи сохраняются. Продолжим этот процесс. После 99 шагов останется один дом и один забор. А убрали мы 198 заборов. Значит, всего их было 199.
Ответ
199 заборов.
|
|
|
Сложность: 4
Классы: 8,9,10
|
Числовая последовательность A1, A2, ..., An, ... определена равенствами A1 = 1, A2 = – 1, An = – An–1 – 2An–2 (n ≥ 3).
Докажите, что при любом натуральном n число 
является полным квадратом.
Решение
Рассмотрим другую последовательность B1, ..., Bn, ..., определенную тем же рекуррентным соотношением, но с другими начальными условиями:
B1 = 1, B2 = 3. Докажем по индукции соотношения: 
База. 
Шаг индукции.
Итак,
Страница:
<< 4 5 6 7 8 9 10 >> [Всего задач: 326]
Фильтр
