Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 08-01-2013 22:45:10

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

au mpins la moitié !

Bonsoir à tous smile

Une véritable énigme que j'ai déjà proposée à plusieurs sites sans réponse .

On se donne un nombre fini de points dans un carré d'aire 2 , l'un d'entre eux étant le coin inférieur gauche du carré . Montrer qu'il est toujours possible de construire dans le carré des rectangles disjoints dont le coin inférieur gauche est l'un des points donnés et tel que la somme de leurs aires soit supérieure à 1 .

http://img189.imageshack.us/img189/2889/aumoinslamoiti.jpg

Un problème ouvert comme je les adore smile

Vasimolo



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 08-01-2013 23:19:09

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2705
Lieu: Luxembourg

au moins la loitié !

C'est du gâteau lol

 #3 - 09-01-2013 10:00:24

SHTF47
Imprnnçbl de Prs2Tt
Enigmes résolues : 39
Messages : 1629
Lieu: Autre nom du colin

au moind la moitié !

Raisonnement par l'absurde spotted.


La musique est une mathématique sonore, la mathématique une musique silencieuse. [Edouard HERRIOT]

 #4 - 09-01-2013 11:29:37

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Au moins la motié !

Bah plus qu'à nous montrer smile


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #5 - 09-01-2013 11:55:59

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

Au moins la moitéi !

Si on prend le cas le plus défavorable, tous les points sont sur la diagonale bas/gauche => haut/droit.
Tous les carrés remplissent la moitié de la figure (ex : la partie entre le coin en haut à gauche et la diagonale), est-ce que la surface occupée par les coins de chaque rectangle (ceux qui sont sous la diagonale) est supérieur au vide entre chaque rectangle déssiné ?

XXXXX
XXXXO
XXXOO
XXOOO
XOOOO

S'il y a 5 points, c'est evident, mais lorsque le nombre de points tend vers l'infini ?

 #6 - 09-01-2013 14:24:10

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

au moinq la moitié !

godisdead: Si on prend le cas le plus défavorable[...]

J'ai pensé aussi à ce cas là, mais je ne vois pas pourquoi c'est le plus défavorable hmm

 #7 - 09-01-2013 16:46:30

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

au loins la moitié !

Il semble que pour [latex]n[/latex] points la borne inférieure de l'aire que l'on peut recouvrir serait [latex]\frac{n+1}{n}[/latex] ce qui correspond bien à [latex]n[/latex] points régulièrement répartis sur la diagonale .

Il faut prendre ça avec un gros conditionnel car je n'ai aucune certitude et bien sûr aucune preuve smile

On peut tout à fait accepter que les rectangles aient des frontières communes , ça simplifie la vision des choses sans rien changer à la borne .

Vasimolo

 #8 - 09-01-2013 17:14:10

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Au moins la motié !

Oui j'ai également trouvé [latex]\frac{n+1}{n}[/latex] pour [latex]n[/latex] points régulièrement répartis sur la diagonale.

Reste à prouver que c'est le pire des cas...

 #9 - 09-01-2013 17:24:45

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

Au moiins la moitié !

Je n'ai pas les bases mathématiques pour le prouver, mais l'idée est que pour avoir le moins de surface pavé, il faut que chaque point se gène le plus possible.
Donc l'écart des coordonnées entre le point A(E;F) et le point B(R;S) doivent être minimum en X et en Y. (A et B étant deux points consécutifs)
Pour E=0 et F=0, on a R=S, et donc tous les points sont sur la diagonale.

 #10 - 09-01-2013 17:46:36

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

au moins la moitoé !

Il semble que le Latex du site ait de nouveau rendu l'âme , espérons que le problème ne nécessitera pas trop de calcul smile

