Квадрирующая машина

[LebedKun]

Вычислительная машина может выполнять только 2 операции: возвести текущее число в квадрат и вычесть из текущего числа $k$ (после выполнения операции получившееся число заменяет текущее в ячейке). При каких натуральных $k$ и $x$ можно получить соседнее числу $x$ число (т.е. получить из числа $x$ число $x\pm1$)?

[Deggial]

Тема перемещена из форума «Загадки, головоломки, ребусы» в форум «Помогите решить / разобраться (М)»
Причина переноса: это - математическая задача, не очень простая, но и не очень сложная. Кто считает, что я неправ (например, я не перенёс тему в Карантин) - выслушаю в ЛС или через механизм жалоб.

LebedKun, приведите попытки решения, для порядка.

[Dan B-Yallay]

LebedKun в сообщении #868777 писал(а):

Вычислительная машина может выполнять только 2 операции: возвести текущее число в квадрат и вычесть из текущего числа $k$ (после выполнения операции получившееся число заменяет текущее в ячейке). При каких натуральных $k$ и $x$ можно получить соседнее числу $x$ число (т.е. получить из числа $x$ число $x\pm1$)?

$x=3,\ k=5$ подойдут?

[svv]

Требуется, чтобы для данных $x, k$ можно было получить и $x-1$, и $x+1$?

[Dan B-Yallay]

svv в сообщении #868880 писал(а):

Требуется, чтобы для данных $x, k$ можно было получить и $x-1$, и $x+1$?

Минуса я че-то не разглядел сначала...

[svv]

С $k=1$ мы почти ($x\neq 1$) всесильны.
А если ещё и допускаются отрицательные числа... (т.е. $k$ и $x$ натуральные, но кто сказал, что промежуточные результаты тоже должны быть натуральные?)

[LebedKun]

Промежуточное значение не может быть отрицательным ($t\geq0$).

З.Ы. Нафиг тему было переносить в другой раздел? Я сам знаю, как решить задачу.

[svv]

svv в сообщении #868880 писал(а):

Требуется, чтобы для данных $x, k$ можно было получить и $x-1$, и $x+1$?

[LebedKun]

svv, требуется, чтобы хотя бы одно соседнее число получилось.


Моё решение:

1. $k=1$ - очевидный случай. Всё сводится к решению уравнения $t^2-n=t\pm1$
$t^2-t-n\mp1=0$
$t^2-t-(n\pm1)=0$
$n=t^2-t\mp1$
Многочлен принимает принимает неотрицательные значения при любом $t\neq1$, значит при любом $x$ и $k=1$ можно получить соседнее число.

2. $k>1$:
Опять же всё сводится к решению уравнения $t^2-kn=t\pm1$
$n=\frac{t^2-t\mp1}{k}$

2.1. $k$ - чётное:
Пусть $k=2m$, тогда $n=\frac{t^2-t\mp1}{2m}=\frac{t(t-1)\mp1}{2m}$. Число $t(t-1)$ - чётное (т.к. произведение чётного и нечетного числа - число чётное), значит значение многочлена $t^2-t\mp1$ - число нечётное. Значит нельзя получить соседних чисел при любом $x$ и $k$ чётном (соседние числа противоположны по признаку чётности).

2.2. $x$ кратно $k$:
Пусть $t=kl$, тогда $n=\frac{(kl)^2-kl\mp1}{k}=\frac{k^2l^2-kl\mp1}{k}=\frac{kl(kl-1)\mp1}{k}$. Число $kl(kl-1)$ кратно $k$, следовательно значение многочлена $t^2-t\mp1$ не кратно $k$ (т.к. при $k>1$ соседнее число даёт в остатке $1$ при делении на $k$). Значит нельзя получить ни одно соседнее число при $x$ кратном $k$

2.3. В остальных случаях значение многочлена $t^2-t\mp1$ должно быть кратно $k$ ($n$ должен быть целым).

Замечание: если $k$ - нечётное, а $x$ не кратно $k$, то $x^2$ не кратно $k$, и наоборот. Если $k$ - нечётное и $x$ при делении на $k$ даёт остаток $q$, то $x-k$ при делении на $k$ даёт тот же остаток $q$.

[Deggial]

Задача делится на 2 подзадачи:
1) Решение в $\mathbb{Z}/k\mathbb{Z}$.
2) Подъем решения из $\mathbb{Z}/k\mathbb{Z}$ до решения в $\mathbb{Z}$.

[venco]

LebedKun в сообщении #869100 писал(а):

Моё решение:

А что такое $t$ в вашем решении?

[Toucan]

LebedKun в сообщении #869087 писал(а):

Нафиг тему было переносить в другой раздел? Я сам знаю, как решить задачу.

LebedKun, замечание за обсуждение действий модератора в тематическом разделе.

[LebedKun]

$t$ - значение промежуточной ячейки

[venco]

Как она связана с $x$?

[LebedKun]

venco, $x$ - исходное число.