Рыбаки и рыбки.
Эту задачу придумал известный английский физик Поль Дирак.
“Три рыбака легли спать, не поделив улова. Проснувшийся ночью первый рыбак решил уйти, взяв свою долю. Но число рыб не делилось на три. Тогда он выбросил одну рыбу, а из числа оставшихся забрал треть. Второй и третий рыбаки поступили аналогично (выбросили по одной рыбе и взяли треть из оставшихся). Спрашивается, какое наименьшее количество рыб может удовлетворить условию задачи?”.
Поль Дирак был мастер давать различным существительным приставку “анти” - античастица, например. И в этой задаче он, по-видимому, не изменил своей привычке, оригинально решив ее: минус две рыбы. Выбрасываем одну - получаем минус три, забираем треть - останется минус две и т.д.
Попробуем решить задачу, не допуская возможности ловли “антирыб”, то есть найдем наименьшее /положительное /число, удовлетворяющее условию приведенной задачи. Правда, при этом сделаем небольшое уточнение - число рыб, доставшееся каждому рыбаку, не обязательно должно быть одинаковым, как в решении Дирака.
Сначала рассмотрим такую задачу: “Имеется некоторое количество рыб. Определить, возможен ли дележ рыб между тремя рыбаками в соответствии с условием задачи Дирака”[1] .
В программе решения этой задачи используем следующие величины:
- k0 - общее количество пойманных рыб;
- k - количество рыб, оставшееся тому или иному рыбаку;
- take - количество рыб, которые взял тот или иной рыбак;
- i - номер рыбака;
- partit - величина логического типа, определяющая возможность дележа (взятия каждым рыбаком трети оставшегося количества рыб).
На */школьном алгоритмическом языке /*соответствующая программа имеет вид:
_алг_ Available_partition _нач_ _цел_ k0, k, take, i, _лог_ partit ¦ _вывод_ _нс_, "Введите количество рыб" ¦ _ввод_ k0 ¦ k:=k0 ¦ i:=1 ¦ _нц_ |цикл “действий” каждого рыбака ¦ ¦ k:=k-1 | осталось после выбрасывания одной рыбы ¦ ¦ _если_ mod(k,n)=0 ¦ ¦ ¦_то_ | i-й рыбак может взять треть оставшихся рыб ¦ ¦ ¦ partit:=_да_ ¦ ¦ ¦ take:=div(k,3) | берет i-й рыбак ¦ ¦ ¦ k:=k- take | оставшееся количество рыб ¦ ¦ ¦_иначе_ ¦ ¦ ¦ partit:=_нет_ | при k0 рыбах дележ невозможен ¦ ¦ _все_ ¦ ¦ i:=i+1 ¦ _кц___при_ i>n _или_ _не_ partit ¦ _если_ partit ¦ ¦_то_ ¦ ¦ _вывод_ _нс_, "При таком количестве рыб дележ возможен" ¦ ¦_иначе_ ¦ ¦ _вывод_ _нс_, "При таком количестве рыб дележ невозможен" ¦ _все_ _кон_
После этого программа нахождения минимального количества рыб, удовлетворяющего условию задачи Дирака, может быть оформлена очень кратко:
_алг_ Задача_Рыбаки_и_рыбки _нач_ _цел_ k0 ¦ k0:=0 |начальное значение диапазона поиска ¦ _нц_ _пока_ _не_ Avail_partit (k0) ¦ ¦ k0:=k0+1 |очередное значение ¦ _кц_ ¦ _вывод_ _нс_, "Наименьшее количество рыб," ¦ _вывод_ "удовлетворяющее условию задачи:", k0 _кон_
где Avail_partit(k0) - вспомогательная функция логического типа, определяющая возможность дележа k0/ /рыб в соответствии с условием задачи, составленная на основе программы, приведенной чуть выше:
алг_ _лог_ Avail_partit (_арг_ _цел_ k0) _нач_ _цел_ k, take, i, _лог_ partit ¦ k:=k0 ¦ i:=1 ¦ _нц_ ¦ ¦ k:=k-1 ¦ ¦ _если_ mod(k,3)=0 ¦ ¦ ¦_то_ ¦ ¦ ¦ partit:=_да_ ¦ ¦ ¦ take:=div(k,3) ¦ ¦ ¦ k:=k- take ¦ ¦ ¦ _иначе_ ¦ ¦ ¦ partit:=_нет_ ¦ ¦ _все_ ¦ ¦ i:=i+1 ¦ _кц___при_ i>3 _или_ _не_ partit ¦ _знач_:= partit | значение функции _кон_
Соответствующая программа на Паскале:
{Задача “Рыбаки и рыбки”}
Var
k0: integer;
Function Avail_partit (k0: integer): boolean;
Var
k, take, i: integer;
partit: boolean;
begin
k:=k0;
i:=1;
repeat {цикл “действий” каждого рыбака}
k:=k-1; {осталось после выбрасывания одной рыбы}
if k mod 3 = 0 then
{i-й рыбак может взять треть оставшихся рыб}
begin
partit:=true;
take:=k div 3; {берет i-й рыбак}
k:=k - take {оставшееся количество рыб}
end
else
partit:=false; {дележ невозможен}
i:=i+1
until (i>3) or not partit;
Avail_partit:= partit {значение функции}
end;
BEGIN {Основной программы}
k0:=0; {начальное значение диапазона поиска}
while not Avail_partit(k0) do
k0:=k0+1; {очередное значение}
write('Наименьшее количество рыб, ');
writeln('удовлетворяющее условию задачи: ', k0)
END.
Выполнив программу, можно увидеть, что минимальное количество рыб, удовлетворяющее условию задачи, равно 25. Имеются и большие значения (52, 79, 106, ...).
Имеется и другой способ решения задачи. Можно, так сказать, идти не от общего количества пойманных рыб, а от числа рыб, доставшихся третьему рыбаку. Если эту величину обозначить take3, то можно записать, что количество рыб, оставшееся тому или иному рыбаку, равно:
- 1) третьему рыбаку: k3 = 3* take3 + 1;
- 2) второму: k2 = 3*k3 + 1;
- 3) первому (то есть общее количество пойманных рыб[2]): k1 = 3*k2 + 1.
Перебирая значения k3, равные 1, 2, 3, …, можно найти такое минимальное число, при котором значения величин k2 и k1 есть целые числа.
Программа, реализующая такой подход к решению задачи, имеет вид:
{Задача "Рыбаки и рыбки"}
Var
take3, k3: word;
k2, k1: real;
BEGIN
take3:=1;
repeat
k3:=3* take3+1;
k2:=k3*3/2+1;
k1:=k2*3/2+1;
take3:= take3+1
until (TRUNC(k2)=k2) and (TRUNC(k1)=k1);
write('Наименьшее количество рыб, ');
writeln('удовлетворяющее условию задачи: ', TRUNC(k1))
END.
Рассмотренную задачу можно решать и при другом числе рыбаков. Соответствующие результаты представлены в таблице (естественно, что некоторые из них являются условными).
Число рыбаков 4 5 6 7 Искомое количество рыб 253 3121 46651 823537
Можно также рассмотреть варианты, в которых каждым рыбаком выбрасывается не одна рыба, а больше, а также случаи, когда перед тем как взять треть каждый рыбак не выбрасывает, а ловит еще одну (или больше) рыбу.
- [1] Эта задача может рассматриваться и как самостоятельная.
- [2] В программах, приведенных в начале статьи, эта величина имела имя k0.
Оставить комментарий
Комментарии
1) если x1 и x2 - решения, то их разность кратна 27
2) если x1 - решение, то x1+27 - также решение.
Отсюда любое положительное решение имеет вид 27k-2, где k-натуральное число