логическая задача про числа

[Alin22]

Нашла решение этой задачи, но не совсем смогла разобраться.
У одного султана было два мудрых визиря. Захотел он проверить, насколько они сообразительны. Позвал он их обоих и сказал:
- Я загадал два числа от 2 до 100. Вы должны их мне назвать.
При этом султан сообщил первому визирю произведение этих чисел, а второму - их сумму.
Первый визирь подумал и говорит:
- Я не знаю что это за числа
На что второй ответил:
- Я был в этом уверен.
Тогда первый говорит:
- В таком случае, я знаю, что это за числа.
Второй:
- Тогда и я знаю, что это за числа.
Какие числа загадал султан?

Решение
Обозначим сумму чисел как S, а их произведение - как P. Сами числа пусть будут x и y x+y=S, xy=P.
Разберём реплики визирей.
- Я не знаю что это за числа, – сказал первый визирь (ему было сообщено P).
Отсюда мы извлекаем информацию о том, что x и y – это не пара простых чисел. Кроме того, их произведение не может быть однозначно разложено на два множителя, не превосходящие ста.
- Я был в этом уверен, – сказал второй визирь (ему было сообщена S).
Зададимся вопросом: в каком случае второй визирь не мог быть на все сто уверенным в том, что первый не угадает числа с первого раза? Во-первых, когда S представляется в виде суммы двух простых чисел. Во-вторых, когда существует такое разложение S в сумму S=a+(S-a), что произведение a(S-a) однозначно раскладывается на множители, меньшие ста.
Таким образом, существует всего десять вариантов значения S, при которых вторым визирем могла быть сказана его реплика. Это числа 11, 17, 23, 27, 29, 35, 37, 41, 47, 53. Вот эту информацию и получил первый визирь после реплики второго.
До этого момента все понятно
- Я знаю что это за числа, – сказал первый визирь.
Итак, первый визирь знает, что xy=P и что x+y=11 или 17 или 23 или 27 или 29 или 35 или 37 или 41 или 47 или 53. Поскольку он может однозначно восстановить числа x и y, то произведение P таково, что сумма его сомножителей для одного варианта разложения равняется одному из десяти допустимых значений (ДДЗ), а для прочих – не равняется. Эту информацию получает перед своей репликой второй визирь.
- Я знаю что это за числа, – сказал второй визирь.
Второй визирь знает сумму чисел и узнал, что для произведения чисел существует единственный вариант разложения на множители, сумма которых равна одному из ДДЗ.
Поскольку он определил числа, то существует единственное разложение суммы S = a+(S-a) такое, что для произведения P=a(S-a) существует единственное разложение на множители P=b*(P/b), такое, что сумма b+P/b равна одному из ДДЗ.
А такое возможно лишь для суммы S=17 и произведения P=52.
Если рассмотреть число 17, то его можно представить:
S= 17= 2+15, P=2*15=30=5*6, 5+6=11
17= 3+14, P=3*14=42=2*21, 2+21=23
17= 4+13, P=4*13=52=2*26, 2+26=28
17= 5+12, P=5*12=60=3*20=5*14=6*10, 3+20=23, 5+14=19,6+10=16
17= 6+11, P=6*11=66=3*22=6*11, 3+22=25, 6+11=17
17= 7+10, P=7*10=70=2*35, 2+35=37
17= 8+9, P=8*9=72=2*36=4*18, 2+36=38, 4+18=22
Не понимаю, почему не подходят другие числа, и почему именно число 17 подходит, ведь во многих вариантах его разложения число равно одному из ДДЗ.

[MrDindows]

"Поскольку он может однозначно восстановить числа x и y, то произведение P таково, что сумма его сомножителей для одного варианта разложения равняется одному из десяти допустимых значений (ДДЗ), а для прочих – не равняется. Эту информацию получает перед своей репликой второй визирь.
- Я знаю что это за числа, – сказал второй визирь.
Второй визирь знает сумму чисел и узнал, что для произведения чисел существует единственный вариант разложения на множители, сумма которых равна одному из ДДЗ."

Например для суммы$ 23$:
$23=7+16; 7*16=112=56*2=28*4=14*8$ ( только одна сумма подходит под ДДЗ)
$23=4+19; 4*19=76=38*2$ ( и опять таки только одна сумма подходит под ДДЗ)

Таким образом, если б у второго визиря была сумма $23$, он бы не смог выбрать между вариантами$(7;16)$ и $(4;19)$, а так как он однозначно знал ответ, знчит эта сумма не подходит.
Аналогично для все других сумм из ДДЗ, кроме 17.

[e2e4]

(Оффтоп)

Задачка-то известная, но что пришло на ум: воистину велик тот султан, который способен окружить себя столь мудрыми визирями.

[Алексей К.]

Alin22 в сообщении #372439 писал(а):

Это числа 11, 17, 23, 27, 29, 35, 37, 41, 47, 53.

А чтобы выделить эту десятку, надо скриптик на мапле писать, или как-то поумней можно? Типа какое-то сокровенное знание о простых числах?

