Inscription / Connexion Nouveau Sujet
Recouvrir un carré avec des carrés
Bonjour,
C'est un prolongement de ce sujet : 
Recherche enigme
Il s'agit de recouvrir un carré avec un certain nombres de carrés qui peuvent être de toutes tailles.
Des exemples :
Et ci-dessous les messages qui se rapportent au prolongement.
Je reviens au cas 2021.
Dans les solutions proposées, on a 4 carrés relativement grands, et 2017 carrés tout petits.
L'idée de cette nouvelle variante, c'est de trouver un découpage en 2021 carrés, mais avec le ratio CotéMaxi / CotéMini le plus proche possible de 1.
Je n'ai pas la solution ... c'est juste un challenge pour personnes intéressées.
On peut peut-être déjà le faire pour 15 carrés, pour que ce soit moins fastidieux
ce serait bien à mettre dans le forum énigmes, vu que ici on ne peut pas blanquer
je ne comprends pas pourquoi tu n'es pas satisfait avec ta première idée de répartition en deux tailles (44² etc)
m² carres + (2p+1)
avec 2021 :
le plus grand carré <2021 est encore 44
donc 2021 = 44² + 2*42+1
et le rapport des tailles max /min = 44/42 = 22/21
Oui, 2021 est très proche de 45²=2025, donc les carrés mis en complément sur la bordure se retrouvent avec des tailles proches des carrés mis au début.
Mais qui sait... il y a peut être mieux ? En tout cas, si ici on est tombé sur un résultat 'équilibré' dès le premier essai, c'est par un coup de chance, c'est parce que 2021 était proche d'un carré parfait. L'idée est donc de bâtir une recherche plus systématique.
Mais je ne sais pas du tout où ça va nous mener !
proche ou pas on peut toujours faire pareil
ici on utilise n = m² + (2k+1)
(un carré de m*m carrés et une bordure de k carrés sur deux côtés, plus le coin)
2021 = 44² + (2*42+1) rapport 44/42
2019 = 44²+(2*41+1) rapport 44/41
au pire (à mi distance de 45² et de 44²), par exemple
1981 = 44² + (2*22+1) rapport 44/22 = 2
on ne dépassera jamais beaucoup de ce rapport max/min = 2
"une recherche plus systématique"
AMHA voué à l'échec dès que n est un tant soit peu grand
l'agencement de n carrés est un problème NP qui croit exponentiellement avec le nombre de carrés
un peu équivalent à étudier un par un tous les réseaux possibles de n arcs.
nota :
2021 peut donc aussi se réaliser avec une bordure tout autour :
un grand carré de 43² petits, bordé sur les 4 cotés par 42 carrés un peu plus grand (43/42) et les 4 coins :
2021 = 43² + 4*42 + 4
ce n'est pas le cas de 2019 car il n'existe pas de
(on va s'écarter de plus en plus d'un problème de collège !)
On peut peut-être déjà le faire pour 15 carrés,
15 = 3²+ 2 x 3
donne max/min = 2
pour les petites valeurs de n on a les pavages avec le plus petit rapport max/ min suivants :
conjecture :
il est toujours possible de faire un pavage en n > 5 carrés avec max/min < 3
Je pense que la conjecture est exacte.
Soit q = max/min.
J'utilise cette remarque de mathafou dans l'autre sujet :
on peut au moins construire une solution à n' > n carrés en redécoupant en 4 un des carrés (n' = n+3),
max devient max ou max/2.
min reste inchangé.
q devient q' = q/2 ou q.
Donc q'
q.
M = max, m = min et q = M/m.
En redécoupant en 4 le plus grand carré, ou l'un d'eux s'il y en a plusieurs :
M devient M' avec M' M.
m devient m' avec m' = min(m, M/2) où min désigne le plus petit des deux.
Si m M/2, on a m' = m et q' q.
Si m > M/2, on a m'= M/2 et M'/m' M/(M/2) ; donc q' 2.
Un exemple avec n = 9 et 9+3 = 12 :
On peut trouver un recouvrement de 12 carrés avec q = M/m = 2.
En partant du recouvrement avec 9 carrés identiques et en partageant l'un d'eux en 4 carrés identiques.
cela tendrait même à prouver que max/min 2
au moins pour n "suffisamment grand"
d'ailleurs mon cas n= 12, max/min = 3 est une erreur
n = 12 se découpe au mieux en
le seul cas identifié avec max/min = 3 > 2 est pour n = 8
9 carrés avec q 
Annuler
connectez vous