2014 dxdy logo

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

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




 
 10 различных цифр в числе, задача 739 из "Putnam and beyond"
Сообщение01.03.2011, 23:16 
Для каждого простого числа $p$ существует бесконечно много натуральных чисел, кратных $p$, у каждого из которых все последние 10 цифр (в десятичной записи) являются попарно различными. Доказать.

Я предлагаю следующее решение:

(Оффтоп)

Рассмотрим бесконечную (в одну сторону) арифметическую прогрессию, состоящую из всех натуральных чисел вида $k\cdot10^{10}+9876543210$, где $k$ - ЦНЧ (целое неотрицательное число).

Все члены элементы этой прогрессии кратны двум и пяти, так что для $p=2$ и для $p=5$ задача уже решена.

Если $p$ отличается от 2 и 5, то разность прогрессии взаимно проста с $p$, следовательно в прогрессии встретятся все возможные остатки при делении на $p$ (это надо здесь доказывать? а на олимпиаде?), причём каждый из них - бесконечно много раз.

Вроде, всё?


В книге "Putnam and beyond" предлагаются два иных решения, одно из которых опирается на МТФ.

 
 
 
 Re: 10 различных цифр в числе, задача 739 из "Putnam and beyond"
Сообщение02.03.2011, 08:45 
Xenia1996 писал(а):
Если $p$ отличается от 2 и 5, то разность прогрессии взаимно проста с $p$, следовательно в прогрессии встретятся все возможные остатки при делении на $p$ (это надо здесь доказывать? а на олимпиаде?), причём каждый из них - бесконечно много раз.

Ну можно доказать, но это факт простой. На олимпиаде - желательно, жюри докопается.

-- Ср мар 02, 2011 11:47:48 --

По-моему, у Вас достаточно простое решение, вряд ли стоит выдумывать более сложное :wink:

 
 
 
 Re: 10 различных цифр в числе, задача 739 из "Putnam and beyond"
Сообщение02.03.2011, 10:29 
МТФ наверное как раз используется для доказательства этого факта. Попробуйте его явно доказать - Вам полезно будет :-)

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


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