Blogue

Wooden laser-cut Jeandel-Rao tiles

07 septembre 2018 | Catégories: sage, slabbe spkg, math | View Comments

I have been working on Jeandel-Rao tiles lately.

/Files/2018/article2_T0_tiles.svg

Before the conference Model Sets and Aperiodic Order held in Durham UK (Sep 3-7 2018), I thought it would be a good idea to bring some real tiles at the conference. So I first decided of some conventions to represent the above tiles as topologically closed disk basically using the representation of integers in base 1:

/Files/2018/T0_shapes.svg

With these shapes, I created a 33 x 19 patch. With 3cm on each side, the patch takes 99cm x 57cm just within the capacity of the laser cut machine (1m x 60 cm):

/Files/2018/33x19_A_scale3.svg

With the help of David Renault from LaBRI, we went at Coh@bit, the FabLab of Bordeaux University and we laser cut two 3mm thick plywood for a total of 1282 Wang tiles. This is the result:

/Files/2018/laser_cut_8x8.jpg

One may recreate the 33 x 19 tiling as follows (note that I am using Cartesian-like coordinates, so the first list data[0] actually is the first column from bottom to top):

sage: data = [[10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 2, 6, 1, 3, 8, 7, 0, 9, 7],
....:  [4, 5, 6, 1, 8, 10, 4, 0, 9, 3, 8, 7, 0, 9, 7, 5, 0, 9, 3],
....:  [3, 7, 6, 1, 7, 2, 5, 0, 9, 8, 7, 5, 0, 9, 3, 7, 0, 9, 10],
....:  [10, 4, 6, 1, 3, 8, 7, 0, 9, 7, 5, 6, 1, 8, 10, 4, 0, 9, 3],
....:  [2, 5, 6, 1, 8, 7, 5, 0, 9, 3, 7, 6, 1, 7, 2, 5, 0, 9, 8],
....:  [8, 7, 6, 1, 7, 5, 6, 1, 8, 10, 4, 6, 1, 3, 8, 7, 0, 9, 7],
....:  [7, 5, 6, 1, 3, 7, 6, 1, 7, 2, 5, 6, 1, 8, 7, 5, 0, 9, 3],
....:  [3, 7, 6, 1, 10, 4, 6, 1, 3, 8, 7, 6, 1, 7, 5, 6, 1, 8, 10],
....:  [10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 5, 6, 1, 3, 7, 6, 1, 7, 2],
....:  [2, 5, 6, 1, 8, 10, 4, 0, 9, 3, 7, 6, 1, 10, 4, 6, 1, 3, 8],
....:  [8, 7, 6, 1, 7, 5, 5, 0, 9, 10, 4, 6, 1, 3, 3, 7, 0, 9, 7],
....:  [7, 5, 6, 1, 3, 7, 6, 1, 10, 4, 5, 6, 1, 8, 10, 4, 0, 9, 3],
....:  [3, 7, 6, 1, 10, 4, 6, 1, 3, 3, 7, 6, 1, 7, 2, 5, 0, 9, 8],
....:  [10, 4, 6, 1, 3, 3, 7, 0, 9, 10, 4, 6, 1, 3, 8, 7, 0, 9, 7],
....:  [4, 5, 6, 1, 8, 10, 4, 0, 9, 3, 3, 7, 0, 9, 7, 5, 0, 9, 3],
....:  [3, 7, 6, 1, 7, 2, 5, 0, 9, 8, 10, 4, 0, 9, 3, 7, 0, 9, 10],
....:  [10, 4, 6, 1, 3, 8, 7, 0, 9, 7, 5, 5, 0, 9, 10, 4, 0, 9, 3],
....:  [2, 5, 6, 1, 8, 7, 5, 0, 9, 3, 7, 6, 1, 10, 4, 5, 0, 9, 8],
....:  [8, 7, 6, 1, 7, 5, 6, 1, 8, 10, 4, 6, 1, 3, 3, 7, 0, 9, 7],
....:  [7, 5, 6, 1, 3, 7, 6, 1, 7, 2, 5, 6, 1, 8, 10, 4, 0, 9, 3],
....:  [3, 7, 6, 1, 10, 4, 6, 1, 3, 8, 7, 6, 1, 7, 2, 5, 0, 9, 8],
....:  [10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 2, 6, 1, 3, 8, 7, 0, 9, 7],
....:  [4, 5, 6, 1, 8, 10, 4, 0, 9, 3, 8, 7, 0, 9, 7, 5, 0, 9, 3],
....:  [3, 7, 6, 1, 7, 2, 5, 0, 9, 8, 7, 5, 0, 9, 3, 7, 0, 9, 10],
....:  [10, 4, 6, 1, 3, 8, 7, 0, 9, 7, 5, 6, 1, 8, 10, 4, 0, 9, 3],
....:  [3, 3, 7, 0, 9, 7, 5, 0, 9, 3, 7, 6, 1, 7, 2, 5, 0, 9, 8],
....:  [8, 10, 4, 0, 9, 3, 7, 0, 9, 10, 4, 6, 1, 3, 8, 7, 0, 9, 7],
....:  [7, 5, 5, 0, 9, 10, 4, 0, 9, 3, 3, 7, 0, 9, 7, 5, 0, 9, 3],
....:  [3, 7, 6, 1, 10, 4, 5, 0, 9, 8, 10, 4, 0, 9, 3, 7, 0, 9, 10],
....:  [10, 4, 6, 1, 3, 3, 7, 0, 9, 7, 5, 5, 0, 9, 10, 4, 0, 9, 3],
....:  [2, 5, 6, 1, 8, 10, 4, 0, 9, 3, 7, 6, 1, 10, 4, 5, 0, 9, 8],
....:  [8, 7, 6, 1, 7, 5, 5, 0, 9, 10, 4, 6, 1, 3, 3, 7, 0, 9, 7],
....:  [7, 5, 6, 1, 3, 7, 6, 1, 10, 4, 5, 6, 1, 8, 10, 4, 0, 9, 3]]

