|
Название: взвешиваем слонов Отправлено: Черная кошка от Октябрь 30, 2011, 10:02:43 В зоопарке живут N слонов. Известно, что у них всех разные массы. Директор зоопарка хочет определить, который слон самый тяжелый, который - второй по весу, ..., который самый легкий. Для этого он может взвешивать слонов на рычажных весах без гирь: поместить одного слона на одну чашу весов, второго - на другую и определить, который тяжелее. При этом каждый слон согласен взвешиваться не более одного раза в день. Доказать, что директор может достичь свою цель за а) 3 дня, если N=4; б) 6 дней, если N=8; в) 15 дней, если N=32. (Считать, что за это время массы слонов не меняются.)
Название: Re: взвешиваем слонов Отправлено: moonlight от Октябрь 30, 2011, 20:13:29 если слонов 4 то всё просто -
1) взвешиваем 2 любые пары 2) находим самого тяжелого и самого лёгкого 3) одним взвешиванием находим 2-го и 3-го. если слонов 8 то в первые 3 дня взвешиваем две любые четвёрки как показано выше, но на 3-й день дополнительно сравниваем самых тяжелых и самых лёгких слонов из четвёрок, так что после 3-х дней найдём самого тяжелого, самого лёгкого и ещё 2 упорядоченные группы 3 и 3 или 2 и 4. если 2 и 4 то более тяжелого из 2-х сравниваем со 2-м из 4-х, а более лёгкого с 3-м из 4-х. И.Т.Д. |