2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Квадрирующая машина
Сообщение28.05.2014, 13:47 


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

 Профиль  
                  
 
 Posted automatically
Сообщение28.05.2014, 18:45 
Супермодератор
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение28.05.2014, 18:48 
Заслуженный участник
Аватара пользователя


11/12/05
9953
LebedKun в сообщении #868777 писал(а):
Вычислительная машина может выполнять только 2 операции: возвести текущее число в квадрат и вычесть из текущего числа $k$ (после выполнения операции получившееся число заменяет текущее в ячейке). При каких натуральных $k$ и $x$ можно получить соседнее числу $x$ число (т.е. получить из числа $x$ число $x\pm1$)?
$x=3,\  k=5$ подойдут? :D

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение28.05.2014, 19:02 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение28.05.2014, 19:13 
Заслуженный участник
Аватара пользователя


11/12/05
9953
svv в сообщении #868880 писал(а):
Требуется, чтобы для данных $x, k$ можно было получить и $x-1$, и $x+1$?
Минуса я че-то не разглядел сначала...

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение28.05.2014, 19:16 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 09:10 


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

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

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 09:32 
Заслуженный участник


23/07/08
10626
Crna Gora
svv в сообщении #868880 писал(а):
Требуется, чтобы для данных $x, k$ можно было получить и $x-1$, и $x+1$?

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 09:45 


12/10/13
99
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 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 14:01 
Заслуженный участник


04/05/09
4582
LebedKun в сообщении #869100 писал(а):
Моё решение:
А что такое $t$ в вашем решении?

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 14:15 
Админ форума
Аватара пользователя


19/03/10
8952
LebedKun в сообщении #869087 писал(а):
Нафиг тему было переносить в другой раздел? Я сам знаю, как решить задачу.
 !  LebedKun, замечание за обсуждение действий модератора в тематическом разделе.

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 17:06 


12/10/13
99
$t$ - значение промежуточной ячейки

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 17:13 
Заслуженный участник


04/05/09
4582
Как она связана с $x$?

 Профиль  
                  
 
 Re: Квадрирующая машина
Сообщение29.05.2014, 17:14 


12/10/13
99
venco, $x$ - исходное число.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group