Кабак по случаю дня сисадмина

Question

На праздник сисадмина товарищи решили сходить в бар. Все они дано не виделись и сели за круглый стол. Их было поровну: 50% предпочитали *nix, а 50% - семейство Windows. Поскольку у администраторов Windows бороды нет, они купили сок, *nix админы взяли пиво. Так как официантка не разбирается в ОС, она все перепутала и большинству достался не свой напиток. Все уже хотели ее потроллить, но она предложила повернуть стол таким образом, что, не передвигая напитки, большинство получит свой заказ. Во всех ли случаях у нее это получится?

Да потому что сказано "большинство"! — Ostap Tan Ivanyshyn, Jul 27 '12 at 12:13
@Flash спорим ты чемпион игры в напёрсток :) — zenith, Jul 27 '12 at 12:28
Имхо, или условие не совсем точное, или админов не может быть нечётное количество. — zenith, Jul 27 '12 at 12:43
Конечно, ответ может быть типа "Нет если админов нечётное колво". Но я не знаю как это доказать. — zenith, Jul 27 '12 at 12:46
@flash выбор из ограниченного количества вариантов. Если бить наугад, а именно так выглядел твой коммент, то с определёной вероятностью можно дать правильный ответ.
По аналогии с анекдотом:
Надпись на могиле "Здесь лежит Flash -- чемпион игры в напёрсток".
Надпись на соседней "Или здесь". — zenith, Jul 27 '12 at 12:54
@zenith, Их четное количество (2 раза по N). — Nicolas Chabanovsky, Jul 27 '12 at 12:57
блин, пропустил что их парное количество) тогда да . всегда — Yaroslav Schubert, Jul 27 '12 at 13:50

score 11 · Accepted Answer · edited Jul 27 '12 at 13:43

11

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

11110000  
11001100  
vvxxvvxx

при повороте:

11110000  
01100110  
xvvxvxxv

Упс: По условию, БОЛЬШИНСТВО получило неправильный напиток.

Для непонятливых:

Ответ: WIN, всегда получится

edited Jul 27 '12 at 13:43

Nicolas Chabanovsky

51,426
87
267
507

answered Jul 27 '12 at 12:59

knes

25,879

В вашем примере не выполняется начальное условие. Изначально большинство получило не свой напиток. а у вас половина. т.е. не больше. С таким распределением неинтересно. – Yura Ivanov Jul 27 '12 at 13:29
Нет. У меня, как раз большинство. Половина рассмотрена как граничный случай, который не выполнится по условию. Читайте внимательно. – knes Jul 27 '12 at 13:30
"и большинству достался не свой напиток." это не граничный случай, а вырожденный. – Yura Ivanov Jul 27 '12 at 13:31
Совершенно верно. См последнюю строчку. – knes Jul 27 '12 at 13:32
1
Ну так это ложная посылка. Вы говорите, что да, не всегда у нее получится, потому что есть случай при котором начальное условие не выполняется. Отсюда может следовать любое утверждение.
Надо исследовать случаи типа:
```
11110000
10001110
```
– Yura Ivanov Jul 27 '12 at 13:34
В указанном вами варианте опять ровно половина недовольных.
11110000
10001110 2

11110000
01000111
2

11110000
10100011
2

Дальше продолжать?

Когда недовольные присутствуют, обязательно будут колебания, так как в противном случае это означало бы, что официантка принесла неверное количество напитков
– knes Jul 27 '12 at 13:43
1
Продолжим? :)
1. Не доказано, что циклический сдвиг также как и распределение всех комбинаций будет нормальным. Циклический сдвиг будет подмножеством, но не обязательно также распределенным.
2. Не доказано, что при циклическом сдвиге будут колебания. Даже наоборот, у вас колебаний нет, значит можно предположить что существуют и другие случаи когда колебаний не будет.
3. Доказательство можно свести к тому, что можно сдвигать стол на любое количество разрядов. Например, на 2 или на n/2 и, ваш пример даст то же ложное утверждение, что типа всегда получится, на самом деле далеко не всегда.
– Yura Ivanov Jul 27 '12 at 15:10

