2014 dxdy logo

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

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




 
 Наличие и отсутствие общих простых делителей
Сообщение03.09.2018, 22:29 
Аватара пользователя
Доказать, что для любых натуральных $2\leqslant k < m\leqslant n$
найдутся $n$ таких натуральных чисел, что у любых $k$ из них есть хотя бы один общий простой делитель, а у любых $m$ из них общих простых делителей нет.

 
 
 
 Re: Наличие и отсутствие общих простых делителей
Сообщение03.09.2018, 22:45 
Аватара пользователя
Индукцией по $n$ доказывается тривиально (как и построением сразу в лоб). Можно ли устроить индукцию скажем по $k$ и $m$?..

 
 
 
 Re: Наличие и отсутствие общих простых делителей
Сообщение03.09.2018, 22:49 
Аватара пользователя
mihaild
А можете без индукции? Например, существуют ли такие 2018 натуральных чисел, что у любых трёх из них есть хотя бы один общий простой делитель, а у любых четырёх из них общих простых делителей нет?

 
 
 
 Re: Наличие и отсутствие общих простых делителей
Сообщение03.09.2018, 23:20 
Аватара пользователя
Подсказка: минимальное из этих чисел не меньше $p_{C_{2017}^2}\#$.

 
 
 
 Re: Наличие и отсутствие общих простых делителей
Сообщение03.09.2018, 23:25 
Аватара пользователя
Можно представить эти числа как $n$ вертикальных стопок; каждая горизонталь - определенное простое число, свое для каждой горизонтали. Положим на самую нижнюю горизонталь по золотой монетке для каких-нибудь $k$ чисел из $n$, и по серебряной для остальных. На вторую горизонталь положим $k$ золотых монеток на другие $k$ мест (не полностю совпадающих с предыдущими), а на остальные снова серебряные. Будем делать так, пока не построим $n$ стопок высотой $C_n^k$: для любых $k$ стопок найдется горизонталь с $k$ золотыми монетками в этих стопках, и ни на одной горизонтали нет более $k$ золотых монеток

 
 
 
 Re: Наличие и отсутствие общих простых делителей
Сообщение04.09.2018, 01:36 
Аватара пользователя
mihaild
waxtep
Большое спасибо!

 
 
 
 Re: Наличие и отсутствие общих простых делителей
Сообщение04.09.2018, 09:20 
Аватара пользователя
Можно воспользоваться следующими алгоритмом:
1) Возьмём массив $k$ одинаковых простых чисел $n_i$.
2) Добавим в него $x:=1$ и с каждым из $k-1$ домножим $x$ и $n_i$ на простое число, отличное от предыдущих.
3) Заменим числа из п.1 на полученные в п.2 и повторим процедуру.
Простых бесконечно много $\implies$ алгоритм реализуем. Массив растёт $\implies$ процедура конечна.

(Пример)

$n=4,\ k=3, \ m=4$
1) $[2_1, 2_2, 2_3]$
2) $[2_1, 2_2, 2_3]$: $3\cdot (1, 2_1, 2_2)$, $5\cdot (3, 2_1\cdot 3, 2_3)$, $7\cdot (3\cdot 5, 2_2\cdot 3, 2_3\cdot 5)$.
Повтор цикла:
1) Новый массив: $[30, 42, 70, 105]$
2) $[30, 42, 70, 105]$: $11\cdot (1, 30, 42)$, $13\cdot (11, 30\cdot 11, 70)$...


Не сложно написать программу для практических нужд.

 
 
 [ Сообщений: 7 ] 


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