Rompecabezas | Los contadores y el tablero – Part 1

Dadas 2n fichas donde n > 1. Tienes que colocar estas 2n fichas en un tablero de n × n de modo que no haya más de dos fichas en la misma fila, columna o diagonal. Solución: Ya que necesitamos colocar 2n fichas en n filas y n columnas del tablero nxn dado, con la condición de que puede haber como máximo dos fichas en la misma fila o en la misma columna. A partir de esto, podemos concluir que se deben colocar exactamente dos fichas en cada fila y columna. Caso 1 :Incluso para n = 2k, podemos obtener una solución mediante la colocación idéntica de n fichas en las primeras k columnas y en las últimas k columnas, como se explica a continuación. Supongamos que las filas y columnas del tablero están numeradas de arriba a abajo y de izquierda a derecha, respectivamente. Se colocan dos fichas en las dos primeras filas de las columnas 1 y k+1, dos fichas en las filas 3 y 4 de las columnas 2 y k+2, y así sucesivamente, hasta que finalmente se colocan fichas en las filas n – 1 y n de las columnas k y 2k. Entendamos esto con la ayuda de un ejemplo cuando n = 8:

2n Problema de contadores para n = 8

Caso 2: Para n impar = 2k + 1, k > 0, podemos obtener una solución colocando dos fichas en las filas 1 y 2 de la columna 1, dos fichas en las filas 3 y 4 de la columna 2, y así sucesivamente hasta que las fichas sean colocado en las filas n – 2 y n – 1 de la columna k. Luego se colocan dos fichas en la primera y última fila de la columna k + 1. Luego se colocan k fichas en la parte derecha del tablero simétricamente con respecto al cuadrado central del tablero a las de la parte izquierda: se colocan dos fichas en las filas 2 y 3 de la columna k + 2, en las filas 4 y 5 de la columna k + 3, y así sucesivamente, hasta las filas n – 1 y n de la última columna. Entendamos esto con la ayuda de un ejemplo cuando n = 7 :

2n contrarresta el problema para n = 7

Referencias: Rompecabezas algorítmicos – Anany Levitin, Maria Levitin