score 7 · Answer 2 · answered Jul 27 '12 at 13:14

У нее получится во всех случаях, потомо, что: Количество админов будет парное, тоесть 2 либо 4 и тд. Если большинству не достался свой напиток, то он не достался либо n/2+1 админам (в случае 6, 10, 14 (когда mod(n/2)=1)) либо n/2+2(8, 12 (mod(n/2)=0)) админам, это значит, что их было больше чем 4. Мой ответ: у нее получится повернуть стол таким образом, что, не передвигая напитки, большинство получит свой заказ, только в случае, когда будет больше, чем 4 админа.

Gorets · Answer 3 · 2012-07-27T12:26:40.817

Так как 50/50, то если поставить стаканы в через один (сок, пиво, сок, пивО) - то покрутив стол - получаем профит, при условии, что виновники торжества, тоже сели через один.

Если бородатые на одной стороне, а форточники на другой - тогда тоже получится, если стаканы поставить в очередности (соки, пиво).

Еще как вариант можно крутить это "барабан" пока они не разберут, кто что хочет, тогда вообще без проблем и Якубович доволен.

Всех админов с праздником! хотя это и не ваш форум =)

UPD

Рассмотрим еще частных случай, если их пришло всего 2е - тогда профит 100%

@Gorets, Думаю лучше доказывать от обратного. — Nicolas Chabanovsky, Jul 27 '12 at 12:13
я сначала думал... потом решил, что эти 3 варианта - все что может решить проблему, остальное - официантка попала... разве что ей ужасно повезет =) — Gorets, Jul 27 '12 at 12:14

Ilya Pirogov · Answer 4 · 2012-07-27T13:29:14.277

6

Нет, поскольку есть как минимум один случай, когда это не возможно. Если все сисадмины будут сидеть попеременно, а напитки идти по порядку сначала пиво, затем сок (или наоборот), то как бы она не крутила стол напитки всегда будут соответствовать только у половины сисадминов.

     + +             + -             + -
     W L             W L             W L
   ┌─────┐         ┌─────┐         ┌─────┐
  ┌┘ b j └┐       ┌┘ b b └┐       ┌┘ b b └┐
-L│ b   j │W-   -L│ b   j │W-   -L│ b   b │W+
  │       │       │       │       │       │
+W│ b   j │L+   +W│ b   j │L+   -W│ j   j │L+
  └┐ b j ┌┘       └┐ j j ┌┘       └┐ j j ┌┘ 
   └─────┘         └─────┘         └─────┘
     L W             L W             L W
     - -             + -             + -

edited Jul 27 '12 at 13:29

answered Jul 27 '12 at 13:04

Ilya Pirogov

10,948

Ага. Но есть условие: УЖЕ большинство получило неправильный. – knes Jul 27 '12 at 13:05
4

Спектр, зачем уже буянишь? Стол сломал в кабаке... – knes Jul 27 '12 at 13:16
Пардон, не внимательно прочитал. В таком случае ответ: ответ да, получится, поскольку это данный случай единственный, когда у нее это не получится. Осталось только доказать почему :) – Ilya Pirogov Jul 27 '12 at 13:16
1

Чёт столы в разных браузерах по-разному поломаны – Spectre Jul 27 '12 at 13:20
5

Пофиксил столы. Теперь они кроссбраузерные :) – Ilya Pirogov Jul 27 '12 at 13:30
3

Cтолы Ilyapirogoff(tm). – knes Jul 27 '12 at 13:33

score 4 · Answer 5 · edited Jul 27 '12 at 13:46

4

Ответ на вопрос: не во всех случаях; если представить, что все - и админы, и напитки расположены рандомно за столом, на столе, то вероятность удачного случая можно рассчитать по формуле (A+B)!/(A! * 2(A+B)) (или что-то около того).

edited Jul 27 '12 at 13:46

Nicolas Chabanovsky

51,426
87
267
507

answered Jul 27 '12 at 12:27

Kira-sa

41

хотелось бы взглянуть на это объяснение на плюсах или джаве, в идеале, конечно же, на баше админа – Gorets Jul 27 '12 at 12:29

