Пятничные задачки. Вася Пупкин скорее жив, чем мертв...

← →
MBo © (2008-12-12 09:33) [0]

1. Вася Пупкин собрался посетить всех привлекательных девушек в округе.
Он может выйти сразу и идти пешком, или вызвать такси, и, подождав машину
определенное время, ехать на ней.
В каждом случае используется способ передвижения, требующий меньшего времени.
При этом оказывается, что на дорогу к Люсе, живущей на расстоянии 1км, понадобится 10мин
К Ане, 2 км, на дорогу понадобится 15 мин
К Вале, 3км, на дорогу понадобится 17,5мин.
Сколько понадобится времени, чтобы добраться к Юле, живущей за 6км?

2. Решил Вася - а пускай девушки к нему сами приходят.
Однако нужна мебель достойная, а не только табуретка с ноутбуком...
Пришел в магазин, и спрашивает, сколько стоит кровать?
Первый продавец ему отвечает: 60 т.р..
Вася удивляется, что очень дорого, но тут второй продавец ему говорит:
"Знаете, у первого продавца есть особенность -- он все числа называет в 12 раз
больше, чем они есть на самом деле"
"Ну хорошо", говорит Вася первому продавцу,
"значит я понял, что кровать стоит 5 т.р., поскольку Вы все увеличиваете в 12 раз".
Тот на это отвечает: "Это Вам кто сказал, мой напарник?
Знаете, у него есть одна особенность -- он все числа преуменьшает в 3 раза"

Так во сколько обойдется Васе кровать на самом деле?

3. Поиздержавшись на комфорт, Вася Пупкин поехал домой не на такси, а на автобусе.
Он купил билет, и, закрыв пальцем шестизначный номер билета, стал открывать
по одной цифре и высчитывать вероятность того, что его билет окажется счастливым
(т.е. сумма первых трех цифр будет равна сумме трех последних).
С первой цифрой Васе не повезло.
Вторая цифра усугубила ситуацию, вероятность того, что билет окажется
счастливым, составила всего 0.0282. Впрочем, могло быть и хуже.
Зато после открывания третьей цифры вероятность "счастья" возросла до 0.055.
С четвертой цифрой Васе вновь не повезло: хуже и придумать было нельзя.
Тем не менее билет все же оказался счастливым. Более того, сумма всех цифр
номера совпала с возрастом Васиного папы.
Hайти номер билета.

4. Привезли Васе мебель, пригласил он домой подругу. Пару свечей зажег.
Когда подруга ушла, свечи потушил. Потом задумался, а сколько же
времени прошло - ведь счастливые часов не наблюдают...
Одна свеча была потолще, рассчитанная на 5 часов горения,
а другая - потоньше и могла сгореть за 4 часа.
Один огарок был больше другого в 4 раза.
Можно ли по этим данным определить, сколько времени был счастлив Вася?

5. Один нумизмат имел стол с правильным круглым отверстием,
предназначенным для чернильницы. У того нумизмата были две монеты
из чистого золота одинаковой толщины. Большая из монет как раз заполняла
все отверстие; меньшая же монета при медленном подталкивании к отверстию
начинала крениться в тот самый момент, когда ее край достигал центра отверстия.
Большая монета весила 6 унций. Сколько весила малая монета?

6. Фокуснику завязывают глаза. Ассистент фокусника обходит зрителей и
собирает 64 монеты любого достоинства. Ассистент фокусника просит одного
из зрителей разложить монеты на шахматной доске (в каждой клетке по одной монете)
и выбрать любую монету (указать на нее пальцем), после чего ассистент
указывает на одну из монет на доске и просит зрителя перевернуть ее.
Фокуснику развязывают глаза, он смотрит на доску и безошибочно определяет монету, которую выбрал зритель.
Как это ему удается?

7. У Васи Пупкина есть 15 шаров, 2 их которых радиоактивны.
Имеется детектор, при поднесении к которому набора шаров выдается сигнал, если
в наборе есть радиоактивные шары.
Как за 7 измерений выявить оба радиоактивных шара?

