Страница:
<< 6 7 8 9
10 11 12 >> [Всего задач: 59]
Задача
60314
(#01.041)
|
|
Сложность: 3
Классы: 8,9
|
Из квадрата клетчатой бумаги размером
16×16
вырезали одну клетку. Докажите, что полученную фигуру можно
разрезать на "уголки'' из трех клеток.
Задача
60315
(#1.42, 1.43, 1.44)
[Ханойская башня I]
|
|
Сложность: 3+
Классы: 8,9,10
|
а) Головоломка "Ханойская башня" представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трёх колышков. Требуется переместить всю башню на другой колышек, перенося каждый раз только один диск и не помещая больший диск на меньший. Докажите, что головоломка имеет решение. Какой способ будет оптимальным (по числу перекладываний дисков)?
б) Занумеруем колышки числами 1, 2, 3. Требуется переместить диски с 1-го колышка на 3-й. Сколько понадобится перекладываний, если прямое перемещение диска с 1-го колышка на 3-й и с 3-го на 1-й запрещено (каждое перекладывание должно производиться через 2-й колышек)?
в) Сколько понадобится перекладываний, если в условии пункта а) добавить дополнительное требование: первый (самый маленький) диск нельзя класть на 2-й колышек?
Решение
а) Пусть минимальное число шагов для перемещения башни из n дисков равно Kn. Выразим Kn+1 через Kn.
Рассмотрим башню из n + 1 диска. Разобьём всю процедуру на три этапа.
Этап 1 – от начала до первого перемещения нижнего диска. В конце этого этапа стоящая на нижнем диске башня из n дисков должна переместиться на один из свободных колышков (колышек, на который следующим шагом должен переместиться нижний диск, должен быть свободен). Нижний диск в этих перемещениях не участвует, следовательно, для этого необходимо (и достаточно) Kn шагов.
Этап 2 – от первого до последнего перемещения нижнего диска. Одного шага достаточно: после первого перемещения нижний диск можно больше не трогать.
Этап 3 – после последнего перемещения нижнего диска. В начале этого этапа колышек, с которого перед этим был снят нижний диск, свободен. Значит, на третьем колышке стоит башня из n дисков, и ее надо переместить на нижний диск. Для такого перемещения также нужно Kn шагов.
Итак, Kn+1 = Kn + 1 + Kn = 2Kn + 1 (выше показано, что меньшим числом шагов обойтись нельзя, а такого количества достаточно).
Поскольку K1 = 1, мы можем последовательно вычислить K2, K3, ..., K8.
Нетрудно вывести и общую формулу: записав полученное соотношение в виде Kn+1 + 1 = 2(Kn + 1), имеем Kn + 1 = 2n–1(K1 + 1) = 2n.
Замечание. "Угадав" ответ, можно его доказать по индукции.
б) Рассуждаем аналогично. Заметим, что здесь K1 = 2.
Сначала придется переместить башню из n дисков с 1-го колышка на 3-й (Kn шагов). Теперь можно переместить нижний диск на 2-й колышек. Затем придется вернуть остальные диски на 1-й колышек, и тогда можно переложить нижний диск на 3-й колышек. Останется снова переместить остальные диски с 1-го колышка на 3-й. Поэтому в нашей ситуации Kn+1 = Kn + 1 + Kn + 1 + Kn = 3Kn + 2.
Записав его в виде Kn+1 + 1 = 3(Kn + 1), получим Kn + 1 = 3n–1(K1 + 1) = 3n.
в) Из-за того, что все башни, содержащие первый диск, приходится собирать на 3-м или 1-м колышках, отличие от рассуждений п. б) только в том, что K1 = 1. Поэтому из того же соотношения Kn + 1 = 3n–1(K1 + 1) получаем Kn = 2·3n–1 – 1.
Ответ
а) Самый короткий способ содержит 28 – 1 = 255 перекладываний.
б) 38 – 1 = 6560 перекладываний; в) 2·37 – 1 = 4373 перекладывания.
Задача
60318
(#01.045)
|
|
Сложность: 3
Классы: 8,9,10
|
Докажите, что квадрат можно разрезать на
n квадратов для
любого
n, начиная с шести.
Решение
Если квадрат допускает разбиение на
n квадратов,
то он допускает разбиение и на
n + 3 квадрата (достаточно один из
квадратов разрезать на четыре). Разобьем все натуральные числа на
три арифметические прогрессии
n = 3
k,
n = 3
k + 1,
n = 3
k + 2, и в
каждой из них найдем минимальное
n, для которого задача имеет
решение. В первой прогрессии минимальное такое
n равно 6, во
второй — 4, в третьей — 8. (Требуемые разбиения строятся
из квадратов 3×3, 2×2 и 5×5.
Задача
60319
(#01.046)
|
|
Сложность: 3
Классы: 8,9,10
|
Докажите, что правильный треугольник можно
разрезать на
n правильных треугольников для любого
n, начиная
с шести.
Задача
60320
(#01.047)
[Золотая цепочка]
|
|
Сложность: 3
Классы: 9,10
|
а) На постоялом дворе остановился путешественник, и хозяин согласился в качестве уплаты за проживание брать кольца золотой цепочки, которую тот носил на руке. Но при этом он поставил условие, чтобы оплата была
ежедневной: каждый день хозяин должен был иметь на одно кольцо больше, чем в предыдущий. Замкнутая в кольцо цепочка содержала 11 колец, а путешественник собирался прожить ровно 11 дней, поэтому он согласился. Какое наименьшее число колец он должен распилить, чтобы иметь возможность платить хозяину?
б) Из скольких колец должна состоять цепочка, чтобы путешественник мог прожить на постоялом дворе наибольшее число дней при условии, что он может распилить только
n колец?
Решение
а) Достаточно разрезать два кольца так, чтобы отделились куски из трёх и шести колец. На третий день путешественник отдает кусок из трёх колец и получает два кольца сдачи, а на шестой – кусок из шести колец и получает пять колец сдачи.
б) Расположим получившиеся куски цепочки (не считая распиленных колец) по возрастанию числа колец в них:
a1 ≤ a2 ≤ ... Ясно, что a1 ≤ n + 1 (иначе заплатить за (n+1)-й день не удастся), a2 ≤ a1 + n + 1 ≤ 2(n + 1), a3 ≤ a2 + a1 + n + 1 ≤ 4(n + 1), ... Кроме того, количество кусков не превосходит n. Поэтому в цепочке не более n + (n + 1)(1 + 2 + 2² + ... + 2n–1) = (n + 1)2n – 1 колец.
Взяв куски максимальной возможной длины (ak = (n + 1)2k–1, k = 1, ..., n), мы получим цепочку из (n + 1)2n – 1 колец.
Ответ
а) 2 кольца. б) Из (
n + 1)2
n – 1 колец.
Страница:
<< 6 7 8 9
10 11 12 >> [Всего задач: 59]
Все источники
>>
Книги, журналы
>>
Алфутова Н.Б., Устинов А.В., Алгебра и теория чисел
>>
глава 1. Метод математической индукции