score 4 · Answer 6 · answered Jul 28 '12 at 19:37

Т.к. число админов четное минимальное значение тех кто получил свой напиток это половина, а половина-это не большинство, поэтому не во всех.

Kota · Answer 7 · 2012-07-27T12:18:48.270

Если они будут сидеть 2л-1в-2л-3в то не получится. Правдиво и обратное, если на местах виндузятников будут сидеть красноглазые. То есть если "группу" линукс\виндовс-пользователей будет разбавлять их "противник" - официантка не выполнит своего обещания. Если же они будут чередоваться в последовательности в-л-в-л-.. или в-в-л-л.., то официантке необходимо будет повернуть стол всего на 10-30 градусов в зависимости от количества человек.

Допустим их 8 (или n, где n - любое четное число) Стол круглый, поэтому все сидят друг против друга. Если одну условную половину стола "разбавить" "противником" - то, как ни крути, не попадешь.
Сделаем наглядную схему л - в | в - л | л - в | л - в | (Ах да, я не умею в столбцы и ASCII) — Kota, Jul 27 '12 at 12:23

score 3 · Answer 8 · edited Jul 27 '12 at 13:45

Рассмотрим ситуации при повороте стола на 1 человека:

напиток не соответствовал человеку и не стал соответствовать,
напиток не соответствовал человеку и стал соответствовать,
напиток соответствовал человеку и не стал соответствовать,
напиток соответствовал человеку и стал соответствовать.

Ситуации 1 и 4 не меняют ничего, 2 или 3 меняют количество нужных нам человек. Если мы повернем стол на 360 градусов, то каждый напиток того самого вида будут иметь равное количество ситуаций, только они будут чередоваться с периодом 1. Gоскольку на данный момент у нас худшее состояние, то при некотором повороте мы можем сделать лучшее состояние.

score 3 · Answer 9 · answered Jul 27 '12 at 19:21

У меня такой вариант:

Циклический сдвиг для N разрядов N раз (т.е. 360 градусов), т.е. все варианты поворотов стола даст нам для каждого разряда ровно N/2 совпадений (просто просуммируем их)

То, есть для любого расставленного заказа и для любой рассадки собутыльников при полном обороте стола каждый из них получит (и не получит тоже) свой напиток одинаковое количество раз, а именно N/2. А всего попаданий будет N*N/2, всегда.

Теперь допустим, что после каждого из N поворотов стола всегда количество участников с чужим напитком будет больше (только тогда официант будет неправ), приходим к противоречию что сумма N чисел больших N/2 должна быть в точности равна N*N/2.

score 3 · Answer 10 · answered Jul 28 '12 at 10:52

3

Не во всех. К примеру, 4 человека. И сели они через одного - unix, windows, unix, windows.

W________U 
|сок пиво|
|сок пиво|
U________W

Даже если она будет крутить стол - напитки будут соответствовать только у половины админов.

answered Jul 28 '12 at 10:52

Nadia

31

По условию у большинства уже не свой напиток, а у Вас поровну. – ReinRaus Jul 28 '12 at 10:55

score 3 · Answer 11 · edited Jul 30 '12 at 21:01

По условию, рассмотрим только случай, когда большинство не получило свой напиток, а про все остальные случаи просто забудем. Определяющим предложением здесь является то, что представителей *nix и windows 50 на 50. И так, у скольких ребят из windows не свой напиток, у стольких ребят из nix опять же не свой. Учитывая предыдущее предложение, отсюда следует то, что крутя стол, мы получим случай, когда nix'ы и windows'ы поменяют свои напитки и ситуация поменяется в обратную сторону, т. е большинство получит свои напитки. Можно запустить програмку-перебор с использование функции random, которая работала бы следующим образом: для определённого случая, когда большинство не получило свой напиток, крутит стол и фиксирует тот момент, когда большинство получает свой напиток. Дальше меняет этот самый случай на другой произвольный, удовлетворяющий условию, и опять же крутит стол. Таким образом, для какого то миллиона случаев, мы экспериментально доказываем требуемое.

Кабак по случаю дня сисадмина

11 Answers11