Челорык » 12 мар 2010, 11:15
Задуманные натуральные числа n и m удовлетворяют условиям
2 <= n <= m <= 99 (5)
Такие числа для краткости будем называть допустимыми. Пусть X := n*m и Y := n+m.
Введем две специальные функции, значениями которых будут множества чисел:
p(x) - множество произведений пар допустимых чисел, сумма которых равна x. Например, p(8) = { 12, 15 }, p(10) = { 16, 21, 24, 25 }.
s(x) - множество сумм пар допустимых чисел, произведение которых равно x. Например, s(11) - пустое множество, s(15) = { 8 }, s(24) = { 14, 11, 10 }.
Утверждение (1) в переводе на наши обозначения означает следующее:
s(X) содержит более одного элемента. (1')
Обозначим через P1 множество чисел, удовлетворяющих (1'). Начало этого множества несложно выписать явно:
P1 = { 12 16 18 20 24 28 30 32 36 40 42 45 48 ... }
Как легко видеть, в P1 нет чисел, являющихся произведением двух простых чисел (а также кубом простого числа).
Отметим еще такой факт, который нам дальше понадобится: P1 не содержит чисел, кратных 53. Действительно для допустимого числа t s(53t) = { 53+t }, то есть состоит из одного числа так как 106 - следующее кратное числу 53 - уже не является допустимым.
Утверждение (2) также легко перевести:
p(Y) является подмножеством P1. (2')
Обозначим множество чисел, удовлетворяющих (2'), через S1. В частности, отсюда следует, что S1 не содержит чисел, представимых в виде суммы двух простых.
Известная гипотеза Гольдбаха-Эйлера (не доказанная, но проверенная для всех досягаемых на ЭВМ чисел) утверждает, что каждое четное число, начиная с 4, является суммой двух простых. Следовательно, S1 не содержит четных чисел. Кроме того, S1 не содержит чисел вида p+2, где p - простое.
Таким образом, в качестве кандидатов в элементы S1 остаются только такие числа:
{ 11 17 23 27 29 35 37 41 47 51 53 57 59 ... 197 }
Выбросим отсюда все числа, большие 55: Если Y>55, то Y можно представить в виде суммы 53 + (Y-53), поэтому число 53*(Y-53) принадлежит s(Y), но произведение таких чисел, как отмечено выше, не принадлежит P1. Теперь проверке в S1 подлежат только числа
{ 11 17 23 27 29 35 37 41 47 51 53 }.
Идем дальше. После фразы (2) P уже знает, что число Y нечетное. Поэтому он может рассматривать в качестве пары сомножителей уже не любые делители числа X, а только делители разной четности. В частности, если X=2^n*p, где p - простое, то s(X) содержит единственное нечетное число Y=2^n+p, и P сможет однозначно определить загаданные числа - это 2^n и p.
Что означает фраза (3)? Она означает, что
пересечение множества s(X) и множества S1 состоит ровно из одного элемента. (3')
Обозначим через P2 множество тех X из P1, для которых выполнено свойство (3'). В частности, 16 не принадлежит P2, так как s(16) состоит только из четных чисел. Так как 30 = 5*6 = 2*15 и оба числа 5+6 и 2+15 принадлежат S1, то пересечение s(30) и S1 содержит хотя бы два элемента, т.е. 30 тоже не принадлежит P2. Рассуждая аналогично, можно получить первые элементы P2:
P2 = { 18 24 28 52 72 76 96 100 102 110 ... }
Замечание: для некоторых X можно сразу сказать, что X входит в P2. А именно, если X = 2^k * p, где p - нечетное простое, а k>1, то единственным нечетным элементом s(X) будет число p+2^k, и нужно только проверить, входит ли это число в S1.
Что можно почерпнуть из фразы (4), сказанной господином S ? Что
пересечение p(Y) и множества P2 состоит ровно из одного элемента X (4')
(иначе S не смог бы выбрать между двумя или более вариантами).
Пусть S2 - множество тех Y из S1, для которых выполнено условие (4').
В отыскании множества S2 и состоит, собственно, задача (для каждого Y из S2 мы однозначно определяем X из условия (4'), а зная X и Y, легко находим загаданные числа).
Выпишем множества p(Y) для всех небольших значений Y из S1:
p(11) = { 18 24 28 30 } - и 18, и 24 входят в P2.
p(17) = { 30 42 52 60 66 70 72 } - в P2 входит только 52.
p(23) = { 42 60 76 90 102 ... } - 76 и 102 входят в P2.
p(27) = { 50 72 92 110 ... } - 72 и 110 входят в P2.
Так как 35 = 2^2 + 31 = 2^4 + 19, то по замечанию, сделанному выше, оба числа 2^2*31 и 2^4*19 входят в P2, поэтому пересечение p(35) и P2 состоит более чем из одного элемента, и 35 не входит в S2.
Аналогично,
37 = 2^5 + 5 = 2^3 + 29,
47 = 2^4 + 31 = 2^2 + 43,
51 = 2^3 + 43 = 2^2 + 47.
Теперь для проверки в S1 остались только числа { 29 41 53 }.
Так как 29 = 4 + 25, а 100 входит в P2 (разберитесь, почему это так) и одновременно с этим 29 = 2^4 + 13 (13 - простое), то 29 не входит в S2.
Так как 41 = 4 + 37 (37 - простое) и 41 = 16 + 25, а 400 входит в P2, то 41 не входит в S2.
Наконец, 53 = 16 + 37 и 53 = 13 + 40, но 13*40=520 также входит в P2.
Мы разобрали все возможные значения Y и пришли к единственному случаю - Y = 17, при этом пересечение p(Y) с P2 - число X=52. Отсюда задуманные числа сразу находятся - это 13 и 4. Ура!
Примечание: Требование, чтобы число Y НЕ БОЛЕЕ ЧЕМ ОДНИМ способом представлялось в виде суммы простого числа и степени двойки, оказывается чрезвычайно мощным. А именно, из достаточно большого количества элементов множества S1 через это "решето" проходят лишь числа
17 29 41 53 59 65 89 97 119 127 ...
При этом 127 - наименьшее число, для которого ни одного такого представления нет. Начиная с 59, числа "просеиваются" так:
59 = 2^4 + 43 (где 43 - простое)
59 = 4 + 55; число 4*55 = 220 принадлежит P2, поскольку
s(220) = { 112 59 49 32 31 }, из коих только 59 принадлежит S1.
65 = 4 + 61 и
65 = 8 + 57; 8*57=456 принадлежит P2, потому что
s(456) = { 230 155 118 82 65 50 43 }, - только 65 принадлежит S1
Зашёл нагадить.