[MrDindows]

Нет, они очень быстро выделяются в ручную.
Это все те числа, которые нельзя разложить на сумму двух простых( либо на такую сумму, где из произведения двух чисел сразу можно сказать, что это за числа, например для числа 59=55+4; 55*4=220=110*2)
Сразу исключаем все чётные.
Далее исключаем все $N$, для которых $N-2$ простое.
А также исключаем все $N>53$, для которых $N-4$ простое.

Вот и остались у нас эти 10 чисел.

[Alin22]

Спасибо большое. Может кто-то еще сможет помочь написать более эффективную программу, реализующую этот алгоритм? у меня слишком много вложенных циклов, наверное, можно сделать все гораздо рациональнее..заранее спасибо. Вот код моей программы:
function TForm1.Multpl(a: integer): boolean; //определяет, можно ли число однозначно разложить на множители<100
var j,n:integer;
begin result:=false; n:=0;
for j:=2 to 99 do
if (a mod j=0) and (a div j<99) then inc(n);
if n<=2 then result:=true;
end;
function TForm1.Simple(a: integer): boolean; //проверяет, простое число или нет
var i:integer;
begin result:=true;
for i:=2 to a-2 do
if a mod i = 0 then result:=false;
end;
procedure TForm1.Button1Click(Sender: TObject);
var n,i,j,k,m:byte;
s,h,p:integer;
b:array[0..9] of integer; //в этом массиве хранятся 10 вариантов для суммы, которые мы определяем
f:boolean;
begin
s:=5; k:=0;
repeat
f:=true;
for i:=2 to s div 2 - 1 do
if (Simple(i) and Simple(s-i)) or (Multpl(i*(s-i))) then f:=false;
if f then begin b[k]:=s; inc(k); end;
inc(s,2);
until s=197;

for i:=0 to 9 do begin //выполняет вторую часть алгоритма: выясняет, для какого S существует разложение на слагаемые, такое что
для их произведения существует единственное разложение на множители, сумма которых равна одному из 10 значений S
h:=0; k:=2;
repeat
n:=0;
for j:=2 to k*(b[i]-k) div 2 -1 do
if k*(b[i]-k) mod j = 0 then
for m:=0 to 9 do
if (j + k*(b[i]-k) div j = b[m]) then inc(n);
if n<=2 then begin p:=k*(b[i]-k); inc(h); end;
inc(k);
until k=b[i] div 2 -1;
if h=1 then label1.Caption:='Сумма равна = '+IntToStr(b[i])+', '+'произведение равно = '+IntToStr(p); end;
end;

[Alin22]

ни у кого нет вариантов?((

[kokakokos]

Объясните, пожалуйста, момент, связаннный с этой задачей.

Вариант 4 и 13.

Первый визирь не знает числа, так как 52 может делиться также на 26 и 2, что в сумме дает 28.

Второй говорит, что знает, что тот не знает.

Первый понимает, что у второго сумма равна 11 или 17 или т.д. из списка. То есть он отметает 26 и 2, т.к. в сумме они дают не 17. Следовательно, первый понмиает, что числа - 4 и 13.

Однако как данный вывод сделать ещё второму?

Ведь он знает только сумму. 17. А она может состоять из слагаемых 6 и 11. И таким образом у первого может быть произведение 66.

Объясните, плиз, а то второй день голову ломаю.

[arseniiv]

(Оффтоп)

Alin22 в сообщении #375402 писал(а):

ни у кого нет вариантов?((

С таким-то кодом; вы, наверное, шутите?

[ludwig51]

Alin22 в сообщении #375402 писал(а):

ни у кого нет вариантов?((

Для решения этой задачи нет необходимости составлять программу.
Задача решается аналитически.
Для этого нужны ручка, листок бумаги и список простых чисел до 100.
Условия для суммы уже приведены:
s<100
(s-2) не простое число
s нечётное число.
Исходя из этих условий имеем 24 допустимых значения для суммы s:
11,17,23,27,31,35,37,41,47,51,53,57,59,65,67,71,77,79,83,87,89,93,95,97
Эти суммы вычисляются логически после реплики математика S (визирь, которому была названа сумма чисел): "Я заранее знал, что вы не сможете назвать эти числа"
Математик P (визирь, которому было сообщено произведение) говорит, что может назвать числа.
Как он может назвать числа?
Значит у него такое произведение, которое однозначно разлагается на произведение двух чисел с учётом выше приведённых условий.
Что ещё за дополнительное условие? Как можно однозначно представить произведение двух чисел?
Если ответить на этот вопрос, то останется только 6 допустимых сумм.
И эти суммы без труда, легко проверяются вручную.
Подсказку давать не имею права.

[VAL]

ludwig51 в сообщении #1387486 писал(а):

Исходя из этих условий имеем 24 допустимых значения для суммы s:
11,17,23,27,31,35,37,41,47,51,53,57,59,65,67,71,77,79,83,87,89,93,95,97

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

Верный перечень возможных сумм указан в письме ТС.