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

← →
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]

Точно!

← →
wal © (2008-12-17 09:22) [46]

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

← →
MBo © (2008-12-17 09:29) [47]

>wal © (17.12.08 09:22) [46]
Да, верно!

← →
Дуб © (2008-12-19 08:19) [48]

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

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

← →
MBo © (2008-12-19 09:28) [49]

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)

← →
Дуб © (2008-12-19 13:19) [51]

> 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

← →
Дуб © (2008-12-19 15:37) [55]

> nnov (19.12.08 15:33) [54]

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

← →
MBo © (2008-12-19 16:34) [56]

>Дуб © (19.12.08 15:37) [55]
Да ладно тебе...
Если человеку интересно порешать, он же не будет решения в ветке смотреть

← →
Дуп (пароль вот прпомню) (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 |____________________________ |

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