Je ne pense pas que le problème nécessite de grosses connaissances mathématiques , il s'agît plutôt de trouver un bon angle d'attaque ( plus facile à dire qu'à faire ) .

Vasimolo

 #11 - 09-01-2013 18:10:27

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

au moins la miitié !

Tiens! Je pensais que c'était "Domi" qui proposait cette énigme, et j'allais justement lui suggérer de la présenter ici.
ça fait déja plusieurs jours que j'y réfléchis et je n'ai pas de solution, malgré l'évidence de la chose...

 #12 - 09-01-2013 18:15:31

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

A umoins la moitié !

Imod , Domi , Vasimolo , ... , c'est selon la forme du gâteau .

Certains gâteaux conviennent à tout le monde alors autant les partager smile

Vasimolo

 #13 - 09-01-2013 18:24:24

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Au moins a moitié !

J'ai bien remarqué que les problèmes que tu posais sur Math Forum étaient de même nature, mais c'est très curieux, je n'ai pas reconnu ta personnalité dans les 2 sites. Je te trouve ici moins émotif, un peu plus sur le recul, plus posé. Est ce à dire que nos personnalités évoluent en fonction du public ?
J'en suis encore tout retourné, de cette révélation...

 #14 - 09-01-2013 18:27:38

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Au omins la moitié !

Chat échaudé ...

Vasimolo

 #15 - 09-01-2013 18:39:02

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

ay moins la moitié !

Je suis surtout plutôt surpris de cette cachotterie pas bien utile.
Mais bon, c'est pas bien grave. Je ne comprends pas, c'est tout.

 #16 - 09-01-2013 18:48:49

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

au moins la mootié !

Ce ne sont pas des cachotteries quand je m'inscris sur un site je propose mon pseudo usuel et quand il est refusé j'en propose un deuxième , etc , ...

Je n'ai jamais caché ma participation à plusieurs sites , j'ai même fourni plusieurs liens de sujets que j'avais proposé en parallèle sur d'autres sites sous d'autres pseudos .

J'étais persuadé que tu m'avais reconnu mais comme tu dis ce n'est pas très grave .

Vasimolo

 #17 - 10-01-2013 17:32:46

Jackv
Elite de Prise2Tete
Enigmes résolues : 34
Messages : 1998
Lieu: 94110

Au moins lla moitié !

Toute cette dernière discussion ne fait pas beaucoup avancer le schmilblick sad ...
Revenons à notre problème smile .

Supposons un certain nombre de points régulièrement répartis sur la diagonale issue du coin bas-gauche comme l'a proposé godisdead.
Pour un petit nombre de points, nous sommes tous d'accord que la formule est bien vérifiée.
            http://www.prise2tete.fr/upload/Jackv-Moitie.gif
L'aire évolue alors comme 1+ 2/n² et reste bien toujours supérieure à 1.

Lorsque le nombre de points tend vers l'infini, la formule reste vrai à condition que la distance entre 2 bandes soit toujours infiniment plus petite que la largeur d'une bande.
Ce qui devient douteux à la limite, lorsque la largeur d'une bande tend vers zéro ! Sauf si on accepte, comme le propose Vasimolo que les rectangles aient des frontières communes.

Il reste à démontrer que ce cas de figure est un minimum.

Considérons un point quelconque A. Soient a la largeur des bandes et b la longueur du rectangle issu de ce point.
Supposons que l'on impose un petit déplacement de A en A' à ce point.
Le cas le plus défavorable a lieu lorsque le déplacement s'effectue selon la diagonale, vers le bas  :
            http://www.prise2tete.fr/upload/Jackv-Moitie1.gif
La largeur de l'une des bandes adjacente va devenir a - da, tandis que l'autre va devenir a + da.
L'aire des 2 bandes entourant le point A qui était de 2a.b + a²   devient  : 
(b+da)*(a+da) + (a+b)*(a-da)   soit :  2a.b + a² + da²

Le cas le plus favorable a lieu lorsque le déplacement s'effectue de A en A' selon la normale à la diagonale :
            http://www.prise2tete.fr/upload/Jackv-Moitie2.gif
La largeur des 2 bandes adjacentes va devenir a + da.
Cette aire passe alors à   :  2a.b + a² + 2b.da

Si le déplacement s'effectue dans une direction intermédiaire, le résultat sera intermédiaire.
Nous avons donc bien un minimum pour le cas où les points sont régulièrement répartis sur la diagonale smile .
Il reste simplement à prouver qu'il n'existe pas d'autres minimaux ailleurs lol .

EDIT : La 2ème figure a été remplacée. Ceux qui l'avait déjà chargée sont invité à faire un F5.

 #18 - 10-01-2013 18:06:54

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Au moins la moité !

Beaux dessins, mais pas très convaincants pour l'instant.
En mettant les points au hasard, on a des configurations bien plus compliquées.

 #19 - 10-01-2013 19:41:53

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

au loins la moitié !

Je peux me tromper mais il me semble qu'on peut évacuer les problèmes de limite , on est complètement dans le discret , c'est presque un problème d'échiquier . On peut supposer sans peine que tous les points sont aux nœuds d'un quadrillage orthonormé . On peut aussi évacuer les problèmes de contact entre les petits rectangles , si on arrive à faire plus que 1 avec contact on fera plus que 1 sans contact . Bref on a un échiquier avec des coins inférieurs-gauches imposés et il faut faire un pavage rectangulaire qui recouvre au moins la moitié de l'échiquier .

C'est plus facile à visualiser mais apparemment pas plus simple à résoudre mad

Content de voir que le problème vous plait smile

Vasimolo

 #20 - 10-01-2013 19:52:09

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1374
Lieu: Coutiches

au moins la moitoé !

C'est amusant, mais je me suis fait les même réflexions que vous tous, avec les même erreurs au départ.

La représentation sous le bon angle reste cependant compliqué à trouver... s'il existe !

 #21 - 10-01-2013 20:02:55

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

Au moins la moiti é!

On peut aussi évacuer les problèmes de contact entre les petits rectangles , si on arrive à faire plus que 1 avec contact on fera plus que 1 sans contact .

Non, je ne suis pas d'accord. Comme vu plus haut par Jackv.
Lorsque le nombre de points tend vers l'infini, la formule reste vrai à condition que la distance entre 2 bandes soit toujours infiniment plus petite que la largeur d'une bande.
Ce qui devient douteux à la limite, lorsque la largeur d'une bande tend vers zéro ! Sauf si on accepte, comme le propose Vasimolo que les rectangles aient des frontières communes.

Prenons un exemple physique :
Sur un carré de 10 cm de coté, tu mets des points sur la diagonale espacée de 1 mm (voir 0.5 mm), et tu essayes sans que les rectangles se touchent de remplir plus de la moitié de ton carré !

 #22 - 10-01-2013 20:07:51

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

zu moins la moitié !

Un autre angle d'attaque pourrait être, soit un carré 100 * 100.
10 000 points, je peux remplir tout le carré. Pour chaque point que je supprime, quelle surface je laisse vide ?
Est-ce qu'en enlevant un grand nombre de point, j'arriverais à laisser 5000 carrés vides ?

Est-ce que le cas d'un carré 2*2 ou 3*3 permet de généraliser à N*N ?

Je creuserais ça dès que ma fille sera au lit !

 #23 - 10-01-2013 20:30:41

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

au moins la mpitié !

godisdead a écrit:

On peut aussi évacuer les problèmes de contact entre les petits rectangles , si on arrive à faire plus que 1 avec contact on fera plus que 1 sans contact .

Non, je ne suis pas d'accord. Comme vu plus haut par Jackv.Lorsque le nombre de points tend vers l'infini, la formule reste vrai à condition que la distance entre 2 bandes soit toujours infiniment plus petite que la largeur d'une bande.Ce qui devient douteux à la limite, lorsque la largeur d'une bande tend vers zéro !

Pas d'accord avec le désaccord smile .

Les deux limites n'évoluent pas en même temps , on fixe un nombre de points très grand si on veut , mais une fois donné il ne bouge plus puis on affine l'espace entre les rectangles donc contact ou pas contact , le problème est le même .

Vasimolo

 #24 - 10-01-2013 20:57:55

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

Au moins la moiti é!

Pas d'accord avec le pas d'accord avec le désaccord smile

A partir de ma théorie (les points sur la diagonale), le problème se resume à déterminer si l'aire du triangle sous la diagonale de chaque rectangle est plus grande ou plus petite que le vide entre ce rectangle et le suivant.
La tolérance de vide entre deux rectangles est une constante. Une fois que cette constante est déterminé, tu pourras determiner à partir de combien de points tu n'arriveras plus à remplir la moitié de ton carré !

 #25 - 10-01-2013 21:39:40

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Au moins la omitié !

A dire vrai je n'ai pas regardé ta théorie en détail , le nombre de point étant fixé , si on peut faire plus que 1 en acceptant les contacts , on peut faire plus que 1 en les approchant , c'est une évidence topologique smile

Vasimolo

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 30 moutons, ils meurent tous sauf 15, combien en reste-t-il ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete