Каталог по темам

Задачи

Страница: 1 2 >> [Всего задач: 7]

Задача 60914

Тема:

[

Ним-сумма

]

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

Ним-сумма. Будем говорить, что число n является ним-суммой чисел m и k ( m $\oplus$ k = n), если оно получается из чисел m и k после следующих преобразований.
1) m и k записываются в двоичной системе счисления

m = (m_s...m₁m₀)₂, k = (k_s...k₁k₀)₂

(меньшее число дополняется спереди нулями).
2) Полученные наборы цифр как векторы складываются покомпонентно по модулю 2:

(m_s,..., m₁, m₀) + (k_s,..., k₁, k₀) $\displaystyle \equiv$ (n_s,..., n₁, n₀)(mod 2).

3) Набор цифр (n_s,..., n₁, n₀) переводится в число n:

(n_s...n₁n₀)₂ = n.

Например, 4 $\oplus$ 7 = 3, так как

4 = (100)₂, 7 = (111)₂, (1, 0, 0) + (1, 1, 1) $\displaystyle \equiv$ (0, 1, 1)(mod 2), (011)₂ = 3.

Докажите, что ним-сумма удовлетворяет следующим свойствам:
а) m $\oplus$ m = 0; б) m $\oplus$ k = k $\oplus$ m; в) (m $\oplus$ t) $\oplus$ k = m $\oplus$ (t $\oplus$ k);
г) если n $\ne$ 0 и

m₁ $\displaystyle \oplus$ m₂ $\displaystyle \oplus$ ... $\displaystyle \oplus$ m_l = n,

(5.1)

то найдется такой номер j ( 1 $\leqslant$ j $\leqslant$ l), для которого m_j $\oplus$ n < m_j.

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

Решение

Задача 60916

Темы:	[	Ним-сумма	]
Темы:	[	Инварианты	]

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

Марсианские амебы II. При помощи ним-сумм (смотри задачу 5.76) можно исследовать самые разные игры и процессы. Например, можно получить еще одно решение задачи 4.20.
Постройте на множестве марсианских амеб {A, B, C} функцию f, для которой выполнялись бы равенства

f (A) $\displaystyle \oplus$ f (B) = f (C), f (A) $\displaystyle \oplus$ f (C) = f (B), f (B) $\displaystyle \oplus$ f (C) = f (A).

Какие рассуждения остается провести, чтобы решить задачу про амеб?

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

Решение

Задача 60917

Темы:	[	Ним-сумма	]
Темы:	[	Теория игр (прочее)	]

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

Проанализируйте при помощи ним-сумм игру ``Йога'' из задачи 4.21.

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

Решение

Задача 60915

[Игра "Ним"]

Темы:	[	Ним-сумма	]
Темы:	[	Выигрышные и проигрышные позиции	]

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

Игра ``Ним''. Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять любое (ненулевое) количество камней, но только из одной кучки. Выигрывает тот, кто взял последний камень. Для анализа игры каждому набору кучек камней m₁, m₂, ..., m_l поставим в соответствие его ним сумму (5.1 ).
а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, то в результате получается позиция с ним-суммой n $\ne$ 0.
б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой n = 0.
в) Опишите выигрышную стратегию в игру ``Ним''.
г) Какой следует сделать ход, если перед вами три кучки: 3, 4 и 5 камней?

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

Решение

Задача 104031

Темы:	[	Выигрышные и проигрышные позиции	]
Темы:	[	Ним-сумма	]

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

а) На столе лежат 111 спичек. Маша и Даша по очереди берут со стола по несколько спичек, но не больше десяти за один раз. Выигрывает тот, кто возьмет последнюю спичку. Кто победит при правильной игре?
б) На полу лежат три кучки - из 3, 4 и 5 спичек. Теперь Маша и Даша за один раз могут взять любое количество спичек, но только из одной кучки. Кто выиграет на этот раз?

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

Страница: 1 2 >> [Всего задач: 7]