а) Может ли быть различных чисел в такой последовательности?
б) Может ли быть различных чисел в такой последовательности?
в) Какое наибольшее количество различных чисел может быть в такой последовательности?
Ответ и решение
Выясним, какие переходы возможны. Следующее число, либо на меньше предыдущего, либо делится на него, то есть равно , где это предыдущее, . При имеем , что невозможно. Значит, возможны только три перехода: , (число повторяется) и при , то есть .
Чётность. Переходы и не меняют чётности, а даёт чётное число. Значит, из чётного числа нельзя перейти к нечётному; нечётное число можно сменить на чётное только удвоением , а это возможно для нечётных от до : , , . Поэтому в последовательности сначала идут нечётные числа, затем (после одного удвоения) только чётные.
Инвариант — величина, которая не изменяется в результате некоторых операций … Если инвариант различает два положения, то от одного нельзя перейти к другому. В качестве инварианта может использоваться чётность или раскраска.
Учебные материалы. Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи, под ред. В. О. Бугаенко, МЦНМО, 2008, Инварианты, с. 29
Многие задачи легко решаются, если заметить, что некоторая величина имеет определённую чётность. Из этого следует, что ситуации, в которых эта величина имеет другую чётность, невозможны.
Учебные материалы. Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи, под ред. В. О. Бугаенко, МЦНМО, 2008, Чётность, с. 13
а) Может ли быть различных чисел?
Подходит последовательность нечётных чисел с шагом : это различных чисел, все в границах, каждое следующее на меньше предыдущего.
Ответ а):
б) Может ли быть различных чисел?
Возьмём все нечётные числа от до с шагом (их ), затем удвоим последнее: , и пойдём по чётным с шагом : (ещё чисел). Всего различных чисел; удвоение допустимо, так как .
Ответ б):
в) Наибольшее количество различных чисел
Пусть удвоение происходит у нечётного числа . Нечётные числа до удвоения идут только вниз (шаг или повтор), поэтому все они лежат между и , не более различных. После удвоения идёт чётное число ; дальше чётные числа можно уменьшать на и удваивать чётные (получаем числа до ). Поэтому все чётные числа лежат между и (число достигается только из ). Посчитаем:
Если удвоения нет, все числа одной чётности: нечётных не более , чётных не более . Итак, наибольшее возможное значение равно (при ).
Пример: нечётные ; затем (удвоили ); чётные вниз ; затем удвоили и получили ; и чётные вниз . Все числа в границах, различных чисел .
Ответ в):
Ответ:
Учебные материалы: Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи, под ред. В. О. Бугаенко, МЦНМО, 2008, Инварианты; Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи, под ред. В. О. Бугаенко, МЦНМО, 2008, Чётность