Dado $n$ cartas colocadas en una mesa redonda de forma invertida, encuentra las operaciones mínimas para que queden boca arriba?

Question

Tengo $n$ tarjetas que se colocan en una mesa redonda de manera que $1$ se coloca entre $n$ y $2$ de manera invertida. Necesito encontrar el mínimo número de operaciones para que queden boca arriba dado que al voltear una carta $i$ También es necesario alternar las dos tarjetas adyacentes.

Por ejemplo Sea $3$ Las cartas se colocan boca abajo en una mesa redonda de forma que $1$ se coloca entre $2$ y $3, 2$ se coloca entre $1$ y $3$ y $3$ se coloca entre $1$ y $2$ . Ahora, si volteo la tarjeta $1$ entonces las dos tarjetas adyacentes ( $2$ y $3$ ) también cambiarán (si están orientados hacia abajo, ahora estarán orientados hacia arriba o viceversa) y los tres estarán orientados hacia arriba ahora.

Mi enfoque Si n%3=0, entonces las operaciones necesarias son n/3. Pero no soy capaz de averiguar cuál será el mínimo de operaciones cuando n%3=1 o 2. He tomado algunos ejemplos y he descubierto que para n=4, se necesitarán 4 operaciones. Para n=7, se necesitarán 7 operaciones. Por lo tanto, se necesitarán n operaciones para n tarjetas cuando n%3=1 o 2. Pero desafortunadamente, esta no es la respuesta correcta.

Answer 1

$1$ se coloca entre $n$ y $2$ así que asumo que hay al menos 3 tarjetas.

Creo que $n$ son necesarias cuando $n \equiv 1 \mod 3$ o $n \equiv 2 \mod 3$ .

Nunca es una buena opción elegir la misma carta dos veces. Sólo cambiarás la orientación de la carta y las dos cartas adyacentes dos veces más y no pasa nada.

De cada tres cartas subsiguientes se debe elegir al menos una, de lo contrario la del medio se quedará definitivamente boca abajo.

Hay $n$ formas en las que puedo elegir los triples. Si sólo elegimos una carta de cada triple, entonces $n$ veces una carta sería elegida. Sin embargo, cada carta está en tres triples y, por lo tanto, el número de cartas elegidas es $n/3$ ¡Una contradicción!

Así que debe haber un triple en el que se haya elegido más de una carta. La carta del medio debe ser volteada un número impar de veces. Por lo tanto, las tres cartas del triple son elegidas.

Movemos el triple por una carta a la vez. Sólo se puede elegir una o tres cartas del triple, así que por inducción encontramos que todas las cartas de la mesa deben ser elegidas exactamente una vez.