MÉTODOS DE RECUENTO

Ayuda para el Problema 8

Probar en primer lugar que cada elemento del conjunto B está exactamente en dos de los conjuntos A_i. Supongamos a continuación que se puede realizar una asignación como la que se pide en el enunciado. Contando las etiquetas 0 en los distintos A_i, deducir que n debe ser par. Recíprocamente, supongamos ahora que n es par. Para cada i distinto de j, llamemos a_ij al único elemento de B que está en A_i y en A_j, de modo que a_ij = a_ji. Observar que, para dar una asignación a los elementos a_ij como la que se pide en el enunciado basta construir una matriz de tamaño (2n+1)x(2n+1) con entradas 0 ó 1 que sea simétrica respecto a la diagonal principal y que en cada fila tenga exactamente n ceros fuera de la diagonal principal. (En realidad, los valores sobre la diagonal principal no juegan ningún papel en el argumento.) Teniendo en cuenta que 2n es divisible por 4, esta matriz es fácil de conseguir con  franjas diagonales de ceros y franjas diagonales de unos.