8. Найти выражение для суммы
S=1 + 2x + 3x^2 + 4x^3 + ... + n*x^(n-1)

9. На полке у Васи стоит N книг различных авторов (N > 3)
Вася смотрит на 1-ю и 2-ю книгу и переставляет их,
если они стоят не в алфавитном порядке.
Потом делает то же с 2-й и 3-й , 3-й и 4-й книгами и так до конца.
Таким образом поступая, делает он 3 прохода слева направо.
Сколько всего сушествует различных исходных вариантов расстановки книг,
которые Вася может за эти 3 прохода расставить по алфавиту?

10. В покоящейся вертикально расположенной запаянной трубке находится
массивный подвижный поршень (на рисунке он примерно посередине трубки)
Трубку быстро перевернули вокруг поршня.
Найти ускорение поршня в первый момент времени после переворота.
Трением поршня о стенки трубки пренебречь.

← →
Bless © (2008-12-12 09:46) [1]

1) 25 мин

← →
Медвежонок Пятачок © (2008-12-12 10:11) [2]

20 штук кровать

← →
boriskb © (2008-12-12 10:14) [3]

> MBo ©

Извините за оффтоп, но вопросы 1-4 это же литература!
:)
Просто браво.

← →
Skyle © (2008-12-12 10:18) [4]

> Медвежонок Пятачок © (12.12.08 10:11) [2]
> 20 штук кровать

А нее 10?

← →
Медвежонок Пятачок © (2008-12-12 10:18) [5]

не, ровно 20 штук

← →
Skyle © (2008-12-12 10:20) [6]

> Медвежонок Пятачок © (12.12.08 10:18) [5]

Ладно, подожду обоснования.

← →
Медвежонок Пятачок © (2008-12-12 10:22) [7]

"12" - это в три умножить на двенадцать уменьшенное значение искажения суммы, которое применяет первый продавец

← →
wal © (2008-12-12 10:29) [8]

4. 3.75ч

← →
Skyle © (2008-12-12 10:29) [9]

Ладно, покажите где я ошибся.

X - кровать, k1 - коэффициент "вранья" первого продавца, k2 - коэффициент второго.

Первый продавец ему отвечает: 60 т.р..
k1 * x = 60

[второй говорит] он все числа называет в 12 раз больше
k1*k2=12

[первый говорит] он все числа преуменьшает в 3 раза
1/3 * k1 = k2

K2 = 2, K1 = 6 => X = 10

← →
Skyle © (2008-12-12 10:32) [10]

6. Монеты не при чём. Просто ассистент по какому-то заранее договорённому алгоритму выбирает другую клетку доски, по которой фокусник однозначно определяет исходную клетку.

← →
axis_of_evil © (2008-12-12 10:39) [11]

10. g, думается

← →
Bless © (2008-12-12 10:40) [12]

5) 3 унции

← →
Медвежонок Пятачок © (2008-12-12 10:52) [13]

Если k1 = 6 , а k2 = 2

то :
не сходится например высказывание первого про второго:

"он все суммы уменьшает в три раза"

получается, что реально он уменьшает не в 3 раза, а в 3/6

и первый продавец увеличивает цену не в 12 а в 24 раза

← →
Skyle © (2008-12-12 10:58) [14]

> Медвежонок Пятачок © (12.12.08 10:52) [13]

> получается, что реально он уменьшает не в 3 раза, а в 3/6

Дробь переверни.

← →
@!!ex © (2008-12-12 11:08) [15]

Кровать стоит 1 666 рублей.
Т.к. второй продавец уменьшает ВСЕ числа в три раза, то значит первый продавец преувеличивает не в 12 раз, а в 36.

← →
Медвежонок Пятачок © (2008-12-12 11:13) [16]

"в три раза" это тоже искаженное

← →
@!!ex © (2008-12-12 11:15) [17]

> [16] Медвежонок Пятачок © (12.12.08 11:13)

