Rzucanie monet w kole

Question

Mamy zestaw N monet umieszczonych w kółku. Wszystkie mają „Ogony” na odwrocie. Wszystkie monety są różne i mają zapisane numery (1, 2, 3 ... N).

W każdym ruchu rzucamy 3 kolejne monety. To znaczy, rozważ:

HHHTT

Jeśli zdecyduję się rzucić monetami 3,4 i 5 to otrzymam: HHTHH

Teraz może istnieć 2 ^ N różnych permutacji reszek z N różnych monet.

1) Udowodnić / obalić, że istnieje skończony zestaw ruchów, w których możemy osiągnąć dowolną z (2 ^ N) permutacji orzeł-reszka tych N monet, od początkowej permutacji wszystkich reszek.

2) Ponadto, jeśli osiągnięcie jakiejkolwiek permutacji jest rzeczywiście możliwe, to jaka jest maksymalna liczba ruchów potrzebna do uzyskania dowolnej permutacji z początkowej permutacji wszystkich ogonów.

Dla dalszego wyjaśnienia, jeśli na przykład N wynosi 3, to 2 ^ 3 różne permutacje tych 3 monet wyglądałyby następująco:

TTT

TTH

THT

THH

HHH

HHT

HTH

HTT

Answer 1

Załóżmy $N \geq 3$albo problem nie jest dobrze zdefiniowany.

Część 1:

Końcowa pozycja monety zależy tylko od tego, ile razy została ona przewrócona (parzysta liczba rzutów, będzie to T; liczba nieparzysta, H).

Tak więc ruchy (składające się z trzech rzutów) są przemienne. Ponadto ruchy są wyraźnie samoodwrotne, więc nie ma sensu wykonywać tego samego ruchu dwa razy. Musimy więc zajmować się tylko (nieuporządkowanymi) zestawami pozycji ruchu (których również są$2^N$).

Jeśli nie wszystkie pozycje są osiągalne, dwa różne zestawy ruchów muszą dać ten sam wynik. Ale to oznacza, że ​​symetryczna różnica (XOR) między tymi zestawami ruchów musi dać konfigurację ze wszystkimi T. Więc zamiast tego możemy zapytać, czy istnieje jakiś niepusty zestaw ruchów, który daje wszystkie T.

Dla każdego zestawu ruchów każda moneta zostanie odwrócona od 0 do 3 razy. Ponadto liczba rzutów sąsiednich monet może różnić się tylko o 0 lub 1. (Podczas tego rzutu jest tylko jeden ruch$x$ i nie $x + 1$i na odwrót.) Tak więc, aby uzyskać wszystkie T, liczba rzutów musi wynosić albo wszystkie 0, albo wszystkie 2. Wszystkie 0 jest możliwe tylko przy pustym zestawie ruchów. A co z wszystkimi 2?

Całkowita liczba rzutów musi być wielokrotnością 3, ponieważ każdy ruch powoduje odwrócenie trzech monet. Tak więc niemożliwe jest zdobycie wszystkich 2, chyba że$N$ jest wielokrotnością 3. Jeśli $N$jest wielokrotnością 3, to jest łatwe. Każdą monetę można obrócić, przesuwając się o co trzecią pozycję. Następnie możemy zrobić to samo ponownie, ale przesunąć o 1, aby je odwrócić.

Zatem każda pozycja końcowa jest osiągalna wtedy i tylko wtedy, gdy$N$nie jest podzielna przez 3.

Część 2:

Jeśli każda pozycja jest osiągalna, to każdy zestaw ruchów osiąga inną pozycję. W szczególności zestaw wszystkich pozycji ruchu osiąga określoną pozycję końcową w$N$ruchy, a żadna inna pozycja nie będzie wymagać więcej niż tyle ruchów. Ta konkretna pozycja to właściwie całe H, ponieważ każda moneta zostanie rzucona 3 razy.

Aby szybko obliczyć ruch ustawiony dla danej pozycji końcowej, sugerowałbym najpierw obliczenie zestawu ruchów, który po prostu obraca monetą 1. Następnie wiemy, jak obrócić pojedynczą monetę, przesuwając ten zestaw ruchów. Następnie możemy obliczyć dowolny wynik, łącząc zestawy ruchów pojedynczych monet (z symetryczną różnicą / XOR).

Answer 2

Mniej „matowe” podejście:

Oczywiste jest, że problem z osiągnięciem dowolnej konfiguracji jest równoważny z zestawem ruchów, w których rzuca się dokładnie jedną monetą.

Teraz jak to znaleźć:

Możesz łatwo skonstruować wymaganą sekwencję przerzucania używając sekwencji 1,2,4,5,7, ... (liczby odpowiadają początkowej monecie, 1 oznacza rzucanie monet 1, 2, 3). To spowoduje rzut monetą 2 (N = 3k + 1) lub N (N = 3k + 2). Konstrukcja jest oczywista, zacznij od monety 1, którą ustawiasz jako orła w pierwszym ruchu, całą resztę odwracaj tak, aby w kierunku „końca” koła rozchodziły się tylko 1-2 głowy. Gdy te głowy (prawie) spotkają się z twoją pierwszą, wykonaj ostatni rzut. Przy N = 3k + 1 dostajesz jedną reszkę na końcu i kończysz rzutem tylko monetą 2, przy N = 3k + 2 dostajesz jedną reszkę 1 przed końcem i rzucasz tylko monetą N. Przy N = 3k dostajesz 2 monety w koniec i dotrzeć do wszystkich ogonów. Ponieważ nie można „wycisnąć” tych monet, aby zostały z pojedynczą „głowicą”, nie jest możliwe osiągnięcie wszystkich konfiguracji.

Teraz najgorszy przypadek:

Aby zdobyć wszystkie głowy, musisz obrócić wszystkie monety 1 lub 3 razy. Oczywiście nie możesz sprawić, aby wszystkie monety zostały przerzucone 1 raz z N = 3k + 1 lub 2. Jeśli moneta X zostanie rzucona 3 razy, moneta X + 1 została już obrócona 2 razy i musi zostać obrócona jeszcze raz itd. musisz rzucić wszystkie monety 3 razy, aby uzyskać wszystkie głowy z początkowych wszystkich ogonów.