Jogando moedas em um círculo

Question

Temos um conjunto de N moedas que são colocadas em um círculo. Todos eles têm "Caudas" como face para cima. As moedas são todas distintas e têm números (1,2,3 ... N) escritos nelas.

Em cada movimento, lançamos quaisquer 3 moedas consecutivas. Ou seja, considere:

HHHTT

Se eu decidir lançar as moedas 3,4 e 5, então terei: HHTHH

Agora, pode haver 2 ^ N permutações cara-coroa distintas de N moedas distintas.

1.Prove / refute que existe um conjunto finito de movimentos nos quais podemos chegar a qualquer uma das (2 ^ N) permutação cara-coroa dessas N moedas, a partir da permutação inicial de todas as caudas.

2. Além disso, se alcançar qualquer permutação é de fato possível, então qual é o número máximo de movimentos necessários para obter qualquer permutação a partir da permutação inicial de todas as caudas.

Para esclarecimentos adicionais, se N fosse 3, por exemplo, então as 2 ^ 3 permutações distintas dessas 3 moedas seriam:

TTT

TTH

THT

THH

HHH

HHT

HTH

HTT

Answer 1

Vamos assumir $N \geq 3$ou então o problema não está bem definido.

Parte 1:

A posição final de uma moeda depende apenas de quantas vezes ela foi lançada (número par de jogadas, será T; número ímpar, H).

Portanto, os movimentos (consistindo em três flips) são comutativos. Além disso, os movimentos são claramente autoinversos, então não há por que fazer o mesmo movimento duas vezes. Então, precisamos nos preocupar apenas com conjuntos (desordenados) de posições de movimento (das quais também existem$2^N$)

Se nem todas as posições forem alcançáveis, dois conjuntos de movimentos diferentes devem dar o mesmo resultado. Mas isso significa que a diferença simétrica (XOR) entre esses conjuntos de movimentos deve dar a configuração com todos os T. Então, podemos perguntar se existe algum conjunto de movimentos não vazio que dá todos os T.

Para qualquer conjunto de movimentos, cada moeda será lançada entre 0 e 3 vezes. Além disso, o número de lançamentos para moedas adjacentes deve diferir apenas por 0 ou 1. (Há apenas um movimento que lançam$x$ e não $x + 1$e vice-versa.) Assim, para obter todo T, o número de lançamentos deve ser todo 0 ou todo 2. Todo 0 só é possível com o conjunto de movimentos vazio. E os 2?

O número total de lançamentos deve ser um múltiplo de 3 porque cada movimento lança três moedas. Portanto, é impossível obter todos os 2, a menos que$N$ é um múltiplo de 3. Se $N$é um múltiplo de 3 é fácil. Cada moeda pode ser lançada movendo-se em cada terceira posição. Então podemos fazer a mesma coisa novamente, mas mudamos 1 para virá-los de volta.

Assim, cada posição final é alcançável se e somente se$N$não é divisível por 3.

Parte 2:

Se cada posição for alcançável, então cada conjunto de movimento atinge uma posição diferente. Em particular, o conjunto de todas as posições de movimento atinge uma determinada posição final em$N$movimentos, e nenhuma outra posição exigirá mais do que tantos movimentos. Esta posição particular é, na verdade, toda H, uma vez que lançará cada moeda 3 vezes.

Para calcular rapidamente o conjunto de movimentos para uma determinada posição final, sugiro primeiro computar o conjunto de movimentos que apenas lança a moeda 1. Então sabemos como lançar qualquer moeda única mudando este conjunto de movimentos. E então podemos calcular qualquer resultado combinando conjuntos de movimentos de moeda única (com diferença simétrica / XOR).

Answer 2

Abordagem menos "matemática":

É óbvio que o problema de se chegar à configuração arbitrária equivale a um conjunto de lances que joga exatamente uma moeda.

Agora como encontrá-lo:

Você pode construir facilmente a sequência de lançamento necessária usando a sequência 1,2,4,5,7, ... (os números correspondem à moeda inicial, 1 significa lançar as moedas 1,2,3). Isso lançará a moeda 2 (N = 3k + 1) ou N (N = 3k + 2). A construção é óbvia, comece com a moeda 1 que você está definindo como cara no primeiro movimento, continue lançando todo o resto para que haja apenas 1-2 caras se propagando em direção ao "fim" do círculo. Assim que essas cabeças (quase) encontrarem a primeira, execute a virada final. Com N = 3k + 1 você ganha uma cara no final e acaba lançando apenas a moeda 2, com N = 3k + 2 você ganha uma cara 1 antes do final e lança apenas a moeda N. Com N = 3k você ganha 2 moedas em o fim e alcançar todas as caudas. Como você não pode "espremer" aquelas moedas para ficar com uma única "cara", não é possível alcançar todas as configurações.

Agora, o pior caso:

Para obter todas as caras, você precisa que todas as moedas sejam viradas 1 ou 3 vezes. Obviamente, você não pode fazer todas as moedas serem lançadas 1 vez com N = 3k + 1 ou 2. Se uma moeda X for lançada 3 vezes, a moeda X + 1 já foi lançada 2 vezes e precisa ser lançada mais uma vez etc, provando você precisa virar todas as moedas 3 vezes para obter todas as caras de todas as coroas iniciais.