Решение головоломки Ж. Арсака
Решение головоломки Ж. Арсака
Выполнила ученица 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г.
Для
подготовки данной работы были использованы материалы с сайта http://licey43.ru