хм. точно...

← →
Skyle © (2008-12-12 11:50) [18]

4. 11/3, как у wal(c), но с использованием одного предположения.

7-я интересная, всё никак чегой-то не даётся :)

← →
Agent13 © (2008-12-12 12:05) [19]

7. Делим 15 шаров на группы: 4, 4, 7.
Первые 2 измерения - испытываем группы шаров по 4. После этой процедуры в худшем случае остаются 8 подозрительных шаров. Их делим так: 2, 2, 4
3 и 4 измерения - группы шаров по 2. В худшем случае - 4 подозрительных шара.
Теперь оставшимися измерениями можем проверять шары по одному.

← →
Agent13 © (2008-12-12 12:06) [20]

Хотя нет, поторопился. [19] можно не читать :)

← →
Agent13 © (2008-12-12 12:17) [21]

Продолжаю поток мыслей :) Моя ошибка в [19] состояла в том, что после 2 измерений могут остаться 2 подозрительных группы - 4 и 7 шаров с одним радиоактивным в каждой. Тогда 3-им измерением испытываем 3 или 4 шара из группы в 7 шаров.
В худшем случае имеем 2 группы по 4 с одним радиоактивным в каждой.
4, 5 измерение - по 2 шара из группы - в результате 2 подозрительных группы по 2 шара.
6, 7 измерение - по 1 шару из группы.

← →
Skyle © (2008-12-12 12:22) [22]

> Agent13 © (12.12.08 12:17) [21]

Каналья, похоже на правду :)

← →
VMcL © (2008-12-12 12:46) [23]

5. 1.5 унции (диаметр в два раза меньше, значит площадь в четыре раза меньше).

← →
Bless © (2008-12-12 12:54) [24]

> VMcL © (12.12.08 12:46) [23]
>
> 5. 1.5 унции (диаметр в два раза меньше, значит площадь
> в четыре раза меньше).
>

Диаметр не в два раза меньше.

← →
VMcL © (2008-12-12 13:53) [25]

>>Bless © (12.12.08 12:54) [24]

Да, это я стормозил :-)
Чувстовал же, что где-то подвох.

← →
MBo © (2008-12-12 14:18) [26]

Bless © (12.12.08 09:46) [1]
1) 25 мин

Верно. По соотношению времен и дистанций ясно, что во втором и третьем случае используется машина, и можно систему уравнений составить

2) рассуждения Skyle © (12.12.08 10:29) [9]
верны, кровать 10 стоит

wal © (12.12.08 10:29) [8]
4. 3.75ч
Верно (3 ч 45 мин)

Bless © (12.12.08 10:40) [12]
5) 3 унции
Да
Геометрически решал или из других соображений?

axis_of_evil © (12.12.08 10:39) [11]
10. g, думается
Нет, неверно

>Agent13
Готового рецепта к этой задаче у меня нет, ранее решал подобную с другими числами. Соображениями поделиться могу, поскольку задача непростая.

← →
Bless © (2008-12-12 14:23) [27]

> Agent13 © (12.12.08 12:17) [21]
> Продолжаю поток мыслей :) Моя ошибка в [19] состояла в том,
> что после 2 измерений могут остаться 2 подозрительных группы
> - 4 и 7 шаров с одним радиоактивным в каждой.

Тут состоит твоя вторая ошибка :)
Ты не можешь знать наверняка, что в каждой группе по шару.
Например, ты поделил 15 на 4, 4, 7 (как ты предлагаешь). И измерил 4 и 4.
Получил "радиоактивности не обнаружено" на одной кучке и "есть радиоактивность" - на другой.
Но ведь может быть так, что во второй кучке - два радиоактивных шара, тогда в кучке с 7 шарами - ни одного.

Соответственно, дальнейшие рассуждения не катят, потому что ты не можешь теперь, не зная точно, где второй шар, делить кучки надвое и сделав одно измерение, одну из кучек отбрасывать.

← →
Bless © (2008-12-12 14:24) [28]

