Lanciare monete in cerchio

Question

Abbiamo una serie di N monete che sono tutte posizionate in un cerchio. Hanno tutti "Tails" come lato a faccia in su. Le monete sono tutte distinte e hanno numeri (1,2,3 ... N) scritti su di loro.

In ogni mossa, lanciamo 3 monete consecutive qualsiasi. Cioè, considera:

HHHTT

Se decido di lanciare le monete 3,4 e 5, otterrò: HHTHH

Ora, ci possono essere 2 ^ N permutazioni testa-coda distinte di N monete distinte.

1. Dimostrare / confutare che esiste un insieme finito di mosse in cui possiamo raggiungere una qualsiasi delle permutazioni testa-croce (2 ^ N) di queste N monete, dalla permutazione iniziale di tutte le code.

2.Inoltre, se è effettivamente possibile raggiungere una qualsiasi permutazione, qual è il numero massimo di mosse necessarie per ottenere una permutazione dalla permutazione iniziale di tutte le code.

Per ulteriori chiarimenti, se N fosse 3, ad esempio, le 2 ^ 3 permutazioni distinte di queste 3 monete sarebbero:

TTT

TTH

THT

THH

HHH

HHT

HTH

HTT

Answer 1

Supponiamo $N \geq 3$oppure il problema non è ben definito.

Parte 1:

la posizione finale di una moneta dipende solo da quante volte è stata lanciata (numero pari di lanci, sarà T; numero dispari, H).

Quindi, le mosse (costituite da tre lanci) sono commutative. Inoltre, le mosse sono chiaramente auto-inverse, quindi non ha senso fare la stessa mossa due volte. Quindi, dobbiamo occuparci solo di insiemi (non ordinati) di posizioni di spostamento (di cui esistono anche$2^N$).

Se non tutte le posizioni sono raggiungibili, allora due diversi set di mosse devono dare lo stesso risultato. Ma ciò significa che la differenza simmetrica (XOR) tra questi set di mosse deve dare la configurazione con tutte le T. Quindi possiamo invece chiedere se c'è qualche set di mosse non vuoto che dà tutta la T.Per

ogni set di mosse, ogni moneta verrà lanciata tra 0 e 3 volte. Inoltre, il numero di lanci per monete adiacenti deve differire solo di 0 o 1. (C'è solo una mossa per quel lancio$x$ e non $x + 1$e viceversa.) Quindi, per ottenere tutto T, il numero di lanci deve essere tutto 0 o tutto 2. Tutto 0 è possibile solo con l'insieme di mosse vuoto. E tutti e 2?

Il numero totale di lanci deve essere un multiplo di 3 perché ogni mossa lancia tre monete. Quindi, è impossibile ottenere tutti e 2 a meno che$N$ è un multiplo di 3. If $N$è un multiplo di 3 è facile. Ogni moneta può essere lanciata spostandosi in ogni terza posizione. Quindi possiamo fare di nuovo la stessa cosa ma spostati di 1 per capovolgerli.

Quindi, ogni posizione finale è raggiungibile se e solo se$N$non è divisibile per 3.

Parte 2:

se ogni posizione è raggiungibile, ogni serie di mosse raggiunge una posizione diversa. In particolare, l'insieme di tutte le posizioni di spostamento raggiunge una certa posizione finale in$N$e nessun'altra posizione richiederà più di tante mosse. Questa particolare posizione è in realtà tutta H in quanto lancerà ogni moneta 3 volte.

Per calcolare rapidamente il set di mosse per una data posizione finale, suggerirei di calcolare prima il set di mosse che lancia la moneta 1. Quindi sappiamo come lanciare una singola moneta spostando questo set di mosse. Quindi possiamo calcolare qualsiasi risultato combinando set di movimenti di monete singole (con differenza simmetrica / XOR).

Answer 2

Approccio meno "mathy":

È ovvio che il problema per raggiungere una configurazione arbitraria equivale a un insieme di mosse che lancia esattamente una moneta.

Ora come trovarlo:

Puoi facilmente costruire la sequenza di lancio richiesta usando la sequenza 1,2,4,5,7, ... (i numeri corrispondono alla moneta iniziale, 1 significa lanciare monete 1,2,3). Questo lancerà la moneta 2 (N = 3k + 1) o N (N = 3k + 2). La costruzione è ovvia, inizia con la moneta 1 che stai impostando come testa con la prima mossa, continua a lanciare tutto il resto in modo che ci siano solo 1-2 teste che si propagano verso la "fine" del cerchio. Una volta che quelle teste (quasi) incontrano la tua prima, esegui il lancio finale. Con N = 3k + 1 ottieni una testa alla fine e finisci per lanciare solo la moneta 2, con N = 3k + 2 ottieni una testa 1 prima della fine e lancia solo la moneta N. Con N = 3k ottieni 2 monete a alla fine e raggiungere tutte le code. Poiché non puoi "spremere" quelle monete per essere lasciate con una sola "testa", non è possibile raggiungere tutte le configurazioni.

Ora il caso peggiore:

Per ottenere tutte le teste è necessario che tutte le monete vengano girate 1 o 3 volte. Ovviamente non puoi fare in modo che tutte le monete vengano lanciate 1 volta con N = 3k + 1 o 2. Se una moneta X viene lanciata 3 volte, la moneta X + 1 è già stata girata 2 volte e deve essere girata ancora una volta ecc., Dimostrando devi lanciare tutte le monete 3 volte per ottenere tutte le teste dalle iniziali tutte le code.