partition avec des carrés

jaybe

Bonjour à tous,

un nouveau problème, cette fois pour la fin des vacances :

1) Montrer que l'on peut faire une partition d'un carré avec $n$ carrés si et seulement si $n$ est différent de 2, 3 ou 5.

2) On appelle pseudo-carré un rectangle de dimensions $L$ et $l$ s'il existe un entier $n$ tel que l'on puisse définir une partition du rectangle avec $k$ carrés si et seulement si $k=n$, $k=n+3$ ou $k \geq n+5$.

a) Vérifier que pour tout entier $L \geq 2$, le rectangle de dimensions $L$ et 1 est un pseudo-carré.

b) Vérifier que le rectangle de dimensions 4 et 3 n'est pas un pseudo-carré.

c) Existe-t-il une caractérisation (simple ?) des pseudo-carrés ?

PS : je ne connais pas la réponse à la question 2)c)... (normalement tout le reste est facile).

bisam

Tu dis que tout le reste est facile, mais je serais curieux de savoir comment tu montres "simplement" qu'on ne peut pas partitionner un carré en 5 carrés...

jaybe

Par exemple, on utilise le fait que chaque bord du carré initial doit toucher au moins deux carrés de la partition.

Edit : mieux, on place déjà un carré dans chaque coin et on essaie de placer un cinquième.

pdepasse

Bonjour,

Déjà j'aimerais savoir si il est vrai qu'un rectangle dont le rapport des dimensions est irrationnel ne peut être partitionné en carrés; Je crois l'avoir lu un jour...Je n'arrive pas à le montrer. Si quelqu'un sait si c'est vrai, qu'il veuille bien me dire si la preuve est simple et qu'alors il ne me la donne pas (tout de suite). Merci!

Lorsque le rapport est rationnel, on peut se ramener au cas où longueur et largeur sont des entiers étrangers, $l$ et $L$.
Alors il est quadrillable en $lL$ carrés . Soit $M(l,L)\leq lL$ le nombre minimum de carrés pouvant paver le rectangle.
Alors c'est un non-pseudo-carré ssi on peut le paver avec $M(l,L)+1, 2 ou 4$ carrés.

Je sais que ce n'est pas la réponse au problème! Je voudrais juste savoir si j'ai bien capté l'énoncé.

Cordialement

jaybe

Ton énoncé me fait penser à un autre problème assez connu : si on assemble des rectangles dont au moins l'une des longueurs est entière en un rectangle $R$, alors au moins l'une des longueurs du rectangle $R$ est entière. Je ne connais qu'une seule preuve de ce résultat avec une astuce particulièrement profonde (pour moi !) qui semble pouvoir être également utilisée pour prouver ton assertion.

(Edit : après un peu de recherche je crois que tu peux laisser tomber la preuve simple : selon l'article "TILING A SQUARE WITH SIMILAR RECTANGLES" de Freiling et Rinne, Max Dehn a prouvé ce résultat en 1903 et la preuve est beaucoup plus difficile que prévue.)

Il existe forcément un rang $N$ tel que l'on puisse toujours paver un rectangle à longueurs rationnelles avec exactement $n$ carré pour tout $n \geq N$. Pour un carré ce rang est 6 et les autres valeurs possibles de $n$ sont $4=6-2$ et $1=6-5$. Pour un pseudo-carré, ce doit être exactement toute valeur entière à partir de $N$ avec pour seules exceptions $N-2$ et $N-5$.

Edit : OK, j'avais mal compris, effectivement on peut aussi formuler le problème ainsi !

pdepasse

Soit $A_i, i\in\{1,2,4\}$ l'ensemble des rectangles $(l,L)$ pavables par $M(l,L)+i$ carrés.

La réunion des trois $A_i$ est l'ensemble des non-pseudo-carrés.
Par ailleurs $A_1$ contient $A_4$

Y a plus qu'à!...

résoudre notre problème de façon simple!

jaybe

Certes ! Au passage, on peut remarquer qu'il y a plusieurs classes de non pseudo-carrés, par exemple (4,3) et (6,5).

pdepasse

OK

$A_2$ contient $(3,4)$ et $A_1$ $(5,6)$.

Tu en connais un dans $A_4$?

jaybe

C'est un peu plus subtil... il y a 6 classes au plus car un non pseudo-rectangle peut être dans $A_2$ ou non ; il peut être dans $A_1$, dans $A_4$ et non $A_1$ ou dans aucun des deux et ces possibilités sont a priori indépendantes.

JLT

Peut-être pour avoir une idée de ce qui se passe il faudrait déjà déterminer parmi tous les rectangles $(m,n)$ avec $m,n\leqslant 10$ premiers entre eux lesquels sont des pseudocarrés et lesquels n'en sont pas.

On a déjà vu par exemple que les rectangles $(1,n)$ sont des pseudocarrés. Il me semble que les rectangles $(2,n)$ également.

JLT

Une autre question que l'on peut se poser (je n'ai pas réfléchi). Est-il vrai que si $m$ et $n$ sont des entiers et $m<n$ alors $M(m,n)=q+M(m,r)$ où $n=mq+r$ est la division Euclidienne de $n$ par $m$ ?

jaybe

D'accord JLT, cela me semble vrai.

Sous réserve de confirmation : toutes les classes existent (6) et :

Les $(3,3k+1)$ sont $A_2$ ; les $(3,3k+2)$ sont pseudo-carrés.

