Каталог по источникам

Задачи

Страница: << 1 2 3 4 5 6 >> [Всего задач: 30]

Задача 60909 (#05.071)

Темы:	[	Системы счисления (прочее)	]
Темы:	[	Индукция (прочее)	]

Сложность: 3+
Классы: 8,9,10

Докажите, что каждое целое число A представимо в виде

A = a₀ + 2a₁ + 2²a₂ +...+ 2ⁿa_n,

где каждое из чисел a_k = 0, 1 или -1 и a_ka_{k + 1} = 0 для всех 0 $\leqslant$ k $\leqslant$ n - 1, причем такое представление единственно.

Прислать комментарий

Решение

Задача 60910 (#05.072)

Темы:	[	Необычные конструкции	]
Темы:	[	Троичная система счисления	]

Сложность: 4
Классы: 9,10,11

Множество Кантора. Отрезок числовой оси от 0 до 1 покрашен в зеленый цвет. Затем его средняя часть — интервал (1/3;2/3) перекрашивается в красный цвет, потом средняя часть каждого из оставшихся зелеными отрезков тоже перекрашивается в красный цвет, с оставшимися зелеными отрезками проделывается та же операция и так до бесконечности. Точки, оставшиеся зелеными, образуют множество Кантора.
а) Найдите сумму длин красных интервалов.
б) Докажите, что число 1/4 останется окрашенным в зеленый цвет.
в) Из суммы

$\displaystyle {\textstyle\dfrac{2}{3}}$ + $\displaystyle {\textstyle\dfrac{2}{9}}$ + $\displaystyle {\textstyle\dfrac{2}{27}}$ + $\displaystyle {\textstyle\dfrac{2}{81}}$ +...

произвольным образом вычеркнуты слагаемые. Докажите, что сумма оставшихся слагаемых — зеленое число.

Прислать комментарий

Решение

Задача 60911 (#05.073)

[Последовательность Морса]

Темы:	[	Периодичность и непериодичность	]
	[	Итерации	]
	[	Двоичная система счисления	]

Сложность: 5
Классы: 8,9,10,11

Последовательность Морса. Бесконечная последовательность из нулей и единиц

0110 1001 1001 0110 1001...

построена по следующему правилу. Сначала написан нуль. Затем делается бесконечное количество шагов. На каждом шаге к уже написанному куску последовательности приписывается новый кусок той же длины, получаемый из него заменой всех нулей единицами, а единиц — нулями.
а) Какая цифра стоит на 2001 месте?
б) Будет ли эта последовательность, начиная с некоторого места, периодической?
в) Докажите, что данная последовательность переходит в себя при замене каждого нуля на комбинацию 01, а каждой единицы — на комбинацию 10.
г) Докажите, что ни одно конечно слово из нулей и единиц не встречается в последовательности Морса три раза подряд.
д) Как, зная представление числа n в двоичной системе счисления, найти n-й элемент данной последовательности?

Прислать комментарий

Решение

Задача 60912 (#05.074)

Темы:	[	Теория алгоритмов (прочее)	]
	[	Двоичная система счисления	]
	[	Индукция (прочее)	]

Сложность: 4
Классы: 8,9,10

Ханойская башня и двоичная система счисления. Рассмотрим два процесса, каждый из которых состоит из 2⁸ - 1 шагов. Первый — это процесс решения головоломки ``Ханойская башня'' (смотри задачу 1.42) при помощи оптимального алгоритма. Второй — это процесс прибавления единицы, который начинается с 0 и заканчивается числом 2⁸ - 1. Опишите связь между этими двумя процессами.

Прислать комментарий

Решение

Задача 60913 (#05.075)

Темы:	[	Рекуррентные соотношения (прочее)	]
Темы:	[	Двоичная система счисления	]

Сложность: 4
Классы: 8,9,10,11

Задача Иосифа Флавия. n человек выстраиваются по кругу и нумеруются числами от 1 до n. Затем из них исключается каждый второй до тех пор, пока не останется только один человек. Например, если n = 10, то порядок исключения таков: 2, 4, 6, 8, 10, 3, 7, 1, 9, так что остается номер 5. Для данного n будем обозначать через J(n) номер последнего оставшегося человека. Докажите, что
а) J(2n) = 2J(n) - 1;
б) J(2n + 1) = 2J(n) + 1;
в) если n = (1b_{m - 1}b_{m - 2}...b₁b₀)₂, то J(n) = (b_{m - 1}b_{m - 2}...b₁b₀1)₂.

Прислать комментарий

Решение

Страница: << 1 2 3 4 5 6 >> [Всего задач: 30]