2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Любое ли число можно получить?
Сообщение27.10.2023, 20:35 
Аватара пользователя


27/10/23
9
Доброго времени суток! Задача такая.
------------------
Есть число 1. К имеющемуся числу можно применять следующие операции:
А) Умножить на любое натуральное число от 2 до 100 (включительно) и прибавить к произведению 1.
Б) Разделить число на его наименьший отличный от 1 делитель.

Любое ли натуральное число можно получить такими операциями?
------------------

Я пытался доказать, что $100! + 2$ нельзя получить. Это число нельзя получить операцией А, но можно получить операцией Б. Поэтому ничего не понятно.

Потом пытался доказать, что любое можно. Можно получить любое число вида $2^n - 1$. Любое нечётное число делит какое-то число такого вида. Но тут тоже не ясно.

Буду признателен за помощь!

 Профиль  
                  
 
 Posted automatically
Сообщение27.10.2023, 21:40 
Админ форума


02/02/19
2537
 i  Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы)

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Posted automatically
Сообщение27.10.2023, 22:45 
Админ форума


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

 Профиль  
                  
 
 Re: Любое ли число можно получить?
Сообщение27.10.2023, 23:13 
Заслуженный участник
Аватара пользователя


26/02/14
562
so dna
Pythagoras в сообщении #1614968 писал(а):
Есть число 1. К имеющемуся числу можно применять следующие операции:
А) Умножить на любое натуральное число от 2 до 100 (включительно) и прибавить к произведению 1.
Б) Разделить число на его наименьший отличный от 1 делитель.

Любое ли натуральное число можно получить такими операциями?

Не заметил сразу, что задачу переместили в другой раздел...
Рассмотрите какое-нибудь число, делящееся на все числа от $1$ до $100$.

 Профиль  
                  
 
 Re: Любое ли число можно получить?
Сообщение28.10.2023, 22:30 
Аватара пользователя


27/10/23
9
Rak so dna в сообщении #1614984 писал(а):
Рассмотрите какое-нибудь число, делящееся на все числа от $1$ до $100$.

Спасибо, понятно! Всё было так легко :-) :facepalm:

 Профиль  
                  
 
 Re: Любое ли число можно получить?
Сообщение31.10.2023, 00:07 


02/04/18
240
Интересно, какое наименьшее нельзя получить? Верхняя граница, как уже ясно из вышесказанного, это произведение всех простых, меньших $100$, то есть $c=2\cdot3\cdot...\cdot97\approx3,2\cdot10^{211}$. А есть ли меньше?

Обозначим наименьшее число $a\le c$. Наименьший простой делитель $p$ числа $a-1$ должен быть больше ста: $p>100$, в противном случае $a$ получается из $\frac{a-1}{p}<a$, а по гипотезе такое число может быть получено. Собственно, для $c$ это выполняется. Но тогда $a-1$ - нечетно, то есть $a$ - четно.

Это число не может быть получено операцией Б, то есть из числа $qa$, где $q$ - наименьший делитель числа $qa$. Но в силу четности, это двойка. Значит, мы не сможем получить число $2a$, и вообще $2^na$ для любого $n$. В противном случае мы бы получили и $a$.
Рассмотрим число $2a-1$. Мы знаем, что $a-1$ не делится на $3$.

Пусть оно равно $3k+1$, тогда $a=3k+2, 2a-1=6k+3$, то есть $2a$ получается из $2k+1<3k+2=a$ операцией А. Однако число $2k+1$ мы можем получить по нашей гипотезе ($a$ - наименьшее невозможное).
Если же оно равно $3k-1$, тогда $a=3k$, $2a-1=6k-1$, и противоречий нет. Уже получаем, что $a$ кратно $6$.

$a-1$ не делится на 5, то есть имеет место одно из значений: $a=5k, 5k+2, 5k+3, 5k+4$. Но лучше использовать делимость на 6 и записать $30k, 30k+12, 30k+18, 30k+24$
$2a-1, 4a-1$ не могут делиться на 5, так что исключим третий и четвертый случаи и сосредоточимся на втором. $8a=240k+96$, и это число может быть получено из $48k+19$, а оно, в свою очередь, из $16k+6<a$, которое точно может быть получено в силу нашей гипотезы. Таким образом, $a$ должно делиться на $30$.

Кажется, что так мы может дойти и до $c$, как минимального. Но с семеркой эти рассуждения уже не работают, соответственно, обобщать не так-то просто, как кажется.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

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



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

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


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

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