Здравствуйте!

Не так давно столкнулся с двумя задачками, связанными с перестановками. Решить их у меня не получилось, но мне бы хотелось разобраться, как решать задачи такого типа за полиномиальное время. Прошу помощи.

1) Условие: Дано число n и массив b — некая перестановка чисел от 1 до n. Нужно найти какую-нибудь перестановку a (также из n элементов), чтобы для каждого i (1  ≤  i  ≤  n) выполнялось равенство b[a[a[i]]] = i. К примеру, если нам дана перестановка b = (3, 4, 1, 2), то в качестве ответа можно вывести перестановку a = (2, 3, 4, 1). Если искомой перестановки a не существует, вывести "0".

2) Условие: Из заданной перестановки нужно извлечь квадратный корень. Здесь можно прочесть полное условие этой задачи (задача P).

Заранее всем спасибо!

Здравствуйте)

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

Условие таково: доказать, что для любого натурального n ≥ 12 найдется такая перестановка чисел от 1 до n {π₁, π₂, π₃, ..., π_n}, что π_i + i является полным квадратом для любого 1 ≤ i ≤ n .

P.S. Заранее прошу прощения, если задача широко известна и где-то уже обсуждалась. Я не нашел.