The above patch have been chosen among 1000 other randomly generated as the closest to the asymptotic frequencies of the tiles in Jeandel-Rao tilings (or at least in the minimal subshift that I describe in the preprint):

sage: from collections import Counter
sage: c = Counter(flatten(data))
sage: tile_count = [c[i] for i in range(11)]

The asymptotic frequencies:

sage: phi = golden_ratio.n()
sage: Linv = [2*phi + 6, 2*phi + 6, 18*phi + 10, 2*phi + 6, 8*phi + 2,
....:      5*phi + 4, 2*phi + 6, 12/5*phi + 14/5, 8*phi + 2,
....:      2*phi + 6, 8*phi + 2]
sage: perfect_proportions = vector([1/a for a in Linv])

Comparison of the number of tiles of each type with the expected frequency:

sage: header_row = ['tile id', 'Asymptotic frequency', 'Expected nb of copies',
....:               'Nb copies in the 33x19 patch']
sage: columns = [range(11), perfect_proportions, vector(perfect_proportions)*33*19, tile_count]
sage: table(columns=columns, header_row=header_row)
  tile id   Asymptotic frequency   Expected nb of copies   Nb copies in the 33x19 patch
+---------+----------------------+-----------------------+------------------------------+
  0         0.108271182329550      67.8860313206280        67
  1         0.108271182329550      67.8860313206280        65
  2         0.0255593590340479     16.0257181143480        16
  3         0.108271182329550      67.8860313206280        71
  4         0.0669152706817991     41.9558747174880        42
  5         0.0827118232955023     51.8603132062800        51
  6         0.108271182329550      67.8860313206280        65
  7         0.149627093977301      93.8161879237680        95
  8         0.0669152706817991     41.9558747174880        44
  9         0.108271182329550      67.8860313206280        67
  10        0.0669152706817991     41.9558747174880        44

I brought the \(33\times19=641\) tiles at the conference and offered to the first 7 persons to find a \(7\times 7\) tiling the opportunity to keep the 49 tiles they used. 49 is a good number since the frequency of the lowest tile (with id 2) is about 2% which allows to have at least one copy of each tile in a subset of 49 tiles allowing a solution.

A natural question to ask is how many such \(7\times 7\) tilings does there exist? With ticket #25125 that was merged in Sage 8.3 this Spring, it is possible to enumerate and count solutions in parallel with Knuth dancing links algorithm. After the installation of the Sage Optional package slabbe (sage -pip install slabbe), one may compute that there are 152244 solutions.

