РАБОТА НАД СТРАНИЦЕЙ НЕ ЗАКОНЧЕНА
From: voldemar@sagantec.co.il (Vladimir A. Pertsel)
Subject: <<< ЧЕРНОБЫЛЬСКИЕ ОРЛЫ >>>
Date: 23 Jun 1996 11:41:37 GMT
Не было никакого оригинала на русском языке!
Была шутка два года назад в rec.puzzles, видимо удачная,
поскольку вызвала к жизни странички вроде
http://links.uwaterloo.ca/~douglas/Chernobyl/
А недавно, где-то там же, я ляпнул шутку насчет перевода с
русского на английский слова яйцо в некоей задачке. Так из
совершенно нерусскоязычной группы мне пришло уже пятое
письмо с просьбой прислать оригинал.
Поднапрягши память, сочинил я и "оригинал" (4 задача)
и перевел "обратно", что смог вспомнить:
Кое-что о Чернобыльских орлах:
1. Существует Чернобыльские орлы с любым наперед заданным числом голов.
2. Интелектуальная мощность Чернобыльского орла равна числу его голов.
3. Интелектуальная мощность стаи Чернобыльских орлов равна произведению
интелектуальных мощностей Чернобыльских орлов, входящих в стаю.
4. Чернобыльские орлы едят сахарную свеклу - по одной свекле в день на
каждую голову и
5. пьют керосин - по литру в неделю на каждое тело (одно у каждого орла).
6. В соответствии с Российскими сельскохозяйственными традициями, всякую
скотину считают не по телам а по головам..
А теперь задачи
1. Сколько и сколькиголовых Чернобыльских орлов нужно взять, чтобы
получить 1000-головую стаю максимальной интелектуальной мощности?
2. Чернобыльский племзавод разводит исключительно 27- и 37-головых
Чернобыльских орлов. Он получил заказ на поставку X-головой стаи.
Известно, что существует ровно один вариант составить эту стаю.
Каким может быть максимальное число X?
3. Встречаются два Чернобыльских орла:
О1: Говорят у тебя есть орлята. Сколько их и сколькиголовые они?
О2: Трое. Их интелектуальная мощность 36, а в день они съедают
столько же свеклы, сколько и ты.
О1: Этих данных недостаточно...
О2: А старший - большой любитель книг Толкиена.
О1: А-а-а! теперь я знаю, сколько!
Так сколькиголовые орлята?
4. Чернобыльский орел с двумя весьма хрупкими яйцами живет на 16 этаже.
Раньше у него было 3 яйца, но одно выпало из окна и разбилось.
И захотел этот орел узнать, начиная с какого этажа яйца начинают
разбиваться. У него есть доступ к окнам на всех этажах, но яиц осталось
только два. Он хочет получить ответ за минимальное число попыток в
худшем случае.
Точнее, он ищет стратегию бросания, которая бы гарантировала получение
ответа за N бросаний, в любом случае. Каково минимальное число N?
--
From the Holy Land, with respect
/\ /\ Vladimir A. Pertsel S/W engineer
((ovo)) E-mail: \|/ Sagantec Israel
():::() voldemar@sagantec.co.il (o o) tel.972-4-8572781
--PVA------------------------ooO-(_)-Ooo------------------
an ancestor of mine by the name of Noah was once the
commanding admiral of the combined fleets of my planet.
From: voldemar@sagantec.co.il (Vladimir A. Pertsel)
Subject: Reшения: <<< ЧЕРНОБЫЛЬСКИЕ ОРЛЫ >>>
Date: 23 Jun 1996 12:42:07 GMT
|> 1. Существует Чернобыльские орлы с любым наперед заданным числом голов.
|> 2. Интелектуальная мощность Чернобыльского орла равна числу его голов.
|> 3. Интелектуальная мощность стаи Чернобыльских орлов равна произведению
|> интелектуальных мощностей Чернобыльских орлов, входящих в стаю.
|> 4. Чернобыльские орлы едят сахарную свеклу - по одной свекле в день на
|> каждую голову и
|> 5. пьют керосин - по литру в неделю на каждое тело (одно у каждого орла).
|> 6. В соответствии с Российскими сельскохозяйственными традициями, всякую
|> скотину считают не по телам а по головам..
|>
рещения еще через 30 строчек
А теперь ответы:
|> 1. Сколько и сколькиголовых Чернобыльских орлов нужно взять, чтобы
|> получить 1000-головую стаю максимальной интелектуальной мощности?
|>
332 трехглавых и {2 двуглавых или один 4-главый}
Решение:
2 3-главых лучше 3 2-главых
5-главый хуже 2-главого с 3-главым
|> 2. Чернобыльский племзавод разводит исключительно 27- и 37-головых
|> Чернобыльских орлов. Он получил заказ на поставку X-головой стаи.
|> Известно, что существует ровно один вариант составить эту стаю.
|> Каким может быть максимальное число X?
|>
(36x27)+(26x37)
Решение:
Если есть 37 27-главых или 27 37-главых, то получим 2-й вариант
|> 3. Встречаются два Чернобыльских орла:
|> О1: Говорят у тебя есть орлята. Сколько их и сколькиголовые они?
|> О2: Трое. Их интелектуальная мощность 36, а в день они съедают
|> столько же свеклы, сколько и ты.
|> О1: Этих данных недостаточно...
|> О2: А старший - большой любитель книг Толкиена.
|> О1: А-а-а! теперь я знаю, сколько!
|>
|> Так сколькиголовые орлята?
|>
9,2,2
Решение:
О1 знал сумму числа голов, но не мог ответить, значит эта сумма 13,
так как только она допускает два варианта: 9,2,2 и 6,6,1
|> 4. Чернобыльский орел с двумя весьма хрупкими яйцами живет на 16 этаже.
|> Раньше у него было 3 яйца, но одно выпало из окна и разбилось.
|> И захотел этот орел узнать, начиная с какого этажа яйца начинают
|> разбиваться. У него есть доступ к окнам на всех этажах, но яиц осталось
|> только два. Он хочет получить ответ за минимальное число попыток в
|> худшем случае.
|> Точнее, он ищет стратегию бросания, которая бы гарантировала получение
|> ответа за N бросаний, в любом случае. Каково минимальное число N?
|>
5 (Обычная ошибка - 6)
Решение:
Первое яйцо бросать с {5,9,12,14,15} этажей, пока
не разобьется. Второе яйцо остается для исследования
промежутка (5-число сделанных попыток) этажей.
За 4 нельзя: первый раз яйцо нельзя бросить выше 4
этажа, т.к. если оно разобьется, одним яйцом промежуток
в 4 этажа за 3 попытки не исследовать... и.т.д
Let us call the floor safe, if the egg doesn't break, being dropped
from it, and unsafe otherwise.
Let us use the "credits" technique. Each attempt takes one credit.
Lemma 1: If we have one egg only and we know that the K-th floor is safe,
the only thing we can do is to check whether the K+1-th floor is safe.
Otherwise we are not guaranteed be able to determine the highest safe floor.
Proof: If we drop the egg from the floor higher, than K+1-th and it breaks,
we shall never know whether K+1-th floor is safe. Thus, the next drop
should be made from the K+1-th floor.
Lemma 2: If we have one egg and N credits, and we know that the K-th floor
is safe, we are able to determine the highest safe floor if and only if we
know that the floor N+K+1 is unsafe.Otherwise we are not guaranteed be able
to determine the highest safe floor.
Proof: We have nothing to do than to drop the egg from all the floors
in an ascending order. That immediately follows from the Lemma 1.
Lemma 3: If we have two eggs and N credits, and we know that the K-th floor
is safe, the highest floor that we can check fore the safeness in the next
egg-dropping is the K+N-th. Otherwise we are not guaranteed be able to
determine the highest safe floor.
Proof: If we drop the first egg from the floor higher, than K+N-th and it
breaks, we will not satisfy the premises of Lemma2, and thus will be unable
to determine the highest safe floor. If we drop the first egg from the K+N-th
floor, than we are able to determine the highest safe floor in any case.
Lemma 4: If we have two eggs and N credits, and we do not know in advance
that N*(N+1)/2+1 -th floor is safe, than we are not guaranteed be able to
determine the highest safe floor.
Proof: Due to Lemma 3 we have nothing to do than to drop the egg not
higher than from the floor shown below in the algorithm. If the egg doesn't
break, we shall not know whether the next floor is safe or not .
The algorithm:
Assume we have two eggs and N credits and we want our algorithm to
return the highest safe floor. According to Lemma 4 We assume that
N*(N+1)/2+1 -th floor is safe.
Credits_left := N;
Floor := 0;
Repeat {Dropping of the first egg}
Floor := Floor + Credits_left;
Drop_first_egg_from(Floor);
Credits_left := Credits_left - 1;
Until ( broken_first_egg or (Credits_left=0) )
If ( Credits_left=0 ) Then exit(N*(N+1)/2);
{ The Floor = N + N-1 + ... + 1 is safe
That means, If we know in advance that
the floor N*(N+1)/2+1 is safe, than the
N*(N+1)/2 -th floor is the highest safe }
Floor := Floor - Credits_left - 1;
{ Now we know that the floor Floor is safe
and Floor+Credits_left+1 is unsafe }
{ Once more, the highest known safe floor
Repeat {Dropping of the second egg}
Floor := Floor + 1;
Drop_second_egg_from(Floor);
Credits_left := Credits_left - 1;
Until ( broken_second_egg or (Credits_left=0) )
If ( broken_second_egg ) Then exit(Floor-1) Else exit(Floor);
С горячим приветом со Святой Земли,
/\ /\ Владимир Анатольевич Перцель, программист из фирмы
((ovo)) E-mail: \|/ Sagantec Israel
():::() voldemar@sagantec.co.il (o o) тел.972-4-8572781
--PVA------------------------ooO-(_)-Ooo------------------
мой предок по имени Ной прославился тем, что
командовал объединенным флотом моей планеты
From: voldemar@sagantec.co.il (Vladimir A. Pertsel)
Subject: <<< Пробуждение Чернобыльского орла >>>
Date: 7 Oct 1996 09:29:47 GMT
В статье <<< ЧЕРНОБЫЛЬСКИЕ ОРЛЫ >>> Владимир Анатольевич Перцель,
программист из фирмы Sagantec Israel писал:
$> 1. Существует Чернобыльские орлы с любым наперед заданным числом голов.
$> 2. Интелектуальная мощность Чернобыльского орла равна числу его голов.
$> 3. Интелектуальная мощность стаи Чернобыльских орлов равна произведению
$> интелектуальных мощностей Чернобыльских орлов, входящих в стаю.
$> 4. Чернобыльские орлы едят сахарную свеклу - по одной свекле в день на
$> каждую голову и
$> 5. пьют керосин - по литру в неделю на каждое тело (одно у каждого орла).
$> 6. В соответствии с Российскими сельскохозяйственными традициями, всякую
$> скотину считают не по телам а по головам..
Все головы девятиголового Чернобыльского орла лежат в ряд и спят.
Шестирукий Серафим пытается разбудить все девять голов. За одну
операцию, он может взять и потрясти шесть голов, лежащих подряд.
При этом спавшие головы просыпаются, но остаются на своих
подушках, зато бодрствовавшие головы засыпают. Долго ли придется
трудиться Серафиму, если он действует оптимальным образом?
--
С горячим приветом со Святой Земли,
/\ /\ Владимир Анатольевич Перцель, программист из фирмы
((ovo)) E-mail: \|/ Sagantec Israel
():::() voldemar@sagantec.co.il (o o) тел.972-4-8572781
--PVA------------------------ooO-(_)-Ooo----------------
Vladimir -- the Master of the Universe (Russian)
From: voldemar@sagantec.co.il (Vladimir A. Pertsel)
Subject: Re: <<< Пробуждение Чернобыльского орла >>>
In article <E03yF6.Fty@actcom.co.il>, nasta@actcom.co.il (gena) writes:
|> НУ И...........???
$> Все головы девятиголового Чернобыльского орла лежат в ряд и спят.
$> Шестирукий Серафим пытается разбудить все девять голов. За одну
$> операцию, он может взять и потрясти шесть голов, лежащих подряд.
$> При этом спавшие головы просыпаются, но остаются на своих
$> подушках, зато бодрствовавшие головы засыпают. Долго ли придется
$> трудиться Серафиму, если он действует оптимальным образом?
ответ через 30 строчек
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
09
08
07
06
05
04
03
02
01
00
Да просто здесь все: Сколько времени ни тряси Серафим головы
орлу, бодрствовать будет только четное число из них.
Разбудить все девять ему не удастся, ибо 9 -- число нечетное.
--
С горячим приветом со Святой Земли,
/\ /\ Владимир Анатольевич Перцель, программист из фирмы
((ovo)) E-mail: \|/ Sagantec Israel
():::() voldemar@sagantec.co.il (o o) тел.972-4-8572781
--PVA------------------------ooO-(_)-Ooo----------------
Vladimir -- the Master of the Universe (Russian)
From: "KK" <kk@knop.spb.ru>
Subject: Re: <<< ЧЕРНОБЫЛЬСКИЕ ОРЛЫ >>> [О задаче 3] [Поправка]
Date: Wed, 9 Oct 96 19:34:21 +0400
Привет!
Я тут на днях написал такое:
> Привет всем!
>
> > From: voldemar@sagantec.co.il (Vladimir A. Pertsel)
> > Subject: [News] <<< ЧЕРНОБЫЛЬСКИЕ ОРЛЫ >>>
> > Date: Sun, 22 Sep 96 11:19:33 GMT
> >
> > 3. Встречаются два Чернобыльских орла:
> > О1: Говорят у тебя есть орлята. Сколько их и сколькиголовые они?
> > О2: Трое. Их интелектуальная мощность 36, а в день они съедают
> > столько же свеклы, сколько и ты.
> > О1: Этих данных недостаточно...
> > О2: А старший - большой любитель книг Толкиена.
> > О1: А-а-а! теперь я знаю, сколько!
> >
> > Так сколькиголовые орлята?
> >
>
> А знаете, что самое смешное в этой задаче?
> Единственное приведенное в ней число (36) на самом деле лишнее!
Ну и т.д.
Виноват - ошибся.
Чтобы загладить свою вину, приведу еще одну задачу о чернобыльских орлах.
------
Встретились три чернобыльских орла и обнаружили, что если вычислить
среднее арифметическое, среднее геометрическое и среднее гармоническое
количеств их голов, то получаются три различных целых числа.
Докажите, что бывают чернобыльские орлы с числом голов более 80.
------
KK.
---
| /~ ----- | /~ ---------------
|onstantin |nop, kk@knop.spb.ru
| \_ ----- | \_ ---------------