квадраты

[avva]

Красивая задачка. Ведущий загадывает натуральное число n и дает Алисе и Боб бумажки с числами n и n^2 (n в квадрате), но случайным образом решает, кто из них получает n, а кто n^2. После этого Алиса показывает Бобу либо белую карточку, либо черную карточку, а Боб, увидев это, правильно говорит, какое число написано у Алисы. Как Алиса и Боб

Comments

[ext_851488]

Идея чет-нечет количества полных пар возможных шагов "вниз"
Пример по степеням двойки (в скобках цвет того, что алиса должна показать бобу):
2^(2^0)=2^1=2 -- 0 шагов вниз (ч)
2^(2^1)=2^2=4 -- 1 шаг вниз (ч)
2^(2^2)=2^4=16 -- 2 шага вниз (б)
2^(2^3)=2^8=256 -- 3 шага вниз (б)
2^(2^4)=2^16=65536 -- 4 шага вниз (ч)
2^(2^5)... (ч)
2^(2^6)... (б)
2^(2^7)... (б)

если б была тройка 3^(2^7)... (б)
если б была семёрка 7^(2^7)... (б)
если б была "туз" 11^(2^7)... (б)

Боб смотрит на бамаську и решает, что бы показала алиса если б у неё была сиё число в квадрате и что если б корень из этого числа и после когда алиса показывает свой цвет однозначно ясно куда идти -- возводить в квадрат или брать корень.

[anonymous]

Полностью не продумал, но:
оба получают числа вида k^(2^m), где - не квадрат. Задача Боба - определить, зная свое m, что у Алисы: m+1 или m-1. Алиса может подсказать ему остаток от деления своего числа на 4 (белый - четный остаток, черный - нечетный, например). Должно быть достаточно.

[kaathewise]

Решил задачку за 5 секунд, но потом 5 минут думал, как короче всего записать ответ :)

Пусть у Алисы число a^(2^q), где q максимально, тогда она говорит Бобу q // 2 % 2.

Надо просто заметить, что задачу можно свести к той, где бы у них были написаны числа n и n+1, и что в ней ответ n // 2 % 2.

[ivan_semushin]

Алиса берёт минимальный простой делитель своего числа, пусть он входит в разложение её числа с показателем m*5^k, где m не делится на 5. Если остаток от деления m на 5 - 1 или 2, то Алиса показывает белую карточку, а если 3 или 4 - то чёрную.

Боб, чтобы узнать, какое число у Алисы, может проделать то же самое для своего числа. Полученное им число m1 будет отличатся от Алисиного в два раза, и зная свой остаток и то, к какой паре принадлежит остаток Алисы, он сможет понять, m = 2*m1 или 2*m = m1.

[anonymous]

Алиса должна посчитать сколько раз можно извлечь корень. Поделить это число на 4 и если остаток 0 или 1, показать белую карточку, а если 2 или 3, то черную.