2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 Re: Квадрирующая машина
Сообщение28.05.2014, 18:48 
Аватара пользователя
LebedKun в сообщении #868777 писал(а):
Вычислительная машина может выполнять только 2 операции: возвести текущее число в квадрат и вычесть из текущего числа $k$ (после выполнения операции получившееся число заменяет текущее в ячейке). При каких натуральных $k$ и $x$ можно получить соседнее числу $x$ число (т.е. получить из числа $x$ число $x\pm1$)?
$x=3,\  k=5$ подойдут? :D

 
 
 
 Re: Квадрирующая машина
Сообщение28.05.2014, 19:02 
Аватара пользователя
Требуется, чтобы для данных $x, k$ можно было получить и $x-1$, и $x+1$?

 
 
 
 Re: Квадрирующая машина
Сообщение28.05.2014, 19:13 
Аватара пользователя
svv в сообщении #868880 писал(а):
Требуется, чтобы для данных $x, k$ можно было получить и $x-1$, и $x+1$?
Минуса я че-то не разглядел сначала...

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

 
 
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 09:10 
Промежуточное значение не может быть отрицательным ($t\geq0$).

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

 
 
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 09:32 
Аватара пользователя
svv в сообщении #868880 писал(а):
Требуется, чтобы для данных $x, k$ можно было получить и $x-1$, и $x+1$?

 
 
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 09:45 
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$.

 
 
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 12:32 
Аватара пользователя
Задача делится на 2 подзадачи:
1) Решение в $\mathbb{Z}/k\mathbb{Z}$.
2) Подъем решения из $\mathbb{Z}/k\mathbb{Z}$ до решения в $\mathbb{Z}$.

 
 
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 14:01 
LebedKun в сообщении #869100 писал(а):
Моё решение:
А что такое $t$ в вашем решении?

 
 
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 14:15 
Аватара пользователя
LebedKun в сообщении #869087 писал(а):
Нафиг тему было переносить в другой раздел? Я сам знаю, как решить задачу.
 !  LebedKun, замечание за обсуждение действий модератора в тематическом разделе.

 
 
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 17:06 
$t$ - значение промежуточной ячейки

 
 
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 17:13 
Как она связана с $x$?

 
 
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 17:14 
venco, $x$ - исходное число.

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group