квадраты

[avva]

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

Comments

[karachee]

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

[p_k]

Пусть k(x) - максимальное натуральное число, такое что из x извлекается корень степени 2^k. Если Алиса получила бумажку с числом a, она показывает белую карточку, если k(a) по модулю 4 равно 0 или 1, и черную карточку в противоположном случае. Боб получив число b, вычисляет k(b), и зная, что |k(b)-k(a)|=1 и цвет показанной карточки, получает также и знак k(b)-k(a). Если он положительный, то у него n^2, если отрицательный - то у него n.

[katyat]

Кто работает, а кто задачи решает, твой ответ первый, мой ответ на второй странице!

[anonymous]

Белый или черный в зависимости от остатка по модулю 4 от максимального количества раз, которое можно последовательно извлечь квадратный корень. Т.е. находим максимальное k, для которого n^(1/2^k) - целое, и смотрим на четность целой части k/2.

Например, если А. получила...
3,2,17, etc. => k=0 => белая
4 => k=1 => белая
16 => k=2 => черная
256 => k=3 => черная

Четность самого k будет чередоваться у Б. и А. независимо ни от чего. Четность половины k, т.е. цвет карточки, будет меняться в зависимости от того, у А. большее или меньшее число. Зная свое k, Б. по цвету карточки определит k Алисы.

[alexa_uk]

Общий принцип - Алиса раскладывает свое число на простые множители, берет степень минимального множителя и сообщает Бобу четность остатка от деления этой степени на 5

т.е. для 4 (2^2) это будет "чет", для 256 (2^8) - "нечет"

Боб соостветственно считает четность и нечетность этого остатка для квадрата и корня своего числа, и дает правильный ответ.

Если у Боба не квадрат, то он сразу знает правильный ответ.

Если n=1, то, видимо, любой ответ правильный.

[karpion]

Алиса раскладывает свое число на простые множители, берет степень минимального множителя
Дадим Алисе число 2^16*3^2.

[alexa_uk]

И?
16 % 5 == 1, нечет

[karpion]

Простите, а почему на пять, а не на семь или одиннадцать?

Все отвечавшие сошлись на том, что для данного числа ключевым будет степень при тройке.

[celen_me]

Алиса и Боб представляют свои числа в форме
x^(2^a) и x^(2^b) соответственно таким образом, что x - не квадрат, a,b >= 0. Понятно, что такое представление единственно, и x совпадут у них без согласования.

Алиса вычисляет (a(a+1)/2)%2. Результат кодируется карточкой и сообщается Бобу. Например, 0 - черный, 1 - белый.

Боб, вычисляет (b(b-1)/2)%2, и сравнивает свой остаток с остатком Алисы. Если они совпадают, то a = b-1 , если нет a = b+1 . Возведя в нужную степень, Боб говорит число.