> Bless © (12.12.08 10:40) [12]
> 5) 3 унции
> Да
> Геометрически решал или из других соображений?

геометрически

← →
Bless © (2008-12-12 14:29) [29]

эврика!

← →
wal © (2008-12-12 14:43) [30]

6. Есть вариант, но в уме тяжело считается. Подожду вариантов

← →
AndreyV © (2008-12-12 15:15) [31]

> [26] MBo © (12.12.08 14:18)
> axis_of_evil © (12.12.08 10:39) [11]
> 10. g, думается
> Нет, неверно

2g, g + такое же давление на поршень со стороны среды, которая стала сверху.

← →
MBo © (2008-12-12 15:28) [32]

AndreyV © (12.12.08 15:15) [31]
10. 2g, g + такое же

да. Поршень удерживается избыточным давлением воздуха, сила равна его весу. При переворачивании и вес, и давление направлены в одну сторону

← →
Antonsh (2008-12-12 15:50) [33]

Народ, а как правильно посчитать 4 задачу?

← →
AndreyV © (2008-12-12 15:58) [34]

Про шары.
Не все кучки необходимо замерять.
Например, 2+1 - меряем где 1. Вот общее решение не могу понять.

← →
MBo © (2008-12-12 16:01) [35]

>Народ, а как правильно посчитать 4 задачу?
1-x/5=4*(1-x/4)

← →
MBo © (2008-12-12 16:06) [36]

>Вот общее решение не могу понять.
Соображения:
а) Вариантов расклада C(15,2) = 120, т.е. за 7 измерений (7 бит, 128 вариантов) потенциально возможно выяснить (однако не факт, что для любых количеств шаров, для которых выполняется подобное условие, можно найти тактику)
б) Взяв группу из, для примера, 10 шаров, и определив, что она радиоактивна, остаемся с 6 измерениями (64 исхода) и С(10, 2) + 10*5 = 45 + 50 = 95 вариантами расклада, если не ошибаюсь, что не гарантирует обнаружения.
Первое слагаемое суммы - если оба шара в группе, второе - если один шар в группе

Таким образом, на каждом этапе нужно выбирать такое разделение, которое оставляет шансы на обнаружение.

← →
Дуб © (2008-12-13 05:32) [37]

А 8-ю еще не подняли из-за сухости цифр? ИМХО, 8 и 10 самые простые задачи из всех.

> Bless © (12.12.08 14:29) [29]
> эврика!

Это ты не про геометрические соображения? Колись!

← →
Bless © (2008-12-15 09:00) [38]

> Дуб © (13.12.08 05:32) [37]
> > Bless © (12.12.08 14:29) [29]
> > эврика!
>
> Это ты не про геометрические соображения? Колись!

Нет. Мне показалось, что я нашел решение 7-й задачи. Показалось :)

← →
Alexis (2008-12-16 15:33) [39]

3)
Izvinite za translit.
Po mojemu ja zada4u po4ti reshil, no nikak ne mogu poniat, kak to4no opredelit pervyje dve cifry, budet interesno uznat reshenije :-)

Nr. bileta ABCDEF
DEF = 189 ili 198 (po mojemu bez raznicy),
C=8, t.e. bilet vygliadit AB8189 ili AB8198

A+B = 10 i AB dolznen byt odnim iz {19, 28, 37, 64, 73, 82, 91}, t.k. Vase ne povezlo s pervoj cifroj, znacit eto ne 46 i ne 55..

U kogo jesio ideji ?

2) vremia ozidanija taksi 10min, skorost Vasi 6 km/cas, skorost taksi 24km/cas (dovolno stranno, no tak vyhodit iz uslovij zadaci). K Jule doberiotsia za 25min (10 min zdiot i 15 min jedet)

← →
wal © (2008-12-16 15:44) [40]

> Alexis (16.12.08 15:33) [39]

У меня DEF=099 получилось, дальше не считал, рабочий день кончился ;)

← →
MBo © (2008-12-16 16:05) [41]

