Главы:
-
глава 1. Метод математической индукции
(59 задач)
глава 2. Комбинаторика
(110 задач)
глава 3. Алгоритм Евклида и основная теорема арифметики
(173 задачи)
глава 4. Арифметика остатков
(209 задач)
глава 5. Числа, дроби, системы счисления
(85 задач)
глава 6. Многочлены
(141 задача)
глава 7. Комплексные числа
(97 задач)
глава 8. Алгебра + геометрия
(90 задач)
глава 9. Уравнения и системы
(100 задач)
глава 10. Неравенства
(76 задач)
глава 11. Последовательности и ряды
(99 задач)
глава 12. Шутки и ошибки
(15 задач)
Фильтр
Выбрана 1 задача
Версия для печати
Убрать все задачи
Задача Иосифа Флавия. 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 = (1bm - 1bm - 2...b1b0)2, то J(n) = (bm - 1bm - 2...b1b01)2.
Решение
Убрать все задачи
Задача Иосифа Флавия. 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 = (1bm - 1bm - 2...b1b0)2, то J(n) = (bm - 1bm - 2...b1b01)2.
Решение
Задачи
Страница: << 123 124 125 126 127 128 129 >> [Всего задач: 1255]
Задача Иосифа Флавия.
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 = (1bm - 1bm - 2...b1b0)2, то J(n) = (bm - 1bm - 2...b1b01)2.
Ним-сумма. Будем
говорить, что число n является ним-суммой чисел m и k
(
m 
k = n), если оно получается из чисел m и k после
следующих преобразований.
1) m и k записываются в двоичной системе счисления
2) Полученные наборы цифр как векторы складываются покомпонентно по модулю 2:
Например, 4 7 = 3, так как
а) m m = 0; б)
m k = k m; в)
(m t) k = m (t k);
г) если n
0 и
то найдется такой номер j ( 1
j l), для которого
mj n < mj.
Игра ``Ним''. Имеется несколько кучек камней. Двое по очереди берут из
них камни. За один ход разрешается взять любое (ненулевое)
количество камней, но только из одной кучки. Выигрывает тот, кто
взял последний камень.
Для анализа игры каждому набору кучек камней m1, m2, ...,
ml поставим в соответствие его ним сумму (5.1
).
а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, то в результате получается позиция с ним-суммой n
0.
б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой n = 0.
в) Опишите выигрышную стратегию в игру ``Ним''.
г) Какой следует сделать ход, если перед вами три кучки: 3, 4 и 5 камней?
Марсианские
амебы II. При помощи ним-сумм (смотри задачу 5.76) можно исследовать самые разные
игры и процессы. Например, можно получить еще одно решение
задачи 4.20.
Постройте на множестве марсианских амеб {A, B, C} функцию f, для которой выполнялись бы равенства
Проанализируйте при помощи ним-сумм игру
``Йога''
из
задачи 4.21.
Страница: << 123 124 125 126 127 128 129 >> [Всего задач: 1255]
Задача 60913 (#05.075) |
|
|
а) J(2n) = 2J(n) - 1;
б) J(2n + 1) = 2J(n) + 1;
в) если n = (1bm - 1bm - 2...b1b0)2, то J(n) = (bm - 1bm - 2...b1b01)2.
|
|
|
Решение |
Задача 60914 (#05.076) |
|
|
1) m и k записываются в двоичной системе счисления
m = (ms...m1m0)2, k = (ks...k1k0)2
(меньшее
число дополняется спереди нулями).
2) Полученные наборы цифр как векторы складываются покомпонентно по модулю 2:
(ms,..., m1, m0) + (ks,..., k1, k0) 
(ns,..., n1, n0)(mod 2).
3) Набор цифр
(ns,..., n1, n0) переводится в число n:
(ns...n1n0)2 = n.
Например, 4
4 = (100)2, 7 = (111)2, (1, 0, 0) + (1, 1, 1) (0, 1, 1)(mod 2), (011)2 = 3.
Докажите, что ним-сумма удовлетворяет следующим свойствам:
а) m
г) если n
то найдется такой номер j ( 1
|
|
Решение |
Задача 60915 (#05.077)[Игра "Ним"] |
|
|
а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, то в результате получается позиция с ним-суммой n
б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой n = 0.
в) Опишите выигрышную стратегию в игру ``Ним''.
г) Какой следует сделать ход, если перед вами три кучки: 3, 4 и 5 камней?
|
|
|
Решение |
Задача 60916 (#05.078) |
|
|
Постройте на множестве марсианских амеб {A, B, C} функцию f, для которой выполнялись бы равенства
f (A) 
f (B) = f (C), f (A) f (C) = f (B), f (B) f (C) = f (A).
Какие рассуждения остается провести, чтобы решить задачу про амеб?
|
|
|
Решение |
Задача 60917 (#05.079) |
|
|
|
|
|
Решение |
Страница: << 123 124 125 126 127 128 129 >> [Всего задач: 1255]
