Комбинаторная задача из жизни

MrDindows · Сообщение **MrDindows** » 12 май 2011, 21:47

Ian писал(а):Source of the post
Вот тут претензия
MrDindows писал(а):Source of the post
Если есть хотя одна батарейка, которая состоит в трёх парах,то брать ее оч.не рекомендуется, вдруг остался треугольник и изолированная, тогда из треугольника можно взять максимум одну, + изолированная ,итого делаем её и ещё 3 батарейки из остальных трёх пар незаряженными и получаем, что в каждой паре есть минимум 1 незаряженная батарейка, что противоречит предположению.
А придирка к док-ву в том, почему бы этим трем парам, включающим в общем случае 4 батарейки, не пересекаться очень сильно, контрпример кратко вставил курсивом
У меня есть переборное док-во, оно длиннее, случаи:1)есть цикл длины 6 2)его нет, но есть 5 3) тех нет, но есть 4, 4)есть только цикл из 3х 5) нет ни одного цикла.

Не понял придирку.
Пуст у нас какая-то батарейка, например 1, принадлежит трём парам:
$\\ 1-a_1 \\ 1-a_2 \\ 1-a_3 \\ a_4-a_5 \\ a_6-a_7 \\ a_8-a_9 \\$
Тогда делаем батарейки $1,\ a_4, \ a_6, \ a_8$ незаряженными, и у нас ни одна пара не имеет 2 заряженных батареек. Там хоть треугольники, хоть ромбы будут - нам всёравно.

Ian · Сообщение **Ian** » 12 май 2011, 22:37

Но может оказаться , , то есть у нас 8 разных батареек 1, и еще одна с которой подключений не проводится. Если вы собрались выбрать "1" в качестве годной, то негодные, из годная только одна, еще изолированная может быть годной, набралось только 3, а Вы взялись для любых заданных 6 попыток указать 4 годных, чтобы приемник не заработал в этих 6 попытках. Собссно, как только Вы пообещали взять эту батарейку 1 как годную, стояла задача: есть еще 4 батарейки неизвестные (среди них 3 годные). Доказать, что с трех попыток нельзя гарантированно найти пару годных. Но эта новая задача невыполнима, в отличие от исходной , просто не надо брать эту батарейку 1 . Я не знаю, насколько Вас устроит такое краткое объяснение (любая комбинаторика больше похожа в этом виде на заклинания, чем на математику), но Вы и сами быстрее найдете свою ошибку.

Так ,отставить придирку, вы же выбирали НЕгодные. Однако симптоматично, что кто-то убежала набираться сил, прежде чем проверять, а я не понял с первого раза и даже со второго. Не люблю эту литературную комбинаторику. графы еще куда ни шло

vvvv · Сообщение **vvvv** » 12 май 2011, 23:10

Обозначи заряженную батарейку - 1,
не заряженную - 0.

Будем каждый раз вставлять новую пару батареек.
Рассмотрим самый неудачный случай, когда 4 пары не дали результата (другие случаи приводят к
более быстрому решению).
Тогда очевидно, что каждая пара (из четырех) состоит из (0 , 1).
Выберем из любой пары одну из батарек и начнем паровать ее с каждой из батареек любой пары из оставшихся трех пар. При этом получим (в худшем случае) три парных комбинаций.
Итак, сделав семь попыток мы, установим, что восьмая попытка даст положительный результат.
Какое число (семь или восемь) принять за ответ - это дело соглашения, хотя формально проделывается восемь операций.

Таланов

vvvv писал(а):Source of the post
Итак, сделав семь попыток мы, установим, что восьмая попытка даст положительный результат.

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

Для тех, кто отчаялся найти алгоритм, отличный от Ксениного:

w0robey · Сообщение **w0robey** » 13 май 2011, 10:45

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

Ксения показала за семь. Просто за седьмую попытку она знает гарантированно, где какая батарейка. У вас кстати тоже за 7.
З. Ы. Как Xenia1996 сказала, так я и считаю...

Таланов

Таланов писал(а):Source of the post
Для тех, кто отчаялся найти алгоритм, отличный от Ксениного:

1 2
3 4
5 6
7 8

1. 1-2
2. 3-4
3. 5-3
4. 5-4
5. 6-7
6. 6-8

7 и 8 - заряжены.

Заглянул на ds по ссылке Ксении, где она выложила эту же задачу. Там считают что мой алгоритм не отличается от Ксениного. Я не согласен. А вы как считаете?

w0robey писал(а):Source of the post
Как Xenia1996 сказала, так я и считаю...

А вас получилось как у Ксении, или на одну попытку больше?

w0robey · Сообщение **w0robey** » 13 май 2011, 11:00

Заглянул на ds по ссылке Ксении, где она выложила эту же задачу. Там считают что мой алгоритм не отличается от Ксениного. Я не согласен. А вы как считаете?

Если бы вы проверили не пару 1-2, а пару 7-8, то это был бы уже способ Ксении... поэтому их можно считать разными, хоть и похожими.

А вас получилось как у Ксении, или на одну попытку больше?

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

grigoriy · Сообщение **grigoriy** » 13 май 2011, 11:03

Xenia1996 писал(а):Source of the post
Из личного опыта: советская "Селга" от одной не работала никогда.

Таланов

w0robey писал(а):Source of the post
На одну больше... но потом придумал с семью, который совпал с вашим.

А вы мой скрытый текст не смотрели?

vvvv · Сообщение **vvvv** » 13 май 2011, 11:05

Таланов писал(а):Source of the post
Таланов писал(а):Source of the post
Для тех, кто отчаялся найти алгоритм, отличный от Ксениного:

1 2
3 4
5 6
7 8

1. 1-2
2. 3-4
3. 5-3
4. 5-4
5. 6-7
6. 6-8

7 и 8 - заряжены.

Заглянул на ds по ссылке Ксении, где она выложила эту же задачу. Там считают что мой алгоритм не отличается от Ксениного. Я не согласен. А вы как считаете?

w0robey писал(а):Source of the post
Как Xenia1996 сказала, так я и считаю...

А вас получилось как у Ксении, или на одну попытку больше?

В своем решении Xenia рассмотрела случай, когда в каждой группе из трех батареек результат
отрицательный и на этом основала свой вывод, но в одной из групп по три батарейки может
быть один результат положительный - тогда 6 , ну, никак.

yourdomain.com