Страница:
<< 3 4 5 6 7 8 9 >> [Всего задач: 323]
|
|
|
Сложность: 4-
Классы: 8,9,10,11
|
n – натуральное число. Докажите, что nn > (n + 1)n–1.
Решение
Применим метод математической индукции. База (n = 2) очевидна.
Шаг индукции. 
по предположению индукции.
|
|
|
Сложность: 4-
Классы: 7,8,9,10
|
Колода из 36 карт
сложена так, что через четыре карты
масть повторяется. Несколько карт сверху сняли, не
перекладывая перевернули и вставили
произвольным образом (не обязательно подряд)
между оставшимися. После этого колоду разделили на
9 стопок по 4 идущие подряд карты. Докажите,
что в каждой из этих
стопок встретится по одной карте каждой масти.
Подсказка
Можно заметить, что первые четыре карты колоды,
полученной в результате описанной операции,
лежали подряд в первоначальной колоде.
Решение
Обозначим через A начальное расположение карт в колоде,
через B - распожение карт в колоде, полученной из
колоды A указанным в условии задачи преобразованием.
Обозначим A' ту часть колоды A, котрую мы сняли сверху,
и через A'' оставшуюся часть.
Посмотрим, где в колоде A находятся первые четыре карты колоды
B. Нетрудно понять, что они находятся на "стыке"
колод A' и A'', т.е. в эту четверку карт входят
несколько (возможно, ни одной) последних карт
A' и несколько первых карт A''.
Поскольку масти в колоде A повторяются с периодом 4,
то в этой четверке по одной карте каждой масти.
Вынем эту четверку из колод A и B.
Мы приходим к аналогичной задаче для меньшей колоды
(так как в колоде A без четырех подряд идущих карт
масти снова повторяются с периодом 4).
Продолжая рассуждать аналогичным образом, рассматриваем
следующую четверку карт колоды B и т.д.
В конце концов, приходим к тому, что требуется доказать.
|
|
|
Сложность: 4-
Классы: 8,9,10
|
Для любого натурального числа n существует составленное из цифр 1 и 2 число, делящееся на 2n. Докажите это.
(Например, на 2 делится 2, на 4 делится 12, на 8 делится 112, на 16 делится 2112...)
Решение
Докажем, что разные n-значные числа, составленные из цифр 1 и 2, дают разные остатки при делении на 2n.
Действительно, разность d таких чисел можно представить в виде an·10n–1 + an–1·10n–2 + ... + a2·10 + a1, где каждое из чисел ai равно 0 или ±1. Рассмотрим наименьший номер k, для которого ak ≠ 0. Очевидно, что d делится на 2k–1, но не делится на 2k. Таким образом, d делится на 2n только тогда, когда d = 0.
Но и таких n-значных чисел, и различных остатков ровно 2n, поэтому одно из этих чисел дает остаток нуль, то есть делится на 2n.
|
|
|
Сложность: 4-
Классы: 7,8,9
|
n человек не знакомы между собой. Нужно так познакомить друг с другом некоторых из них, чтобы ни у каких трёх людей не оказалось одинакового числа знакомых. Докажите, что это можно сделать при любом n.
Решение
Индукция по n. База. При n < 3 конструкция очевидна.
Шаг индукции. Предположим, что удалось познакомить n человек, так, что никакие трое из них не имеют равного числа знакомых. Присоединим (n+1)-го. Если среди первых n человек найдётся человек, знакомый со всеми остальными, то (n+1)-го не будем ни с кем знакомить. Если же такого нет, то познакомим (n+1)-го со всеми.
В первом случае (n+1)-й не имеет знакомых, а каждый из остальных имеет хоть одного знакомого – того, который ранее был знаком со всеми. Во втором случае (n+1)-й имеет n знакомых, количество знакомых у каждого из первых n человек возросло на единицу, но ни у одного из них не стало n знакомых.
На рисунке показаны схемы знакомств при n ≤ 6, получающиеся описанным способом.
|
|
|
Сложность: 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).
Страница:
<< 3 4 5 6 7 8 9 >> [Всего задач: 323]
Фильтр
