Бесконечные алгоритмы



жүктеу 39.75 Kb.
Дата03.07.2018
өлшемі39.75 Kb.

Бесконечные алгоритмы


Рабочий несет домой со стройки один кирпич. – Что ж всего один-то? – удивляется охранник. – А я не ленивый, еще не раз схожу…

Алгоритм может последовательно проверять по одной бесконечную цепочку гипотез, пока одна из них не окажется верной.

  1. Состав из конечного числа одинаковых вагонов замкнут в кольцо. Тебя с куском мела поместили в один из вагонов. Ты можешь свободно ходить по составу и делать любые пометки на стенах вагонов. В какой-то момент ты должен сказать, сколько вагонов в поезде. Однако попытка у тебя всего одна. Если угадаешь, то тебя выпустят (а иначе – конец). Учти, однако, что до тебя уже многие пытались пройти это испытание. Возможно, они оставляли на стенах какие-то пометки. Опиши алгоритм, который поможет спастись наверняка.

Бесконечный объект часто строят индуктивно, последовательно наращивая конечный объект. Обычно есть бесконечно много вариантов наращивания, а число запретов конечно в каждый момент.

  1. В таблице две строки и бесконечно много столбцов. В каждой строке и каждом столбце все числа различны. Докажите, что можно выбрать бесконечно много столбцов так, чтобы все числа в выбранных столбцах были различны.

Индуктивное построение может вестись группами, когда один из объектов группы – обязательный (например, минимальный из непостроенных), а остальные – вспомогательные.

  1. Петя построил последовательность из 2013 различных натуральных чисел, где для любого k≤2013 сумма первых k чисел делилась на k. Докажите, что последовательность можно продолжить до бесконечности с сохранением условия о делимости и так, чтобы каждое натуральное число встретилось ровно один раз.

Определение. Множество A счетно, если его элементы можно занумеровать натуральными числами.

  1. Счетны ли множества:
    а) целых чисел; б) клеток бесконечной во все стороны шахматной доски;
    в) рациональных чисел; г) конечных множеств натуральных чисел?

Индуктивное построение можно проводить с любым счетным множеством: достаточно только его пронумеровать.

  1. Бесконечная вправо и влево последовательность целых чисел называется биекцией, если в ней каждое целое число встречается ровно по одному разу. Докажите, что любую биекцию можно представить как сумму двух других биекций (последовательности складываются покоординатно).

Диагональный метод Кантора: на каждом шаге обеспечиваем отличие от объекта с очередным номером.

  1. Дано счетное множество различных двоичных последовательностей. Докажите, что можно написать двоичную последовательность, не входящую в это множество.

  2. Два бога по очереди выписывают цифры бесконечной десятичной дроби. Первый своим ходом приписывает в хвост любое конечное число цифр, второй – одну. Они успевают сделать все ходы (то есть, бесконечно много) за час. Если в итоге получится периодическая дробь (без предпериода), выигрывает первый, иначе – второй. Кто из них может выиграть, как бы ни играл соперник?

  3. Пусть дана бесконечная шахматная доска, в каждой клетке которой стоит натуральное число (числа могут повторяться). Идя королем по доске (возможно, с повторением клеток), и выписывая по порядку числа, мы получаем королевскую последовательность. Докажите, что для любой данной доски есть некоролевская последовательность.

Счетное множество разбивается на счетное число конечных множеств. В частности, счетное число отдельных «плохих» ходов можно заменить на счетное число «хороших» групп ходов.

  1. В целых точках прямой расположены ямы, шириной 0,01 каждая. Длина прыжков блохи постоянна и равна. Докажите, что блоха рано или поздно попадет в яму.

Для самостоятельного решения


БА1. Дан отрезок числовой оси. Два бога ходят по очереди. Каждым ходом от отрезка отрезается и отбрасывается правая или левая половинка. Когда игра закончится, остается общая точка всех отрезков. Если она рациональна, выигрывает первый, иначе – второй. У кого из них есть выигрышная стратегия?

БА2. Петя и Вася играют на бесконечной в обе стороны клетчатой полоске, вначале пустой. Ходят по очереди, начинает Петя. За ход Петя ставит два крестика в любые две пустые клетки. Вася за один ход стирает одну группу крестиков, идущую подряд без пробелов. Может ли Петя получить группу из не менее чем 2013 крестиков подряд?

БА3. Последовательность задана рекуррентной формулой xn+1=[xn]{xn}.
а) Докажите, что если x1>0, то начиная с некоторого места все члены равны 0.
б) Докажите, что |[ xn+1]||[xn]|
в) Докажите, что если –1<x1<0, то последовательность периодична с периодом длины 2.
г) Решите уравнение x=[x]{x}.
д) Докажите, что если xn<–1, то найдется какое-то xm, что m>n и [xn] [xm] (для этого рассмотрите, как ведет себя расстояние от xn до ближайшего решения уравнения из (г))?
е) Докажите, что последовательность периодична.

БА4. Назовем лабиринтом шахматную доску 8×8, где между некоторыми полями вставлены перегородки. По команде ВПРАВО ладья смещается на одно поле вправо или, если справа край доски или перегородка, остается на месте; аналогично выполняются команды ВЛЕВО, ВВЕРХ и ВНИЗ. Бог пишет программу – конечную последовательность указанных команд, и дает её чёрту, после чего чёрт выбирает лабиринт и помещает в него ладью на любое поле. Докажите, что бог может написать такую программу, что ладья обойдет все доступные поля в лабиринте при любом выборе чёрта.

БА5. Можно ли переставить числа натурального ряда в другом порядке так, чтобы сумма любых первых k чисел делилась на k+1-й член?

БА6. Рассмотрим последовательность, первые два члена которой равны 1 и 2 соответственно, а каждый следующий член – это наименьшее натуральное число, которое еще не встретилось в последовательности и которое не взаимно просто с предыдущим членом последовательности. Докажите, что каждое натуральное число входит в эту последовательность.

Барнаул 2014, 11 ноября. 10 класс, А.Шаповалов www.ashap.info/Uroki/Altaj/index.html

Достарыңызбен бөлісу:


©kzref.org 2017
әкімшілігінің қараңыз

    Басты бет