>У меня DEF=099 получилось
это правильно.
Сумму цифр половинки билета верно определили, как 18 (из вероятности 0.055 и разумности возраста папы)
Поскольку четвертая цифра наихудшая, то это ноль, и две оставшиеся - только девятки.
Далее весьма сложный шаг - определить сумму двух первых цифр в диапазоне от 9 до 18 так, чтобы вероятность 0.0282 оказалась...

← →
Alexis (2008-12-16 16:29) [42]

> Далее весьма сложный шаг - определить сумму двух первых
> цифр в диапазоне от 9 до 18 так, чтобы вероятность 0.0282
> оказалась...

A razve ne C cifru nado najti pervoj ? Ved zada4u nado "rasputyvat"" ot obratnogo.

Ja rassuzdal tak : kogda Vasia otkryl pervyje dve cifry, on ponial, cto ostavshyjesia 4 cifry dolzny obrazovat kakuju-to opredelionnuju summu s verojatnostju 0.0282, t.e. iz 10000 kombinacij(interval [0..9999]) tolko 282 "popadajut" v cel"

Beriom C# :)
static void Main(string[] args) { ushort[] sumVariants = new ushort[37]; //4*9 = 36 for (ushort number = 0; number < 10000; number++) { ushort digitSum = 0; ushort number2 = number; while (number2 != 0) { int result = 0; ushort quotient = (ushort)Math.DivRem(number2, 10, out result); digitSum += (ushort)result; number2 = quotient; } sumVariants[digitSum] += 1; } ushort checksum = 0; foreach (ushort sumVariant in sumVariants) { checksum += sumVariant; } System.Diagnostics.Debug.Assert(checksum == 10000); System.IO.StreamWriter outputStream = new System.IO.StreamWriter(System.IO.Path.Combine(Environment.CurrentDirectory, "variants.txt")); for (int i = 0; i < 37; i++) { Console.WriteLine("Sum = {0}, {1} variants", i, sumVariants[i]); outputStream.WriteLine("Sum = {0}, {1} variants", i, sumVariants[i]); } outputStream.Close(); }

i polu4ajem
Sum = 0, 1 variants
Sum = 1, 4 variants
Sum = 2, 10 variants
Sum = 3, 20 variants
Sum = 4, 35 variants
Sum = 5, 56 variants
Sum = 6, 84 variants
Sum = 7, 120 variants
Sum = 8, 165 variants
Sum = 9, 220 variants
Sum = 10, 282 variants, ne podhodit, t.k. DEF=18, a eto bolshe 10
Sum = 11, 348 variants
Sum = 12, 415 variants
Sum = 13, 480 variants
Sum = 14, 540 variants
Sum = 15, 592 variants
Sum = 16, 633 variants
Sum = 17, 660 variants
Sum = 18, 670 variants
Sum = 19, 660 variants
Sum = 20, 633 variants
Sum = 21, 592 variants
Sum = 22, 540 variants
Sum = 23, 480 variants
Sum = 24, 415 variants
Sum = 25, 348 variants
Sum = 26, 282 variants !! => C = 26 - 18 = 8
Sum = 27, 220 variants
Sum = 28, 165 variants
Sum = 29, 120 variants
Sum = 30, 84 variants
Sum = 31, 56 variants
Sum = 32, 35 variants
Sum = 33, 20 variants
Sum = 34, 10 variants
Sum = 35, 4 variants
Sum = 36, 1 variants

← →
MBo © (2008-12-16 16:53) [43]

ага, подход в принципе правильный, только почему ты считаешь сумму четырех цифр!?
На этом этапе Вася не знает суммы половинки, но мы-то знаем, что сумма 18. Это поможет нам перебирать меньше вариантов.
Если сумма первых двух - 18, то сумма половинки от 18 до 27, и вероятность счастья = (1 + 3 + 6 + ..+55)/10000 ~ 0.022
Если 17, то то сумма половинки от 17 до 26, и вероятность (3+ 6+ 10 + ..+63)/10000=0.0282 - вот оно!

← →
Alexis (2008-12-16 17:24) [44]

> ага, подход в принципе правильный, только почему ты считаешь
> сумму четырех цифр!?

Aga, to4no, zaparilsia. Ja po4emu-to reshil, cto 282 "popadanija" nado iskat sredi CDEF, t.k. AB Vasia uze otkryl.

Zna4it imejem AB1099, gde A+B=17
Eto 89 i 98. Jesli moglo byt huze, to eto 98, ABCDEF=981099

← →
MBo © (2008-12-16 17:37) [45]

Точно!

6. Раз других вариантов не последовало, выложу свой.
Клетки нумеруем от 0 до 63.
1) Ассистент производит операцию xor всех номеров клеток, на которых монетка лежил "орлом".
2) Ассистент производит операцию xor результата из 1) и номера клетки, на которой лежит выбранная зрителем монета.
3) Ассистент просит зрителя перевернуть монету, которя лежит на клетке с номером, полученным в 2)
4) Фокусник делает ту же операцию, что в 1) и получает номер клетки, на котором лежит выбранная зрителем монета.

