Réponse à une question de Christian Lemay

02 avril 2016 | Catégories: math | View Comments

Mon ami Christian Lemay, créateur de jeux de sociétés, a récemment posé la question suivante:

Amis mathématiciens...
J'ai 6 critères (1-2-3-4-5-6).
Les 3 premiers critères ont trois "variantes", "possibilités", "déclinaisons" (?)
Les 3 derniers ont 4 variantes.

Je veux savoir j'ai combien de combinaisons possibles, sachant que toutes
les combinaisons doivent avoir au minimum 2 différences et qu'un même
attribut soit partagé par au moins 3 personnages. Quelqu'un peut m'aider à
trouver la formule?

J'ai écrit le code suivant:

import itertools
from collections import Counter
L3 = range(3)
L4 = range(4)
S = set(itertools.product(L3,L3,L3,L4,L4,L4))
def distance(x,y):
    return sum(1 for a,b in zip(x,y) if a!=b)
def distance1_voisins(x):
    return [s for s in S if distance(x,s) == 1]
def trouve_ce_que_christian_veut():
    possible = copy(S)
    A = set()
    while possible:
        a = choice(list(possible))
        possible.remove(a)
        A.add(a)
        voisins = distance1_voisins(a)
        possible.difference_update(voisins)
    return A
def verifie(A):
    print "Nombre de sommets:", len(A)
    L = [distance(a,b) for a,b in itertools.product(A, repeat=2) if a!=b]
    print "Distance entre paires de sommets distincts:"
    print Counter(L)
    print "Nombre de combinaisons partageant le même attribut:"
    for i in range(6):
        print Counter(s[i] for s in A)

Il y a 1728 possiblités. Elles sont représentées dans l'ensemble S:

sage: 4^3*3^3
1728
sage: len(S)
1728

Ma méthode choisit un élément aléatoire de l'ensemble S puis élimine toutes les possibilités qui ont une seule différence avec cet élément choisi. Puis, on refait jusqu'à ce qu'il ne reste plus possibilités. Comme la méthode est aléatoire, le résultat n'est pas toujours le même. En gros, ça varie entre 284 et 297:

sage: A = trouve_ce_que_christian_veut()
sage: len(A)
284
sage: A = trouve_ce_que_christian_veut()
sage: len(A)
288
sage: A = trouve_ce_que_christian_veut()
sage: len(A)
291

En voici un où je teste les contraintes données par Christian:

sage: A = trouve_ce_que_christian_veut()
sage: len(A)
296
sage: verifie(A)
Nombre de sommets: 296
Distance entre paires de sommets distincts:
Counter({4: 28928, 5: 27188, 3: 14268, 6: 10972, 2: 5964})
Nombre de combinaisons partageant le même attribut:
Counter({1: 101, 0: 98, 2: 97})
Counter({2: 100, 0: 99, 1: 97})
Counter({1: 104, 0: 97, 2: 95})
Counter({3: 77, 1: 74, 0: 73, 2: 72})
Counter({3: 80, 2: 75, 1: 71, 0: 70})
Counter({1: 76, 3: 76, 2: 73, 0: 71})

On remarque que le deuxième critère est automatiquement vérifié comme au moins environ 70 possibilités partagent le même attribut.

J'imagine que la motivation de Christian est d'obtenir un tel ensemble. Alors, voici. Les éléments de l'ensemble A de 296 éléments ci-haut sont:

