Страница:
<< 41 42 43 44
45 46 47 >> [Всего задач: 328]
На ребрах связного графа расставлены стрелки так, что для каждой вершины числа входящих и выходящих рёбер равны.
Докажите, что двигаясь по стрелкам, можно добраться от каждой вершины до любой другой.
|
|
|
Сложность: 4
Классы: 7,8,9,10
|
Сто мудрецов хотят проехать на электричке из 12 вагонов от первой до 76-й станции. Они знают, что на первой станции в два вагона электрички сядут два контролёра. После четвёртой станции на каждом перегоне один из контролёров будет переходить в соседний вагон, причём они "ходят" по очереди. Мудрец видит контролёра, только если он в соседнем вагоне или через вагон. На каждой станции каждый мудрец может перебежать по платформе не далее чем на три вагона (например, из 7-го вагона мудрец может добежать до любого вагона с номером от 4 до 10 и сесть в него). Какое максимальное число мудрецов сможет ни разу не оказаться в одном вагоне с контролёром, как бы контролёры ни перемещались? (Никакой информации о контролёрах, кроме указанной в задаче, мудрец не получает. Мудрецы договариваются о стратегии заранее.)
|
|
|
Сложность: 4
Классы: 10,11
|
Докажите, что при умножении многочлена (x + 1)n–1 на любой многочлен, отличный от нуля, получается многочлен, имеющий не менее n отличных от нуля коэффициентов.
|
|
|
Сложность: 4
Классы: 9,10,11
|
Пусть a0 – целое, a1, ..., an – натуральные числа. Определим две последовательности
P–1 = 1, P0 = a0, Pk = akPk–1 + Pk–2 (1 ≤ k ≤ n); Q–1 = 0, Q0 = 1, Qk = akQk–1 + Qk–2 (1 ≤ k ≤ n).
Дроби Pk/Qk называются подходящими дробями к числу [a0; a1, a2, ..., an].
Докажите, что построенные последовательности для k = 0, 1, ..., n обладают следующими свойствами:
а) Pk/Qk = [a0; a1, a2,..., ak];
б) PkQk–1 – Pk–1Qk = (–1)k+1;
в) (Pk, Qk) = 1.
|
|
|
Сложность: 4
Классы: 8,9,10
|
Ханойская башня и двоичная
система счисления.
Рассмотрим два
процесса, каждый из которых состоит из 2
8 - 1 шагов. Первый —
это процесс решения головоломки ``Ханойская башня'' (смотри задачу
1.42) при
помощи оптимального алгоритма. Второй — это процесс прибавления
единицы, который начинается с 0 и заканчивается числом 2
8 - 1.
Опишите связь между этими двумя процессами.
Страница:
<< 41 42 43 44
45 46 47 >> [Всего задач: 328]
Фильтр
Решение 
