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

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

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

Ксения, а от каких батареек работали радиостанции любителей-коротковолновиков в 20-е годы прошлого века?
Ах, что же это я... Откуда вам знать... В то время вы были совсем ещё крошкой...

:rolleyes:

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

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

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

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

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

Таланов

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

Тогда меньше шести получится. Повезло просто.

Ксения, а откуда вы взяли эту задачу?

СергейП

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

Они правы.
Если перенумеровать батарейки в Вашем решении так - 1 и 2 сделать 7 и 8, а остальные уменьшить на 2, то полное решение выглядит так (с не большой перестановкой)
1. 1-2
2. 1-3
3. 2-3
4. 4-5
5. 4-6
6. 7-8
7. 5-6

А решение Ксении
1. 1-2
2. 1-3
3. 2-3
4. 4-5
5. 4-6
6. 5-6
7. 7-8

Одно из измерений даст 2 заряженные батарейки, в худше случае - это произойдет при последнем 7-ом измерении.
Ваши решения отличаются перестановкой одного последнего замера.

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

Таланов писал(а):Source of the post
Ксения, а откуда вы взяли эту задачу?

Это очень известная задача. Вам в пионерском лагере никогда её не задавали? Или на маткружке?
По-моему, не было советского пионера, который не сталкивался с ней ни разу.

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

[quote name='talanov' date='13.5.2011, 13:16' post='278525']
[quote name='vvvv' post='278520' date='13.5.2011, 18:05']
В своем решении Xenia рассмотрела случай, когда в каждой группе из трех батареек результат
отрицательный и на этом основала свой вывод, но в одной из групп по три батарейки может
быть один результат положительный - тогда 6 , ну, никак.
[/quote] Тогда меньше шести получится. Повезло просто.

Ксения, а откуда вы взяли эту задачу?
[/quote

Да, нужно рассматривать наихудший вариант

Таланов

СергейП писал(а):Source of the post
Таланов писал(а):Source of the post Там считают что мой алгоритм не отличается от Ксениного. Я не согласен. А вы как считаете?
Они правы...
Ваши решения отличаются ...

Я понял.

Xenia1996 писал(а):Source of the post
По-моему, не было советского пионера, который не сталкивался с ней ни разу.

Ну это, по-вашему. А по-моему, ответственно вам заявляю как бывший советский пионер и бывший советский пионервожатый, были такие.

Equinoxe · Сообщение **Equinoxe** » 13 май 2011, 21:27

Всем привет!

Доказать очень просто:
Свести задачку к задачке на графах, а именно к полному графу из 8 вершин, из которого вырезают 6 рёбер, и необходимо доказать, что будет клика размера 4.
Ясно, что если у каждого удаленного ребра хотя бы одну вершинку удалить, то оставшееся будет кликой, осталось лишь доказать, что этих самых оставшихся будет не менее 4х
Ну, вперёд:
1. Изначально есть хотя бы два смежных ребра, удаляем их общую вершину, задачка свелась к 4 ребрам (удалённым) и 7 вершинам (либо удалённых ребер меньше, ясно, что тогда в итоге останется не меньше вершин, чем при таком раскладе)
2. Опять найдутся два смежных, опять удаляем их общую вершину, сводим к 2 рёбрам и 6 вершинам
3. Для каждого ребра удалим по вершинке — и получим желаемые 4 вершинки ^_^

Xenia1996 · Сообщение **Xenia1996** » 13 май 2011, 21:38

Equinoxe писал(а):Source of the post
Всем привет!

Equinoxe · Сообщение **Equinoxe** » 13 май 2011, 21:42

Xenia1996 писал(а):Source of the post
Equinoxe писал(а):Source of the post
Всем привет!

Как здорово, что Вы вернулись! Я Вас упомянула дважды в этой теме. Всё спрашивала "а где же Анечка?", словно младенец, которого от груди оторвали

А что означает "ГИА"?
И почему КРИ - в космосе?

yourdomain.com