Так с 8-й что? Слишком сухая или таки идей нет?

На данный момент есть 2 подхода.

9 тоже еще не трогали

← →
anonims (2008-12-19 11:25) [50]

8. S-искомая последовательность
S(1-x)/(1-x) =(1+x+x^2+x^3+...+x^(n-2)+x^(n-1) -nx^n)/(1-x) =
геом пр(1.x.n) /(1-x) - nx^n/(1-x)

> anonims (19.12.08 11:25) [50]

Можно еще так:
1. проинтегрировать.
2. просуммировать
3. продиференцировать

полученое - ответ.

← →
nnov (2008-12-19 14:31) [52]

ну если уж быть точным: все цифры - а значит когда второй продавец говорит про первого, то он имеет ввиду третьего (раз уж все цифры умножает на три), а когда первый говорит про второго, то он говорит не "второй", а напарник, значит не врет)) тогда вообще ничего не понятно=)

← →
nnov (2008-12-19 14:35) [53]

> @!!ex © (12.12.08 11:08) [15]
>
> Кровать стоит 1 666 рублей.
> Т.к. второй продавец уменьшает ВСЕ числа в три раза, то
> значит первый продавец преувеличивает не в 12 раз, а в 36.
>

говорят, тут все на много сложнее - через искажение...

← →
nnov (2008-12-19 15:33) [54]

> "он все суммы уменьшает в три раза"
>
> получается, что реально он уменьшает не в 3 раза, а в 3/6
>
> и первый продавец увеличивает цену не в 12 а в 24 раза

это получается 3/12 и 36

> nnov (19.12.08 15:33) [54]

ты все свои рассуждения тут приводить будешь? Задачу давно решили и решение написали. Кому интересны скрипы в твоем мозгу?

← →
Дуп (пароль вот прпомню) (2008-12-20 07:07) [57]

> MBo © (19.12.08 16:34) [56]

Я понимаю, но не понимаю. :) Про споллеры писал - с ними бы, конечно, было бы получше.

Кстати, тут задачку подкидывали: есть циркуль и линейка и угол. Разделить его на три части - приближенно, но с хорошей точностью. Последнее формализовать не буду - но примерно как - с любой наперед заданой.

> Дуп (пароль вот прпомню) (20.12.08 07:07) [57]

Делить угол пополам (классика, описывать не буду), то тех пор, пока не получим величину "любую наперед заданную", потом из этих кусочков составляем три примерно равных части, n, n, n+-1

>wal © (22.12.08 09:04) [58]

Ага. В общем случае - записать нужную дробь в двоичной системе счисления и по написаному строить.

1/3 = 0.(01) ТО есть надо будет надстраивать четвертинки, четрвертинки от четвертинок и т.д.

