Enigme Optimisation de carrés @ Prise2Tete

Promath- · #1

Bonjour

Une énigme que je ne pourrai pas suivre hélas, je rentre lundi

Sur une grille carrée de (n+1)(n+1) points, on veut placer exactement n carrés non ponctuels tels que tous les sommets de ces carrés soient des points de la grille, et que les carrés ne se touchent ni par un sommet ni par une arête, bref qu'ils ne se touchent jamais.
Mais ils peuvent toucher le bord de la grille.
On note A_n l'aire maximale de l'ensemble des carrés disposés. Bien sûr A<n² pour n>1
Pour n=2 on se rend compte qu'on ne peut pas satisfaire les conditions
Pour n=3, on trouve A=3 donc A/n²=1/3
Pour n=4, la configuration suivante montre A>=8 donc A/n²>=1/2

Calculer la limite quand n tend vers l'infini de (A_n)/n²

Bonne chance!

Vasimolo · #2

On sent bien que la réponse est 1 mais pourquoi ? Je vais y réfléchir ( j'adore ces petits problèmes )

Vasimolo

gwen27 · #3

On peut facilement placer un carré (n-2)x(n-2) dans un coin et des carrés unitaires autour donc la limite est 1.

Promath- · #4

Vasimolo: bon courage!

Gwen: Bien!

portugal · #5

Ça semble trop simple : j’ai dû rater quelque chose.

On place une succession de carrés 1*1 en haut alignés. Comme il y a n+1 points par ligne, on peut placer n/2 carrés en ligne en tenant compte de l’espacement.

On laisse un interligne vide et on recommence mais on décide de n’en mettre que n/2-1.

Reste un carré à placer dont on place le sommet "haut-gauche" en ligne 5 à gauche. L’espace en bas/droite du sommet est vide. On peut donc placer dans cet espace un carré n-4*n-4

On a donc An > (n-4)^2/ n^2= (1-4/n)^2 qui tend vers 1 pour n tendant vers l'infini.

La limite est donc 1

nodgim · #6

Salut Promath,
Il suffit de placer un gros carré de coté n-2 dans un coin et de placer les n-1 autres carrés de coté 1 sur les 2 cotés libres. On néglige l'aire occupée par les petits carrés. Le rapport aire occupée/aire totale est de (n-2)²/n²=1-4/n+4/n² qui tend vers 1 quand n tend vers 00.

Promath- · #7

Nodgim, Portugal :oui

halloduda · #8

1
Considérons N² carrés (1-epsilon)*(1-epsilon) disjoints dans un carré NxN.
Ils représentent une surface N²*(1-2epsilon+epsilon²).
A l'échelle près, epsilon=1/2k, en zoomant d'un facteur 2k, toutes les valeurs sont entières comme dans l'énoncé.

Vasimolo · #9

En fait c'est assez simple , il suffit de caser un gros carré dans l'angle et de saupoudrer les deux côtés restants avec des petits carrés de côté 1 :

Vasimolo

enigmatus · #10

Bonjour,
Ce n'est sans doute pas optimisé, mais on peut toujours placer un carré de côté [latex]n-2[/latex] dans le coin en bas à gauche, et [latex]n-1[/latex] carrés unitaires sur la bande de largeur [latex]1[/latex] en haut et à droite (on pourrait même en placer [latex]n[/latex] si [latex]n[/latex] est impair).
[TeX]1\geq A\geq(n-2)^{2}+(n-1)=n^2-3n+3[/TeX]
Donc [latex]\lim\limits_{n \to \infty} \frac{A}{n^2}= 1[/latex]

Promath- · #11

Bien!

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 31-10-2015 17:58:01

Optimisation ed carrés

#0 Pub

#2 - 31-10-2015 18:45:03

Opimisation de carrés

#3 - 31-10-2015 19:01:25

optumisation de carrés

#4 - 31-10-2015 19:08:39

Optimisation de carré

#5 - 31-10-2015 23:55:45

Optimiisation de carrés

#6 - 01-11-2015 08:04:14

optimisatoon de carrés

#7 - 01-11-2015 08:49:38

Optimisation de carréss

#8 - 01-11-2015 09:31:48

optimisation de xarrés

#9 - 01-11-2015 10:57:09

Optimisation de crrés

#10 - 01-11-2015 11:51:13

oprimisation de carrés

#11 - 28-11-2015 17:05:44

optimisatoon de carrés

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums