Carrés imparfaits
Un carré de dimensions 13×13 est à découper en carrés plus petits,
en utilisant le minimum de morceaux, toutes les dimensions étant entières.
Si les carrés sont tous différents, ce problème est connu sous le nom de pavage parfait.
Le plus petit carré qui accepte un pavage parfait est celui de 110×110
Si certains carrés peuvent être identiques, le pavage est dit imparfait.
Le problème est connu sous le nom de "Couverture de Mrs Perkins" (Mrs Perkins's Quilt),
du nom donné à ce problème par H.E. Dudeney dans son livre "Amusements in Mathematics",
bien qu'il semble l'avoir emprunté à Sam Loyd.
L'exemple ci-contre est un pavage minimal imparfait du 21×21.
Prenons le carré de côté 2n×2n. Une découpe évidente est en 4 carrés n×n.
De même le 9×9 pourrait se découper en 9 carrés de 3×3.
Pour garder l'intérêt du problème pour tout n, on impose que les côtés des carrés
soient premiers entre eux dans leur ensemble, c'est à dire le PGCD des côtés est 1.
(et le 21×21 n'est pas en 9 carrés de 7×7)
Avec cette contrainte, un carré de 4×4 se découpe en 7 morceaux minimum. Comment ?
Solution
Combien de morceaux au minimum pour le 9×9 ?
Solution
Déduire un pavage minimal du 13×13 à partir des pavages de carrés plus petits.