Последним шагом можно сделать еще такое. Когда получим сегмент который захотим четвертовать чтобы добавить его четвертинку, можно построить хорду и поделить на три части и прибавить дугу отсекаемую первой третью. При этом достигнутая точность при дальнейшем четвертовании будет достигнута через много шагов.

Например, при делении угла в 90 градусов, после двух делений и одной хорды уже был угол 29,95, при простом посторении половинок - такая точность только на 7-м шаге.

Решил, кажется, 7-ую. Правда, длинно и ни разу не элегантно (приведено ниже).
А есть ли красивое решение?

Решение.
Сперва отмечу, что если есть группа шаров, в которой есть как минимум один радиоактивных шар, то найти ОДИН радиоактивный шар можно гарантированно (последовательно деля группу пополам и меряя одну из групп)
за 1 измерение - в группе из 2 шаров,
за 2 измерения - в группе из 4 шаров,
за 3 измерения - в группе из 8 шаров,
за 4 измерения - в группе из 16 шаров.

Далее введем обозначение
N+ обозначает группу из N шаров, среди которых есть хотя бы один радиоактивный.
N? обозначает группу из N шаров, которую мы не меряли (т.е. неизвестно, есть ли в ней радиоактивные шары).
Обозначение для группы, где все шары - нерадиоактивные, не нужно, т.к. такую группу мы будем сразу выбрасывать.

Итак, поехали. Делим 15 шаров на две группы: 5 и 10 шаров и меряем группу с 5 шарами.
Возможны 2 варианта:
(а) 5+ 10?
(б) 10?

Остается 6 измерений.

С деревом и рисунками обошлись бы одной страницей, текстом будет длиннее... Ну да ладно.

Итак рассматриваем все варианты по очереди.
Сначала вариант (а):
Помним, что осталось 6 измерений и шары поделены на 5+ 10?
Делаем новую группу из 4 шаров из группы 10? и 1 шара из группы 5+ (оставшиеся 4 шара этой группы обозначим как 4") и меряем радиоактивность этой новой группы(в ней 5 шаров). Это единственное такое "хитрое" деление на всю задачу :)
Возможны варианты
(а а) 5+ 4" 6?
(а б)4+ 6?

Решаем вариант (а а). Осталось 5 измерений:

меряем один шар - тот, что сейчас в группе 5+, а ранее был забран из группы, что теперь обозначена как 4".
Если этот шар радиоактивный (нашли!), то нам остается 4 измерения и еще 14 шаров, один из которых - радиоактивный.
Как указано в начале, 4-х измерений достаточно для поиска 1 радиоактивного шара в группе из 16 шаров. И заведомо достаточно для группы из 14 шаров. Так что в этом случае мы найдем оба шара и уложимся в 7 измерений.

Если же этот шар нерадиоактивный, то мы его выбрасываем. У нас остается 4+ 4" 6?
Но поскольку этот шар нерадиоактивный, а группа 4", когда он в ней находится, была радиоактивной, то значит радиоактивным является какой-то другой шар этой группы. Т.е. на самом деле имеем 4+ 4+ 6?
Т.о. у нас осталось 4 измерения и две группы по четыре шара, в каждой из которых есть 1 радиоактивный. Как показано вначале, по 2 измерения на каждую группу - вполне достаточно, чтоб найти эти шары.

Итак, вариант (а а) - решаемый.

Теперь решаем вариант (а б), напомню, остается 5 измерений и имеем группы 4+ 6?:

Меряем 4 шара из группы 6?. Получаются варианты:
(а б а) 4+ 4+ 2?
(а б б) 4+ 2?

Причем осталось 4 измерения.
Вариант (а б а), очевидно, вполне решаем за это количество измерений (по два измерения на каждую группу 4+).

Решаем (а б б) 4+ 2?.
Меряем группу 2? Получаем:
(а б б а) 4+ 2+
(а б б б) 4+
Осталось 3 измерения.

Для (а б б а) этого достаточно (2 измерения, чтоб найти шар в группе 4+ и одно - в группе 2+).
Дляя (а б б б) - тоже очевидно достаточно: 4 шара и 3 измерения.
Итак, вариант (а б б) - полностью решаемый.
А значит, и варианта (а б) решаем. А значит, и вариант (а) решаем, т.к. мы рассмотрели все возможные варианты, следующие из (а), и показали, что во всех них исходного количества измерений вполне достаточно.

Итак, теперь вариант (б): 10?, осталось 6 измерений:
Дальше буду писать вкратце. Количество оставшихся измерений тоже писать дальше не буду, его легко посчитать: оно равно 7 минус количество букв в обозначении варианта.
Итак:
(б а) 3+ 7?
(б б) 7?

(б a а) 3+ 4+ 3? - решаемо (по 2 измерения на группы 3+ 4+. А осталось как раз 4 измерения. Хватает.)
(б а б) 3+ 3?

(б а б а) 3+ 2+ 1? решаемо (2 измерения на группу 3+ и одно - на 2+)
(б а б б) 3+ 1?

(б а б б а) 3+ 1+ решаемо (2 оставшихся измерения - на поиск шара в группе 3+. А 1+ - это и есть второй шар)
(б а б б б) 3+ решаемо (2 измерения на поиск первого шара в 3+. И затем еще одно измерение на поиск второго в двух оставшихся шарах).

Итак, вариант (б а) полностью рассмотрен и во всех случаях решаем.

Теперь вариант (б б) 7?:
(б б а) 2+ 5? Решаемо (за 1 измерение находим один радиоактивный в группе 2+. Второй шар этой группы добавляем в группу 5?, получаем 6+ (ведь второй шар теперь точно здесь, больше ж негде :)) и решаем ее за 3 измерения. Как раз уложились в 4 измерения.
(б б б) 5? Очевидно решаемо. Четыре измерения на пять шаров.

Вариант (б б) полностью рассмотрен и во всех случаях решаем. Значит и вариант (б) в целом тоже.

Мы рассмотрели полностью все варианты.

>Bless
Сложно, блин, переварить пока не могу ;)

