Rompecabezas | Los Contadores y el Tablero Rectangular

Dadas 3N fichas, hay tres tipos de fichas Roja , Blanca y Azul , todas ellas iguales en número, es decir, N y un tablero rectangular con 3 filas y N columnas están llenos de fichas, la tarea es reorganizar las fichas de modo que cada La columna tiene contadores de tres colores diferentes. La única operación permitida es intercambiar las fichas en la misma fila. Diseñe un algoritmo para realizar esta tarea o demuestre que tal algoritmo no existe.

Solución:

1. Para N = 1: El problema es trivial ya que las 3 fichas de una columna son de diferentes colores.
2. Para N > 1: El problema se puede resolver colocando las fichas de 3 colores diferentes para la primera columna y luego resolviendo para la instancia más pequeña del problema. Considere la primera columna. Hay tres posibilidades:
   • Los tres contadores son de diferentes colores: en este caso, no es necesario hacer nada.
   • Exactamente dos fichas son del mismo color: supongamos que las dos fichas del mismo color son rojas y están en las dos primeras filas, mientras que la ficha de la primera fila, la tercera columna, es blanca, como se muestra. Dado que debe haber N fichas azules en el tablero, y no más de N-1 de ellas pueden estar en la tercera fila, esto implica que al menos una ficha de color azul debe estar en las dos primeras filas. Por lo tanto, el algoritmo requerido puede escanear las dos primeras filas, comenzando desde la segunda columna hasta encontrar una columna azul; después de encontrar un contador azul, debe intercambiarse con el contador de la primera columna.
     
   • Las tres fichas son del mismo color: supongamos que las tres fichas de la primera columna son rojas. Esto implica que cada una de las tres filas ahora debe contener al menos un contador de un color diferente al rojo, podemos, por lo tanto, escanear cualquier fila, para obtener un contador del color diferente e intercambiarlo con el contador en el primera columna para obtener la situación mencionada anteriormente.