sage: from slabbe import WangTileSet
sage: tiles = [(2,4,2,1), (2,2,2,0), (1,1,3,1), (1,2,3,2), (3,1,3,3),
....: (0,1,3,1), (0,0,0,1), (3,1,0,2), (0,2,1,2), (1,2,1,4), (3,3,1,2)]
sage: T0 = WangTileSet(tiles)
sage: T0_solver = T0.solver(7,7)
sage: %time T0_solver.number_of_solutions(ncpus=8)
CPU times: user 16 ms, sys: 82.3 ms, total: 98.3 ms
Wall time: 388 ms
152244

One may also get the list of all solutions and print one of them:

sage: %time L = T0_solver.all_solutions(); print(len(L))
152244
CPU times: user 6.46 s, sys: 344 ms, total: 6.8 s
Wall time: 6.82 s
sage: L[0]
A wang tiling of a 7 x 7 rectangle
sage: L[0].table()  # warning: the output is in Cartesian-like coordinates
[[1, 8, 10, 4, 5, 0, 9],
 [1, 7, 2, 5, 6, 1, 8],
 [1, 3, 8, 7, 6, 1, 7],
 [0, 9, 7, 5, 6, 1, 3],
 [0, 9, 3, 7, 6, 1, 8],
 [1, 8, 10, 4, 6, 1, 7],
 [1, 7, 2, 2, 6, 1, 3]]

This is the number of distinct sets of 49 tiles which admits a 7x7 solution:

sage: from collections import Counter
sage: def count_tiles(tiling):
....:     C = Counter(flatten(tiling.table()))
....:     return tuple(C.get(a,0) for a in range(11))
sage: Lfreq = map(count_tiles, L)
sage: Lfreq_count = Counter(Lfreq)
sage: len(Lfreq_count)
83258

Number of other solutions with the same set of 49 tiles:

sage: Counter(Lfreq_count.values())
Counter({1: 49076, 2: 19849, 3: 6313, 4: 3664, 6: 1410, 5: 1341, 7: 705, 8:
293, 9: 159, 14: 116, 10: 104, 12: 97, 18: 44, 11: 26, 15: 24, 13: 10, 17: 8,
22: 6, 32: 6, 16: 3, 28: 2, 19: 1, 21: 1})

How the number of \(k\times k\)-solutions grows for k from 0 to 9:

sage: [T0.solver(k,k).number_of_solutions() for k in range(10)]
[0, 11, 85, 444, 1723, 9172, 50638, 152244, 262019, 1641695]

Unfortunately, most of those \(k\times k\)-solutions are not extendable to a tiling of the whole plane. Indeed the number of \(k\times k\) patches in the language of the minimal aperiodic subshift that I am able to describe and which is a proper subset of Jeandel-Rao tilings seems, according to some heuristic, to be something like:

[1, 11, 49, 108, 184, 268, 367, 483]

I do not share my (ugly) code for this computation yet, as I will rather share clean code soon when times come. So among the 152244 about only 483 (0.32%) of them are prolongable into a uniformly recurrent tiling of the plane.

Read and Post Comments

Conférence sur les pavages

27 juin 2016 | Catégories: math | View Comments

Récemment, j'ai manqué quelques entraînements d'ultimate à Liège, car je participais à une conférence sur les pavages en France. "Les pavages?" me demande Maïté qui vient de commencer des travaux dans sa nouvelle maison. Et oui, les pavages! Mais pourquoi s'intéresser aux pavages?

Les pavages sont utiles en chimie et en physique, car ils permettent de modéliser mathématiquement le placement des atomes et molécules dans l'espace. Dans un cristal, les atomes sont placés de manière périodique comme la plupart des pavages utilisés dans les salles de bain de nos maisons.

Dans les années 80, Daniel Schechtman, un chercheur en chimie, a découvert des cristaux qui n'ont pas de structure périodique. Au début et pendant plusieurs années, ses collègues ne l'ont pas cru. Il a finalement obtenu le prix Nobel de Chimie en 2011 pour sa découverte.

Or on connaissait depuis les années 70 des pavages apériodique du plan. Les plus connus sont les pavages de Penrose qui ont plusieurs variantes. Avec la découverte des quasi-cristaux, les pavages apériodiques ont continué de susciter l'intérêt des chercheurs jusqu'à aujourd'hui...

Quelques liens:

Read and Post Comments

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