>А есть ли красивое решение?
Готового решения у меня нет, но для, кажется, 11 шаров - решалось тоже длинно.

← →
nnov (2008-12-23 08:24) [62]

> MBo © (23.12.08 05:30) [61]
>
> >Bless
> Сложно, блин, переварить пока не могу ;)

Я сразу честно предупредил, что некрасиво, хотя если с деревом и картинками, то понять проще :)

Вообще плохо даже не то, что длинно, а то, что это просто решение конкретной задачи, ни к чему больше не пригодное.

Я помню пятничную задачу про скрытую проводку, концы которой выходят на двух этажах и нужно было определить, где начало и конец каждого провода. Вот там решение (не помню, чье) было мало того что лаконичным, так еще и легко распространялось на любое количество проводов, т.е. годилось для решения целого класса задач. Вот это было красивое решение.
Честно говоря, я рассчитывал услышать нечто подобное и для этой задачи :)

Первое измерение для группы в 5 шаров - однозначно, другие варианты даже теоретически не гарантируют успеха
Далее при положительном измерении получается табличка возможных пар
_| 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1|__ | 2 |__ | 3 |__ | 4 |_ | 5 |_______________________ |
Пар 60. Далее, как мне кажется, нужно разбивать таблицу примерно пополам, чтобы в каждой половине было не более 32 пар.
Например, измерение группы из 6 неизмеренных шаров - шары 10-15 отделяются вертикальной линией, прямоугольник справа, 30 + 30 - теоретически проходит
1 измеренный + 4 неизмеренных - узкая полоска сверху плюс квадрат справа
30+30 - тоже проходит, это твой вариант
2 измеренных и 1 неизмеренный - 30 + 30
Больше я разбиений не углядел.

еще попытка выровнять табличку
_| 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1|__ | 2 |__ | 3 |__ | 4 |__ | 5 |____________________________ |

Пятничные задачки. Вася Пупкин скорее жив, чем мертв... Найти похожие ветки