Les $(4,4k+1)$ sont $A_1$ ; les $(4,4k+3)$ sont $A_2$.

$(5,6)$ est $A_1$ et $A_2$ ; $(5,7)$ est $A_2$ et $A_4$ ; $(5,8)$ est $A_4$, $(5,9)$ est $A_1$.

$(6,7)$ est $A_2$ et $A_4$ ; $(6,11)$ est $A_1$ et $A_2$.

A compléter au fur et à mesure...

jaybe

Et pour répondre à ta question par la négative, $M(5,6)=5$ tandis que $M(1,5)=5$ ; une autre façon de comprendre cette question (je pense) : ce n'est pas l'algorithme d'Euclide qui fournit la partition utilisant le moins de carrés !

JLT

Tu es sûr que $(3,7)$ est pseudocarré ?

Edit : jaybe a corrigé son message.

jaybe

Bien vu, je corrige ! J'ai bien fait de préciser qu'il fallait vérifier...

pdepasse

je me suis inversé le 1 et le 4: si on est dans $A_1$ on est dans $A_4$, donc c'est $A_4$ qui contient $A_1$ et non l'inverse!

Avec ou sans mon inversion, il n'y a plus que six classes parmi les sept a priori envisageables puisque l'un des $A_i$ est dans un autre.

Edit: Oups, j'arrive en retard!

jaybe

C'est assez surprenant, il y a déjà eu pas mal de recherches concernant une estimation asymptotique de la constante $M(l,L)$ mais apparemment personne (du moins d'après ce que j'ai pu lire pour l'instant) ne s'est intéressé à ces classes ni même n'a mentionné ces possibilités.

jaybe

Je n'ai pas trouvé de nouveau pseudo-carré qui n'ait déjà été mentionné. Y 'en a-t-il ? Avis aux amateurs...

pdepasse

(Si j'ai bien compris!), ta conjecture, jaybe, est que seuls les $(1,n), (2,2n+1), (3,3n+2)$ sont des pseudo-carrés parmi les $(l,L)=1$
Une reformulation (triviale!):

Tout $(l,L)=1$ est non-pseudo-carré si $l\geq 4$.

Trois démonstrations suffisantes ($i\in\{0,1,2\}$):
Si $(l,L)=1$ (et $l\geq 4$) admet un pavage par deux rectangles dont $i$ pseudo-carré(s), alors c'est un non-pseudo-carré.

Y a plus qu'à

jaybe

Je ne comprends pas ta démonstration pdepasse : tout rectangle peut être pavé par deux rectangles dont 0, 1 ou 2 est (sont) pseudo-carré(s) !

pdepasse

Je n'ai rien démontré!

Je dis seulement (et c'est trivial (sauf si c'est faux!)) que pour prouver ta conjecture il suffit de faire les trois démonstrations que je dis.

Bien sûr, je n'ai fait aucune des trois, sinon je l'aurais dit.

Je ne fais que proposer l'idée qu'on peut penser à "découper" ta conjecture en trois cas qui, comme tu le remarques, représentent l'ensemble des cas possibles.

jaybe

Ok, j'ai compris... cela ne me semble pas être une bonne approche car on ne voit pas à quel moment l'hypothèse $l \geq 4$ intervient.

JLT

De toute façon, je ne vois pas comment on peut réussir à montrer quoi que ce soit si on n'a pas d'informations sur $M(l,L)$.

D'ailleurs, une question annexe : est-il vrai que si $l$ et $L$ sont des entiers, alors il existe une partition du rectangle $l\times L$ en $M(l,L)$ carrés de côtés entiers ?

jaybe

C'est une excellente question JLT ! Je n'ai pas la réponse définitive mais je serai tenté de dire que c'est non, pour la raison suivante : il est possible de paver le rectangle de dimensions 98 et 86 avec 11 carrés (tous différents) dont un carré unité. Donc il reste à savoir si l'on peut paver le rectangle de dimensions 49 et 43 avec 11 carrés entiers ou moins ; si c'est impossible on a un contre-exemple (un lien pour le dessin : http://www.squaring.net/sq/sr/spsr/o11/order11_spsr.html).

pdepasse

Merci d'appuyer très précisément en deux endroits qui font très mal! Va falloir que je me soigne.

Je soupçonnais ma première maladie (rêver naïvement d'une forme de récurrence sur les $M(l,L)$ qui fournirait, sans qu'il soit nécessaire de la résoudre entièrement,. des renseignements suffisants pour notre affaire,
mais je n'avais même pas songé à la seconde: implicitement, je répondais "oui" à ta question, ce qui est, de fait, pour l'instant, totalement gratuit!

jaybe

Du nouveau : mon contre-exemple n'est pas bon (on peut faire 10 : un carré de taille 34, puis 2 de taille 15 et 4 de taille 9, on finit avec 1 de taille 13 et 2 de taille 2) et j'ai mis le doigt sur une conjecture : pour $n$ et $m$ entiers, le nombre minimal pour paver avec des carrés entiers le rectangle ($n$,$m$) est le même que pour le rectangle ($2n,2m$). D'après le site http://demonstrations.wolfram.com/MinimallySquaredRectangles/, c'était initialement pensé comme faux, puis on a commencé à penser que cela pourrait être vrai lorsqu'aucun contre-exemple ne s'est manifesté pour $1 \leq n \leq m < 150$...