Решение головоломки Ж. Арсака

Выполнила ученица 11 А класса Коробова Тамара Аркадьевна

Муниципальное общеобразовательное учреждение “Лицей №43”

Саранск, 2004

Моя работа будет посвящена решению головоломки, условие которой находится в книге Ж. Арсака “Программирование игр и головоломок”.

Условие головоломки таково:

Выбрали два натуральных числа большие 1 и меньшие 100. Значение их произведения сообщили господину Р, а значение суммы – господину S (причем, ни один из них не знает какое число сообщили другому). Далее между господином Р и господином S произошел такой диалог:

Господин Р: Я не могу найти эти два числа.

Господин S: Я знаю, что Вам это и не удалось бы.

Господин Р: Ах так. Ну тогда я их знаю.

Господин S: Ну тогда и я тоже их знаю.

Этим диалогом загаданные числа “вычисляются” однозначно.

Я составила программу на языке Pascal, которая “анализирует” высказывания господина Р и господина S и поэтому, естественно, состоит из 4 частей:

1) первая “отбрасывает” пары, состоящие из простых чисел;

2) вторая “отбрасывает” из оставшихся пар такие, сумма которых может быть представлена в виде двух простых слагаемых;

3) третья – те пары чисел, произведение которых встречается у какой-нибудь другой пары чисел, которая, кстати, тоже будет отброшена;

4) четвертая – те пары чисел, сумма которых встречается у какой-нибудь другой пары чисел, которая, кстати, тоже будет отброшена.

Теперь о самой программе: для хранения информации о парах чисел я использую двумерный булевский массив b, в который на соответствующие места я буду записывать “истину”, если пара чисел удовлетворяет условию задачи на данном шаге и, естественно, “ложь”, если – нет. Кстати, чтобы числа i, j и j, i не считались дважды перебор идет только по половине таблицы.

Булевская процедура prost будет “истиной”, если число х – простое и “ложью”, если – составное.

Остальные пояснения находятся в ремарках самой программы.

Const n=99;

M=(n-1)*n div 2;

Var b: array[2..250,2..250] of boolean;

I, j,k, l,p, vs1,vs2,vs3,vs4,sum, s: word;

Fin: boolean;

Function prost(x: word): boolean; {истина, если х – простое число}

Var da: boolean;

P: word;

Begin

Da:=true;

If x>2 then

For p:=2 to trunc(sqrt(x)) do if x=(x div p)*p then da:=false;

Prost:=da;

End;

Begin

{начинается первый шаг – будут отброшены те пары чисел,

У которых оба числа – простые}

Writeln(‘ при n= ‘,n);

Vs1:=0; {vs1 – количество решений после первого шага}

For i:=2 to n do

For j:=i to n do

Begin

If prost(i) and prost(j) then b[i, j]:=false

Else begin b[i, j]:=true; vs1:=vs1+1; end;

End;

Writeln(‘vs1= ‘,vs1:5,’ iz ‘,m);

S:=0; {s – количество решений, которые будут отбрасываться в дальнейшем}

{начинается второй шаг – будут отброшены те пары чисел i, j, сумма которых

Может быть представлена в виде двух простых слагаемых}

For i:=2 to n do

For j:=i to n do

Begin

If b[i, j] then

Begin

Sum:=i+j; fin:=false; k:=2;

While (not fin) and (k<=(sum div 2)) do

Begin

If prost(k) and prost(sum-k) then fin:=true;

K:=k+1;

End;

If fin then begin b[i, j]:=false; s:=s+1; end;

End;

End;

Vs2:=vs1-s; writeln(‘vs2= ‘,vs2:5,’ iz ‘,m);

{начинается третий шаг – будут отброшены те пары чисел i, j, произведение

Которых встречается у какой-нибудь другой пары чисел, которая, кстати,

Тоже будет отброшена}

For i:=2 to n do

For j:=i to n do if b[i, j] and (i=98) and (j=99) then writeln(i:3,j:3);

For i:=2 to n do

For j:=i to n do

Begin

If b[i, j] then

Begin

P:=i*j; fin:=false; k:=2;

While k<=n do

Begin

L:=k;

While l<=n do

Begin

If b[k, l] and (p=k*l) and (i<>k) then

Begin fin:=true; b[k, l]:=false; s:=s+1; end;

L:=l+1;

End;

K:=k+1;

End;

If fin then begin b[i, j]:=false; s:=s+1; end;

End;

End;

Vs3:=vs1-s; writeln(‘vs3= ‘,vs3:5,’ iz ‘,m);

{начинается четвертый шаг – будут отброшены те пары чисел i, j, сумма

Которых встречается у какой-нибудь другой пары чисел, которая, кстати,

Тоже будет отброшена}

For i:=2 to n do

For j:=i to n do

Begin

If b[i, j] then

Begin

Sum:=i+j; fin:=false; k:=2;

While k<=n do

Begin

L:=k;

While l<=n do

Begin

If b[k, l] and (sum=k+l) and (i<>k) then

Begin fin:=true; b[k, l]:=false; s:=s+1; end;

L:=l+1;

End;

K:=k+1;

End;

If fin then begin b[i, j]:=false; s:=s+1; end;

End;

End;

Vs4:=vs1-s; writeln(‘vs4= ‘,vs4:5,’ iz ‘,m);

For i:=2 to n do

For j:=i to n do if b[i, j] then writeln(i:4,j:4);

Readln

End.

Теперь о результатах:

1) оказывается при тех условиях, которые сообщены в книге (числа более 1 и менее 100, то есть от 2 до 99 включительно, поэтому первоначально в программе константа n=99) задача имеет два решения:

(4;13) и (98;99);

2) но если условия изменить: числа от 2 до 100 включительно, то второе решение (98;99) отбрасывается на 4 шаге, так как есть две пары чисел с такой суммой: (98;99) и (97;100).

Все это побудило меня исследовать эту задачу более подробно: при каких еще значениях n эта задача будет иметь единственное решение.

Достаточно видоизменить приведенную программу (n теперь будет не константой, а переменной и взять всю программу внутрь цикла по этой переменной от 5 до 110).

Результаты оказались такие:

При достаточно малых значениях n (n<35) задача либо не имела решения (при n=5, 7, 8, 10, 11, 13, 16, 17, 20, 22, 23, 25, 28, 31, 32), либо имела только одно решение равное числам (n-1) и n (при n=6, 9, 12, 14, 15, 18, 19, 21, 24, 26, 27, 29, 30, 33, 34).

При n=35 произошел качественный скачок: теперь решения были всегда, причем при некоторых значениях n (при n=35, 37, 38, 41, 43, 46, 50, 52, 53, 55, 56, 58, 65, 67, 70, 71, 76, 77, 80, 83, 85, 88, 91, 92, 97, 98, 100, 101, 107) это было единственное решение одинаковое для всех n: (4;13), а при остальных значениях n>35 добавлялось еще одно решение: (n-1;n).

Список литературы

Ж. Арсак, “Программирование игр и головоломок”, М., Наука, 1990г.


Решение головоломки Ж. Арсака