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

F(x) · Сообщение **F(x)** » 12 май 2011, 20:25

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

sangol, то что вы посчитали -- это всего лишь вероятность вытянуть наугад 2 заряженные батарейки за 1 попытку...

Xenia1996 · Сообщение **Xenia1996** » 12 май 2011, 20:25

Александр Малошенко

хм..

w0robey · Сообщение **w0robey** » 12 май 2011, 20:34

F(x), честно признаюсь, я не знаю что он посчитал (формулировка по определению не в счёт)

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

w0robey писал(а):Source of the post
F(x), честно признаюсь, я не знаю что он посчитал (формулировка по определению не в счёт)

ТВ здесь не проходит, восьмая установка пары батареек гарантирует работу и баста

F(x) · Сообщение **F(x)** » 12 май 2011, 20:51

w0robey писал(а):Source of the post
F(x), честно признаюсь, я не знаю что он посчитал (формулировка по определению не в счёт)

не знаю как прокоментировать это, а вы это к чему вообще?

vvvv писал(а):Source of the post
ТВ здесь не проходит, восьмая установка пары батареек гарантирует работу и баста

не-е... пар всего 4 )

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

F(x) писал(а):Source of the post
w0robey писал(а):Source of the post
F(x), честно признаюсь, я не знаю что он посчитал (формулировка по определению не в счёт)

не знаю как прокоментировать это, а вы это к чему вообще?

vvvv писал(а):Source of the post
ТВ здесь не проходит, восьмая установка пары батареек гарантирует работу и баста

не-е... пар всего 4 )

Установок пар больше, ведь предлагали 18, хотя при плохом алгоритме можно совать и большее число раз

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

Ксюш, попробую-ка я доказать минимальность 7.
Значит у нас есть 7 комбинаций:
1-2
1-3
2-3
4-5
4-6
5-6
7-8
Из них есть минимум одна, которая составлена из 2 заряженных батареек, не зависимо от того, какие из 8 батареек: 1,2,3..8 , являются заряженными.
Предположим что есть способ для 6 проверок, который даёт аналогичный результат. Запишем эти комбинации как:
$\\ a_1 \ a_2\\ a_3 \ a_4\\ a_5 \ a_6\\ a_7 \ a_8\\ a_9 \ a_{10}\\ a_{11} \ a_{12}\\$
Если есть хотя одна батарейка, которая состоит в трёх парах, делаем её и ещё 3 батарейки из остальных трёх пар незаряженными и получаем, что в каждой паре есть минимум 1 незаряженная батарейка, что противоречит предположению.
Если "тройных" батареек нет, то у нас должно быть минимум 4 - "двойных". И гаранировано найдутся 2 такие батарейки, что не состоят вместе в одной паре. Тогда наши пары запишем в таком виде:
$\\1-2 \\ 1-3 \\ 4-a_1\\ 4-a_2\\ a_3-a_4\\ a_5-a_6\\$
И сделав батарейки 1, 4, $a_3,\ a_5$ незаряженными, добьёмся того, что пар заряженных батареек опять нет.
А значит способ из 6 проверок не может существовать, что и требовалось доказать.

Вот так вот, без теории графов и прочих теорий. Оформление конечно не ахти, но суть, имхо, верна и её можно понять)

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

MrDindows писал(а):Source of the post
Ксюш, попробую-ка я доказать минимальность 7.

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

Вот тут претензия

MrDindows писал(а):Source of the post
Если есть хотя одна батарейка, которая состоит в трёх парах,то брать ее оч.не рекомендуется, вдруг остался треугольник и изолированная, тогда из треугольника можно взять максимум одну, + изолированная ,итого делаем её и ещё 3 батарейки из остальных трёх пар незаряженными и получаем, что в каждой паре есть минимум 1 незаряженная батарейка, что противоречит предположению.

А придирка к док-ву в том, почему бы этим трем парам, включающим в общем случае 4 батарейки, не пересекаться очень сильно, контрпример кратко вставил курсивом
У меня есть переборное док-во, оно длиннее, случаи:1)есть цикл длины 6 2)его нет, но есть 5 3) тех нет, но есть 4, 4)есть только цикл из 3х 5) нет ни одного цикла.

yourdomain.com