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
[+]

 #51 - 16-01-2013 03:00:00

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

ai moins la moitié !

godisdead, d'une part je ne suis pas d'accord pour dire qu'un point ayant une coordonnée commune avec un autre ne peut qu'augmenter la surface que l'on peut couvrir :

Par exemple, sur un carré 8x8 : Avec les points (1,2) et (6,2), on peut couvrir 58 cases, mais si l'on rajoute (6,1), on n'en couvre plus que 56.

D'autre part, cela n'implique en rien que les points doivent se trouver sur la diagonale pour une surface minimale.

#0 Pub

 #52 - 16-01-2013 10:23:05

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

au moins la miitié !

Oui, j'aurais du préciser, ajouter un point avec une coordonnée commune et l'autre supérieur.
Dans ton exemple, c'est le (6;2) qui devient superflu.

Je suis d'accord que mon raccourci manque une démonstration (pour dire que tous les points doivent être sur la diagonale)
En fait, si tous les points ont des coordonnées X et Y différentes, donc dans un carré 10*10, il n'y aura que 10 points.
donc chaque point peut paver une surface horizontale ou verticale de 55 cases. (1+2+3+4+5+6+7+8+9+10)
Tout placement autre que sur la diagonale permettra de paver autant ou plus.

 #53 - 16-01-2013 11:43:25

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

Au moins la moiité !

Si l'on part d'un carré 8x8 avec les points (1;2), (2;4), (6;1) et (7;2), on peut couvrir 54 cases. Si l'on rajoute (6;3), on ne peut plus en couvrir que 53.

 #54 - 16-01-2013 12:12:08

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

Au moins la motié !

Bien vu !

 #55 - 16-01-2013 14:32:12

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,466E+3

Au moins al moitié !

J'ai tenté pas mal d'idées sur ce problème mais aucune n'aboutit.

La seule encore prometteuse de manière simple serait de se dire que l'ensemble des points SUR ou A GAUCHE de la diagonale permet potentiellement de voir plus de la moitié de la zone. (En regardant à droite)

Idem pour les point A DROITE (en regardant vers le haut )

Si on superpose les deux visions, on voit potentiellement plus que le carré complet.

 #56 - 16-01-2013 18:42:55

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

Au moins la moitié !!

J'ai plein de nouvelles idées , je vous tiens au courant smile

Vasimolo

 #57 - 25-01-2013 15:43:54

AlexF
Amateur de Prise2Tete
Enigmes résolues : 32
Messages : 2

Au moins la moiti !

Bon bah moi je vais opter pour un petit raisonnement par recurrence, bon mon hypothèse [latex]\mathcal{H}(n)[/latex] Il existe une construction de n rectangles tel que la somme de leurs aire fasse 1.
Je crois que tout le monde est convaincu de [latex]\mathcal{H}(1)[/latex] ou le rectangle en question est en fait le carré tout entier.
Bon on suppose [latex]\mathcal{H}(n)[/latex], je rajoute cette fois un [latex]n+1[/latex]ème point.
Deux possibilités, soit il est inclus dans un rectangle déjà existant soit pas.
S'il n'est pas inclus c'est trivial (on en a un nombre fini donc il lui reste une place fini à notre nouveau petit rectangle).
S'il est inclus, on se place dans le référentiel tu nouveau rectangle de dimensions [latex]X,Y[/latex].
si on appelle [latex]x,y[/latex] les coordonnées relatives du point, on voit bien qu'on a 2 choix possibles de configuration pour le rectangle en bas à gauche et une possible pour l'autre. On prend [latex]\max(Xy,xY)[/latex] (plus grosse aire)
De cette façon l'aire totale est [latex](X-x)(Y-y)+\max(Xy,xY)=XY-\min((X-x)y,x(Y-y))[/latex].
ce qui vaut dans le pire des cas (pour [latex]x=\frac{X}{2}[/latex] et [latex]y=\frac{Y}{2}[/latex]) [latex]\frac{3}{4}XY[/latex].

On perd donc ainsi dans le pire des cas à chaque itération les 3/4 de notre plus gros rectangle.

On obtient ainsi un graphe binaire qui représente la construction de nos rectangles, chaque nouveau noeud divisant l'aire au pire de 3/4.
On obtient ensuite que l'aire totale est minorée par la somme des produits des diminutions faites à chaque noeuds. Le nombre total de diminutions étant le nombre d'itérations soit [latex]n-1[/latex].

EDIT, bon malheureusement je me suis un peu perdu...
Je crois pas pouvoir prouver que cette méthode marche, même si elle me semble convenir, parce que c'est pas aprce que l'on choisit le pire cas à chaque itération qu'on récupère e pire cas pour n rectangles...

 #58 - 25-01-2013 23:31:35

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

zu moins la moitié !

C'est gentil d'essayer Alex mais c'est loin d'être aussi simple smile

Je ne fais pas le malin pour autant , les quelques idées que j'avais partent en fumée les unes après les autres mad

Avis aux amateurs smile

Vasimolo

 #59 - 29-01-2013 19:18:13

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

Au moins l amoitié !

Juste un petit coucou pour dire que le problème est ouvert depuis 40 ans , alors n'y passez pas toutes vos nuits smile

Je peux donner des références pour ceux que ça intéresse .

Merci à ceux qui ont essayé smile

Vasimolo

 #60 - 30-01-2013 15:18:19

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

Au moins la moitié

Je veux bien les références steup ! smile

 #61 - 30-01-2013 17:15:10

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

Au moins la omitié !

Bonne lecture ( c'est un peu aride ) .



Bizarrement on a l'impression qu'on peut facilement faire mieux smile

Vasimolo

 #62 - 01-02-2013 17:53:57

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

Au moins la mmoitié !

Merci bien. Je lirai ça un de ces soirs au coin du feu pour me détendre.
Je vois qu'ils ont quand même fait pas mal de dessins, ça aide à digérer... big_smile

 

Réponse rapide

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

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

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