Carrés imparfaits

Il s'agit de découper un carré de n×n en carrés plus petits, de côtés premiers entre eux dans leur ensemble.
Et bien entendu de trouver le plus petit nombre de morceaux !
Nous appellerons s(n) ce nombre minimal de morceaux

Le carré de 2×2 est trivial, de même celui de 3×3, et s(2) = 4, s(3) = 6
Celui de 4×4 met déja en oeuvre la contrainte "premiers entre eux", car sinon on aurait le découpage trivial en 4 carrés de 2×2
Il suffit de découper un des carrés de 2×2 en 4 carrés de 1×1 pour obtenir un découpage primitif (premiers entre eux) et s(4) = 7.
Il reste à prouver que ce découpage est optimal.
Ici ce n'est pas trop dur car la seule autre posibilité à envisager est l'utilisation d'un carré de 3×3,
le reste ne pouvant se paver qu'avec des 1×1, soit 8 carrés en tout au lieu de 7.

Faisons tout de suite une remarque : ce n'est pas le seul pavage optimal.
En effet on peut réarranger ici les mêmes carrés autrement.
De façon générale, les carrés formant un rectangle peuvent se réarranger dans ce rectangle, ne serait-ce que par les symétries du rectangle.

Passons au carré de 5×5
Si on considère un de ses côtés, on aura 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1
Soit à priori p(5) - 1 = 6 points de départ possibles pour le pavage (5+0 étant éliminé).
Il n'est ici pas trop difficile de les examiner tous et de trouver le pavage optimal.
D'autant plus que seuls les pavages avec des plus gros morceaux possibles sont à envisager sérieusement. Inutile donc de partir avec les 2+1+1+1 et 1+1+1+1+1, car même si ces partitions étaient nécessaires, elles seraient sur un autre côté du carré de départ !
Comme on a toujours intérêt à avoir les plus gros morceaux possible, pour en avoir le moins possible, il est intéressant que la plus petite dimension de la surface restante soit la plus grande possible.
En considérant cette surface comme la superposition de deux rectangles, il faut maximiser la plus petite largeur de ces rectangles.
On voit aussi que 3+1+1 est inutile, par échange des carrés de 1×1 avec ce qui est au dessous, on est ramené au 3+2.

Seule est donc à envisager sérieusement pour l'instant le 5 = 3+2.
On peut mettre par symétrie immédiatement un deuxième carré 2×2, et il reste une surface que l'on peut considérer comme un carré de 3×3 auquel on a oté un coin de 1×1.

Mais les pavages du 3×3 ont justement un carré de 1×1 dans un coin !
On obtient alors un pavage du 5×5 en 3 + s(3) - 1 = 8 morceaux

En réarrangeant les morceaux dans les rectangles, on obtient 6 variantes, dont deux sont identiques par symétrie.
Ces variantes montrent, sans qu'il soit besoin de les essayer, que l'examen des autres partitions de 5 est inutile, car on les a sur les autres côtés de ces variantes (2+2+1, 2+1+1+1, 3+1+1).

Restent le 4+1 conduisant "visiblement" à 10 morceaux, et le 1+1+1+1+1 laissant un rectangle de 4×5 à paver.
Les pavages envisageables pour ce rectangle donnent 5 morceaux au mieux (un 4×4 et quatre 1×1), soit là encore 10 morceaux en tout.

Le pavage obtenu est donc bien optimal et s(5) = 8.

On peut ainsi poursuivre de proche en proche avec cette méthode pour trouver les pavages minimaux.
L'inconvénient est que pour n "suffisemment grand", le nombre de partitions p(n) augmente rapidement :
ainsi p(13) = 101, soit 100 possibilités de points de départ à examiner ! Sans compter les permutations de carrés...
Certes la plus "prometteuse" est comme pour le 5×5, celle en deux carrés "presque égaux", soit ici 13 = 7+6.
Mais à moins de prouver que toutes les autres sont soit pire, soit obtenues "sur les autres côtés" par réarrangement des pièces, il faut aussi les essayer !

Essayons donc de partir de 13 = 7+6.
Il reste un carré de 7×7 moins un coin, et on est donc amené à étudier d'abord le pavage optimal du 7×7.

La même méthode donne 7 = 4+3, et à partir du pavage du 4×4 moins un coin, on obtient s(7) ≤ 9
Car il faudrait encore prouver que ce pavage est optimal, même si c'est un bon candidat.

On peut réorganiser ce pavage pour avoir un 1×1 dans un coin, et donc un pavage du 13×13.
On a donc s(13) ≤ 3 + s(7) - 1 ≤ 11.

La même méthode peut être employée pour le 9×9, à partir de 9 = 5+4 et d'un pavage optimal du 5×5 moins un coin de 1×1.

Il a été démontré (Conway 2003) que les valeurs de s(n) jusqu'à n = 15 sont :

n	2	3	4	5	6	7	8	9	10	11	12	13	14	15
s(n)	4	6	7	8	9	9	10	10	11	11	11	11	12	12

Une liste plus complète est sur OEIS A005670

On a de bons candidats pour n>15, et même pour des valeurs élevées de n, mais pas de preuves.
Quand n devient assez grand (même déjà le 13×13 n'est pas prouvé ci-dessus être optimal), la méthode exposée ici devient impraticable.
On utilise alors une analogie et le graphe équivallent.
Voir le problème Morceaux étudiant des pavages parfaits (en morceaux tous différents) pour des explications sur ces graphes.
Le problème est alors pris à l'envers, c'est à dire à partir d'un s(n) et des graphes avec s(n) arcs, en déduire ceux qui correspondent à des pavages carrés.
Mais là aussi, le nombre de graphes possibles avec s(n) arcs augmente très vite ...