Теория чисел. Хитрые, но школьные задачи.

[lampard]

1) Натуральное число удалось разложить на 100 сомножителей, больших единицы, двумя способами так, что ни один из сомножителей первого разложения не совпадает ни с одним из сомножителей второго. Докажите, что это число можно разложить на 150 сомножителей (не обязательно различных), больших единицы.

$N=n_1\cdot n_2\cdot ....\cdot n_{100}=k_1\cdot k_2\cdot ...\cdot k_{100}$

Если нам удалось разложить на $100$ различных сомножителей дважды, то среди набора $n_1,n_2,...,n_{100},k_1,...k_{100}$ есть по-крайней мере $100$ составных чисел, каждое из которых можно представить в виде произведения двух других.
Возьмем набор из $100$ составных чисел. Разложим эти составные числа на множители, тогда получится минимум $200$ сомножителей. Верна ли эта идея? Если не верна, то пните, пожалуйста, в нужном направлении!

2) Каких чисел больше среди чисел от $1$ до $10^{20}$: с суммой цифр $115$ или с суммой цифр $65$?

Тут вообще не понимаю с чего начать. Есть только идея, что количество цифр у нас не более $20$, потому $65$ организовать будет проще, на первый взгляд, наверное, это и есть ответ, но это только догадки, обосновать не могу

[Korvin]

lampard в сообщении #1013123 писал(а):

...

2) Каких чисел больше среди чисел от $1$ до $10^{20}$: с суммой цифр $115$ или с суммой цифр $65$?

Тут вообще не понимаю с чего начать. Есть только идея, что количество цифр у нас не более $20$, потому $65$ организовать будет проще, на первый взгляд, наверное, это и есть ответ, но это только догадки, обосновать не могу

Цифр 20, если отсутствующие в начале числа цифры считать нулями, и любая цифра пробегает значения от 0 до 9, средняя 4,5, и средняя сумма цифр 90. Распределение суммы цифр симметричное, отсюда 65 и 115 встречаются одинаково часто.

[svv]

Ага. Если сумма цифр числа $x$ равна $65$, то сумма цифр числа $y=99999999999999999999-x$ будет $9\cdot 20-65=115$, и наоборот.

[Korvin]

svv в сообщении #1013258 писал(а):

Ага. Если сумма цифр числа $x$ равна $65$, то сумма цифр числа $y=99999999999999999999-x$ будет $9\cdot 20-65=115$, и наоборот.

Но из приведенного не следует, что чисел с суммой цифр 90-x$ будет ровно столько, сколько с суммой цифр 90+x$. А если считать распределение нормальным как сумму 20 прямоугольных распределений, то можно и сигму посчитать и вероятности каждой суммы цифр. Понятно, учитывая приближенный характер замены дискретного распределения непрерывным.

[Cash]

Korvin в сообщении #1013431 писал(а):

Но из приведенного не следует, что чисел с суммой цифр 90-x$ будет ровно столько, сколько с суммой цифр 90+x$.

Следует, следует. Про взаимно-однозначные соответствия слыхали? Получается при этом математически строго. В отличии от Вашего мутного рассуждения.

[lampard]

Спасибо, со второй задачей понятно все. А как к первой подступиться?

[Korvin]

Cash в сообщении #1013439 писал(а):

Korvin в сообщении #1013431 писал(а):

Но из приведенного не следует, что чисел с суммой цифр 90-x$ будет ровно столько, сколько с суммой цифр 90+x$.

Следует, следует. Про взаимно-однозначные соответствия слыхали? Получается при этом математически строго. В отличии от Вашего мутного рассуждения.

Ну, положим, гуманитарную математику никто не отменял. Помнится, одно время даже на строгой ежедневной математической конференции такая секция была. Через нормальное распределение вообще многое понимается интуитивно и сразу.

[provincialka]

lampard в сообщении #1013123 писал(а):

Возьмем набор из $100$ составных чисел. Разложим эти составные числа на множители, тогда получится минимум $200$ сомножителей. Верна ли эта идея?

Нет, неверна, потому что некоторые из сомножителей вы посчитаете дважды!
Например (вместо 100 берем 4)
$2\cdot 3\cdot (5\cdot 7)\cdot(11\cdot13)=(2\cdot 7)\cdot(3\cdot 13)\cdot 5\cdot11$
Здесь, действительно, выписаны 4 составных числа. Но у них в совокупности 6 простых сомножителей!

Может, попробовать от противного? Что, если наше число можно разложить не более, чем на 149 сомножителей, больших 1?

-- 16.05.2015, 17:57 --

А утверждение задачи 1 вообще верно? Пусть $a_i$ -- последовательность простых чисел.
$a_1\cdot a_2 \cdot ...\cdot a_{51}\cdot(a_{52}\cdot a_{53})\cdot... \cdot(a_{148}\cdot a_{149})=a_{99} \cdot ...\cdot a_{149}\cdot(a_{1}\cdot a_{2})\cdot ... \cdot(a_{97}\cdot a_{98})$

[grizzly]

Korvin в сообщении #1015980 писал(а):

Через нормальное распределение вообще многое понимается интуитивно и сразу.

Заметьте, что пока Ваше рассуждение выглядело как подсказка для интуиции ТС, где искать решение, против него никто и не возражал. Но продолжать настаивать на том, что эта подсказка является решением, да ещё и более строгим, чем приведенное правильное решение, в этом разделе совершенно ни к чему.

[lampard]

Значит выходит утверждение задачи, которое нужно доказать оказалось неверным, спасибо!

[provincialka]

lampard в сообщении #1016005 писал(а):

Значит выходит утверждение задачи, которое нужно доказать оказалось неверным, спасибо!

Да, так. Но можно поставить вопрос, каким числом надо заменить 150, чтобы оно стало верным.

[lampard]

provincialka в сообщении #1015983 писал(а):

А утверждение задачи 1 вообще верно? Пусть $a_i$ -- последовательность простых чисел.
$a_1\cdot a_2 \cdot ...\cdot a_{51}\cdot(a_{52}\cdot a_{53})\cdot... \cdot(a_{148}\cdot a_{149})=a_{99} \cdot ...\cdot a_{149}\cdot(a_{1}\cdot a_{2})\cdot ... \cdot(a_{97}\cdot a_{98})$

А разве это противоречит условию задачи, по-моему все сходится!!!

[provincialka]

lampard в сообщении #1016232 писал(а):

А разве это противоречит условию задачи, по-моему все сходится!!!

Хм... Может, я что-то не так поняла, я не так уж долго над задачей думала... А что сходится? Представлены два разложения из разных чисел, а произведение имеет не более 149 сомножителей!

[Shadow]

provincialka в сообщении #1016045 писал(а):

Да, так. Но можно поставить вопрос, каким числом надо заменить 150, чтобы оно стало верным.

134

[lampard]

Ах, точно, все ясно, спасибо!