Blogue

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...

Read and Post Comments

Rues de mathématicien(ne)s à Paris

20 avril 2015 | Catégories: math | View Comments

/Files/2014/rue_ampere.jpg /Files/2014/rue_clairaut1.jpg /Files/2014/rue_dalembert.jpg /Files/2014/rue_dubreuil_jacotin.jpg /Files/2014/rue_fermat.jpg /Files/2014/rue_gassendi.jpg /Files/2014/rue_legendre.jpg /Files/2014/rue_monge.jpg /Files/2014/rue_sophie_germain.jpg

Et deux autres rues:

/Files/2014/rue_petits_carreaux.jpg /Files/2014/rue_tocqueville.jpg
Read and Post Comments

Calculer l'inverse d'une matrice rectangulaire

30 juillet 2012 | Catégories: math | View Comments

Existe-t-il des méthodes pour calculer l'inverse d'une matrice rectangulaire non carrée. Je me souviens qu'Ernest Monga nous avait fait travailler sur ce sujet dans un cours qu'il donnait à l'Université de Sherbrooke. Il a notamment donné une présentation Inverse généralisé d’une matrice quelconque – application à deux problèmes statistiques au camp 2011 de l'AMQ.

À l'aide de quelques conditions, il est possible de définir l'inverse d'une matrice rectangulaire de façon unique. Plus d'informations sont disponibles dans le livre Probabilités, analyse des données et statistique sur books.google.ca, sur Wikipédia Pseudo-inverse. Sur la page de wikipédia en anglais Moore-Penrose pseudoinverse, on trouve aussi une section Software libraries mentionnant que les librairies NumPy et SciPy peuvent calculer cette matrice pseudo-inverse.

sage: m = matrix(2, range(6))
sage: m
[0 1 2]
[3 4 5]
sage: mm = numpy.matrix(m)
sage: mm
matrix([[0, 1, 2],
        [3, 4, 5]])
sage: mm.I
matrix([[-0.77777778,  0.27777778],
        [-0.11111111,  0.11111111],
        [ 0.55555556, -0.05555556]])
sage: mm * mm.I
matrix([[  1.00000000e+00,  -1.38777878e-16],
        [  3.10862447e-15,   1.00000000e+00]])
sage: mm.I * mm
matrix([[ 0.83333333,  0.33333333, -0.16666667],
        [ 0.33333333,  0.33333333,  0.33333333],
        [-0.16666667,  0.33333333,  0.83333333]])

Alors que la fonction Moore-Penrose Matrix Inverse est présente dans Mathematica, je crois qu'elle n'est pas encore présente dans Sage sans passer par NumPy. Peut-être qu'une implémentation basée sur l'article Fast Computation of Moore-Penrose Inverse Matrices de Pierre Courrieu (2008) pourrait être effectuée.

Read and Post Comments
« Previous Page