sage: A
{(0, 0, 0, 0, 2, 2),
 (0, 0, 0, 0, 3, 1),
 (0, 0, 0, 1, 0, 3),
 (0, 0, 0, 1, 2, 1),
 (0, 0, 0, 1, 3, 0),
 (0, 0, 0, 2, 0, 1),
 (0, 0, 0, 2, 1, 3),
 (0, 0, 0, 2, 2, 0),
 (0, 0, 0, 3, 0, 0),
 (0, 0, 0, 3, 1, 2),
 (0, 0, 0, 3, 2, 3),
 (0, 0, 1, 0, 0, 2),
 (0, 0, 1, 0, 1, 3),
 (0, 0, 1, 0, 3, 0),
 (0, 0, 1, 1, 1, 2),
 (0, 0, 1, 1, 2, 3),
 (0, 0, 1, 1, 3, 1),
 (0, 0, 1, 2, 0, 3),
 (0, 0, 1, 2, 1, 1),
 (0, 0, 1, 3, 1, 0),
 (0, 0, 1, 3, 2, 1),
 (0, 0, 1, 3, 3, 3),
 (0, 0, 2, 0, 0, 0),
 (0, 0, 2, 0, 1, 2),
 (0, 0, 2, 0, 2, 1),
 (0, 0, 2, 0, 3, 3),
 (0, 0, 2, 1, 1, 1),
 (0, 0, 2, 1, 2, 2),
 (0, 0, 2, 2, 1, 0),
 (0, 0, 2, 2, 2, 3),
 (0, 0, 2, 3, 0, 2),
 (0, 0, 2, 3, 1, 3),
 (0, 1, 0, 0, 0, 1),
 (0, 1, 0, 0, 1, 2),
 (0, 1, 0, 0, 2, 3),
 (0, 1, 0, 1, 1, 0),
 (0, 1, 0, 1, 2, 2),
 (0, 1, 0, 1, 3, 1),
 (0, 1, 0, 2, 0, 3),
 (0, 1, 0, 2, 1, 1),
 (0, 1, 0, 2, 3, 0),
 (0, 1, 0, 3, 1, 3),
 (0, 1, 0, 3, 2, 1),
 (0, 1, 0, 3, 3, 2),
 (0, 1, 1, 0, 0, 3),
 (0, 1, 1, 0, 1, 0),
 (0, 1, 1, 0, 2, 2),
 (0, 1, 1, 1, 0, 0),
 (0, 1, 1, 1, 1, 1),
 (0, 1, 1, 1, 3, 3),
 (0, 1, 1, 2, 2, 0),
 (0, 1, 1, 2, 3, 2),
 (0, 1, 1, 3, 0, 2),
 (0, 1, 1, 3, 2, 3),
 (0, 1, 2, 0, 1, 3),
 (0, 1, 2, 1, 0, 3),
 (0, 1, 2, 1, 2, 1),
 (0, 1, 2, 1, 3, 2),
 (0, 1, 2, 2, 0, 1),
 (0, 1, 2, 2, 1, 2),
 (0, 1, 2, 2, 3, 3),
 (0, 1, 2, 3, 2, 0),
 (0, 1, 2, 3, 3, 1),
 (0, 2, 0, 0, 1, 3),
 (0, 2, 0, 0, 2, 1),
 (0, 2, 0, 0, 3, 0),
 (0, 2, 0, 1, 1, 2),
 (0, 2, 0, 1, 2, 3),
 (0, 2, 0, 2, 0, 0),
 (0, 2, 0, 2, 3, 1),
 (0, 2, 0, 3, 0, 1),
 (0, 2, 0, 3, 2, 0),
 (0, 2, 0, 3, 3, 3),
 (0, 2, 1, 0, 0, 0),
 (0, 2, 1, 0, 1, 2),
 (0, 2, 1, 0, 3, 3),
 (0, 2, 1, 1, 0, 2),
 (0, 2, 1, 1, 1, 0),
 (0, 2, 1, 1, 2, 1),
 (0, 2, 1, 2, 0, 1),
 (0, 2, 1, 2, 1, 3),
 (0, 2, 1, 2, 2, 2),
 (0, 2, 1, 2, 3, 0),
 (0, 2, 1, 3, 0, 3),
 (0, 2, 1, 3, 1, 1),
 (0, 2, 1, 3, 3, 2),
 (0, 2, 2, 0, 0, 2),
 (0, 2, 2, 0, 1, 0),
 (0, 2, 2, 0, 2, 3),
 (0, 2, 2, 0, 3, 1),
 (0, 2, 2, 1, 0, 1),
 (0, 2, 2, 1, 2, 0),
 (0, 2, 2, 1, 3, 3),
 (0, 2, 2, 2, 0, 3),
 (0, 2, 2, 2, 2, 1),
 (0, 2, 2, 2, 3, 2),
 (0, 2, 2, 3, 1, 2),
 (0, 2, 2, 3, 3, 0),
 (1, 0, 0, 0, 0, 0),
 (1, 0, 0, 0, 2, 1),
 (1, 0, 0, 0, 3, 2),
 (1, 0, 0, 1, 1, 2),
 (1, 0, 0, 1, 2, 0),
 (1, 0, 0, 1, 3, 3),
 (1, 0, 0, 2, 0, 2),
 (1, 0, 0, 2, 1, 1),
 (1, 0, 0, 2, 2, 3),
 (1, 0, 0, 3, 1, 3),
 (1, 0, 0, 3, 2, 2),
 (1, 0, 0, 3, 3, 1),
 (1, 0, 1, 0, 0, 3),
 (1, 0, 1, 0, 2, 0),
 (1, 0, 1, 0, 3, 1),
 (1, 0, 1, 1, 0, 1),
 (1, 0, 1, 1, 1, 3),
 (1, 0, 1, 1, 2, 2),
 (1, 0, 1, 1, 3, 0),
 (1, 0, 1, 2, 0, 0),
 (1, 0, 1, 2, 2, 1),
 (1, 0, 1, 2, 3, 3),
 (1, 0, 1, 3, 1, 2),
 (1, 0, 1, 3, 2, 3),
 (1, 0, 2, 0, 0, 1),
 (1, 0, 2, 0, 1, 3),
 (1, 0, 2, 1, 1, 0),
 (1, 0, 2, 1, 2, 1),
 (1, 0, 2, 2, 2, 2),
 (1, 0, 2, 2, 3, 0),
 (1, 0, 2, 3, 0, 3),
 (1, 0, 2, 3, 1, 1),
 (1, 0, 2, 3, 2, 0),
 (1, 0, 2, 3, 3, 2),
 (1, 1, 0, 0, 0, 3),
 (1, 1, 0, 0, 1, 1),
 (1, 1, 0, 0, 2, 2),
 (1, 1, 0, 0, 3, 0),
 (1, 1, 0, 1, 0, 0),
 (1, 1, 0, 1, 2, 3),
 (1, 1, 0, 1, 3, 2),
 (1, 1, 0, 2, 1, 0),
 (1, 1, 0, 2, 2, 1),
 (1, 1, 0, 2, 3, 3),
 (1, 1, 0, 3, 0, 1),
 (1, 1, 1, 0, 0, 2),
 (1, 1, 1, 0, 2, 1),
 (1, 1, 1, 0, 3, 3),
 (1, 1, 1, 1, 1, 0),
 (1, 1, 1, 2, 1, 3),
 (1, 1, 1, 2, 2, 2),
 (1, 1, 1, 2, 3, 1),
 (1, 1, 1, 3, 0, 3),
 (1, 1, 1, 3, 1, 1),
 (1, 1, 1, 3, 2, 0),
 (1, 1, 1, 3, 3, 2),
 (1, 1, 2, 0, 0, 0),
 (1, 1, 2, 0, 3, 1),
 (1, 1, 2, 1, 0, 2),
 (1, 1, 2, 1, 2, 0),
 (1, 1, 2, 1, 3, 3),
 (1, 1, 2, 2, 0, 3),
 (1, 1, 2, 2, 1, 1),
 (1, 1, 2, 2, 3, 2),
 (1, 1, 2, 3, 1, 2),
 (1, 1, 2, 3, 2, 3),
 (1, 1, 2, 3, 3, 0),
 (1, 2, 0, 0, 0, 2),
 (1, 2, 0, 0, 3, 1),
 (1, 2, 0, 1, 1, 0),
 (1, 2, 0, 1, 2, 1),
 (1, 2, 0, 2, 0, 3),
 (1, 2, 0, 2, 2, 2),
 (1, 2, 0, 2, 3, 0),
 (1, 2, 0, 3, 0, 0),
 (1, 2, 0, 3, 1, 1),
 (1, 2, 0, 3, 2, 3),
 (1, 2, 0, 3, 3, 2),
 (1, 2, 1, 0, 1, 1),
 (1, 2, 1, 0, 2, 3),
 (1, 2, 1, 0, 3, 0),
 (1, 2, 1, 1, 1, 2),
 (1, 2, 1, 1, 2, 0),
 (1, 2, 1, 1, 3, 3),
 (1, 2, 1, 2, 3, 2),
 (1, 2, 1, 3, 0, 2),
 (1, 2, 1, 3, 1, 3),
 (1, 2, 1, 3, 3, 1),
 (1, 2, 2, 0, 1, 2),
 (1, 2, 2, 0, 2, 1),
 (1, 2, 2, 1, 0, 3),
 (1, 2, 2, 1, 1, 1),
 (1, 2, 2, 1, 3, 2),
 (1, 2, 2, 2, 0, 2),
 (1, 2, 2, 2, 1, 3),
 (1, 2, 2, 2, 2, 0),
 (1, 2, 2, 2, 3, 1),
 (1, 2, 2, 3, 0, 1),
 (1, 2, 2, 3, 1, 0),
 (1, 2, 2, 3, 2, 2),
 (1, 2, 2, 3, 3, 3),
 (2, 0, 0, 0, 0, 1),
 (2, 0, 0, 0, 1, 0),
 (2, 0, 0, 0, 2, 3),
 (2, 0, 0, 1, 0, 0),
 (2, 0, 0, 1, 1, 3),
 (2, 0, 0, 1, 2, 2),
 (2, 0, 0, 1, 3, 1),
 (2, 0, 0, 2, 2, 1),
 (2, 0, 0, 2, 3, 2),
 (2, 0, 0, 3, 3, 0),
 (2, 0, 1, 0, 3, 3),
 (2, 0, 1, 1, 0, 2),
 (2, 0, 1, 1, 1, 0),
 (2, 0, 1, 1, 2, 1),
 (2, 0, 1, 2, 0, 1),
 (2, 0, 1, 2, 1, 3),
 (2, 0, 1, 2, 2, 2),
 (2, 0, 1, 2, 3, 0),
 (2, 0, 1, 3, 0, 3),
 (2, 0, 1, 3, 1, 1),
 (2, 0, 1, 3, 2, 0),
 (2, 0, 1, 3, 3, 2),
 (2, 0, 2, 0, 1, 1),
 (2, 0, 2, 0, 2, 0),
 (2, 0, 2, 0, 3, 2),
 (2, 0, 2, 1, 0, 1),
 (2, 0, 2, 1, 3, 0),
 (2, 0, 2, 2, 0, 3),
 (2, 0, 2, 2, 1, 2),
 (2, 0, 2, 2, 3, 1),
 (2, 0, 2, 3, 0, 0),
 (2, 0, 2, 3, 2, 1),
 (2, 0, 2, 3, 3, 3),
 (2, 1, 0, 0, 2, 1),
 (2, 1, 0, 0, 3, 2),
 (2, 1, 0, 1, 0, 3),
 (2, 1, 0, 1, 1, 1),
 (2, 1, 0, 1, 3, 0),
 (2, 1, 0, 2, 0, 0),
 (2, 1, 0, 2, 1, 3),
 (2, 1, 0, 2, 2, 2),
 (2, 1, 0, 2, 3, 1),
 (2, 1, 0, 3, 0, 2),
 (2, 1, 0, 3, 2, 0),
 (2, 1, 0, 3, 3, 3),
 (2, 1, 1, 0, 0, 0),
 (2, 1, 1, 0, 1, 2),
 (2, 1, 1, 0, 2, 3),
 (2, 1, 1, 0, 3, 1),
 (2, 1, 1, 1, 0, 1),
 (2, 1, 1, 1, 2, 0),
 (2, 1, 1, 1, 3, 2),
 (2, 1, 1, 2, 0, 3),
 (2, 1, 1, 2, 1, 1),
 (2, 1, 1, 3, 1, 3),
 (2, 1, 1, 3, 2, 1),
 (2, 1, 1, 3, 3, 0),
 (2, 1, 2, 0, 0, 3),
 (2, 1, 2, 0, 3, 0),
 (2, 1, 2, 1, 0, 0),
 (2, 1, 2, 1, 2, 3),
 (2, 1, 2, 2, 0, 2),
 (2, 1, 2, 2, 2, 0),
 (2, 1, 2, 3, 0, 1),
 (2, 1, 2, 3, 1, 0),
 (2, 1, 2, 3, 2, 2),
 (2, 2, 0, 0, 1, 2),
 (2, 2, 0, 0, 2, 0),
 (2, 2, 0, 0, 3, 3),
 (2, 2, 0, 1, 0, 1),
 (2, 2, 0, 1, 3, 2),
 (2, 2, 0, 3, 1, 3),
 (2, 2, 0, 3, 2, 2),
 (2, 2, 0, 3, 3, 1),
 (2, 2, 1, 0, 0, 1),
 (2, 2, 1, 0, 3, 2),
 (2, 2, 1, 1, 0, 3),
 (2, 2, 1, 1, 1, 1),
 (2, 2, 1, 1, 2, 2),
 (2, 2, 1, 1, 3, 0),
 (2, 2, 1, 2, 0, 2),
 (2, 2, 1, 2, 1, 0),
 (2, 2, 1, 2, 2, 3),
 (2, 2, 1, 2, 3, 1),
 (2, 2, 1, 3, 0, 0),
 (2, 2, 1, 3, 1, 2),
 (2, 2, 1, 3, 3, 3),
 (2, 2, 2, 0, 0, 0),
 (2, 2, 2, 0, 1, 3),
 (2, 2, 2, 0, 2, 2),
 (2, 2, 2, 1, 1, 2),
 (2, 2, 2, 1, 3, 1),
 (2, 2, 2, 2, 1, 1),
 (2, 2, 2, 2, 3, 0),
 (2, 2, 2, 3, 0, 3),
 (2, 2, 2, 3, 2, 0),
 (2, 2, 2, 3, 3, 2)}

Je suis d'accord avec Philippe Beaudoin qui répond sur Facebook:

De manière intéressante, c'est la même question que:, combien peut-on placer de "tour" (la pièce d'échec) sur un hyper-échiquier de 3x3x3x4x4x4 sans qu'aucune des pièces ne se menacent.

Il conjecture que la réponse optimale est 432:

En fait, je suis presque certain que la réponse est 432 (3x3x3x4x4).

Peut-être. Je n'ai pas réfléchi plus à la question. Mais, je ne vois pas comment la formule proposée par Philippe généralise la formule connue pour l'équiquier 8x8...

Sébastien Labbé

Réponse à une question de Christian Lemay