Une paire de brochettes

[Imod]

Des morceaux de viande ou de légumes sont représentés par des rectangles dont les côtés sont verticaux ou horizontaux et on suppose qu'on peut traverser toute paire de morceaux par un pic horizontal ou vertical . Montrer qu'il existe alors deux pics ( un horizontal et un vertical ) traversant l'ensemble des morceaux .



Amusez-vous bien :zen:

Imod

[miikou]

on place le bas des morceaus d'une type donne( par exemple ceux horizontaux ) sur une meme droite, l'intersection de ces morceaux 'virtuels' est non vide. sinon deux de ces derniers ne pourraient pas etre embroché ensemble

[nodgim]

il est évident qu'il est impossible pour un rectangle d'avoir une partie horizontale ou verticale commune avec chacun de 2 autres rectangles, sans se trouver sur la partie commune à ces 2 rectangles. :doh:

[Edward]

Ok je me lance.

D'abord on repère tous les morceaux que l'on ne peut pas joindre avec un trait horizontal ; nous appellerons ces morceaux les "morceaux 1". Ainsi, le plus haut placé délimitera le haut de notre "surface de travail" et le plus bas placé le bas. A partir de la, on différencie les zones restantes en 3 types de zones :
- Les zones enclavées : les morceaux placés dans cette zone peuvent être coupés par 2 pics, l'un horizontal et l'autre vertical, de telle sorte que ces pics traversent le dit morceau et au moins un morceau 1. Tout autre bloc ne remplissant pas cette condition devient un morceau 1.
- Les zones périphériques : les pics qui traversent les morceaux de cette zone, s'ils veulent traverser les morceaux 1, ne peuvent être qu'horizontaux.
- Les zones restantes sont des zones où l'on ne peut former que des morceaux 1.

Un petit dessin (morceaux 1 en jaune, zones enclavées en rouge et zones périphériques en bleu) :



Suposons qu'un morceau se trouve dans une zone périphérique. il doit nécessairement atteindre la hauteur du bas du morceau 1 le plus haut et celle du haut du morceau 1 le plus bas.
S'il n'y a qu'un seul morceau 1, un seul pic, horizontal, coupe les 2 morceaux. Tous les autres morceaux qui devront etre rajoutés seront coupés par ce pic. On peut donc placer le pic vertical n'importe où.
S'il y a plusieurs morceux 1, le pic vertical passera par ces dits morceaux. Quant au pic horizontal, il coupera le morceau de la zone périphérique avec un morceau 1. On a ainsi plusieurs possibilités de pics horizontaux, que je réduis à une par morceau 1 pour faire plus clair ^^ (ils s'agit en réalité de plusieurs "zones" possibles).
Si des morceaux viennent à être ajoutés dans les zones périphériques, comme ils doivent avoir la même hauteur minimale que le 1er, il y a toujours autant de possibilités de pics horizontaux.

Si un morceau vient à être ajouté dans les zones enclavés, ils doit être "aligné" sur le plan horizontal (puisque il ne peut pas l'être autrement) avec au moins un morceau 1 et tous les morceaux périphériques. Se faisant, il diminue le nombre de possibilités de pics horizontaux, puisque tout bloc d'une zone enclavé n'es pas "aligné " sur le plan horizontal avec au moins un morceau 1.
Ajoutons d'autres morceaux dans la même zone enclavée, plusieurs possibilités s'offrent à nous :
- le morceau ajouté est "aligné" horizontalement avec le précédent, il l'est donc également avec le/les morceau/x 1 aligné/s avec ce dernier morceau : il reste toujours au moins une solution.
- le morceau ajouté est "aligné" verticalement avec le précédent. Ces deux morceaux deviennent des morceaux 1, et le morceau 1 précédent devient un morceau enclavé, (petite illustration suivant le shéma précédent, j'ai eu la flemme de changer la couleur des lignes^^) :



A noter que l'on aurait pu permuter les morceaux 1 et 2 avant d'ajouter le 3, mais cela n'aurait rien changé.

Si l'on ajoute un morceau dans une autre zone enclavée, le pic horizontal ne coupera que les morceaux enclavés et périphériques. En effet, le morceau placé dans la deuxieme zone n'est pas aligné horizontalement avec le morceau 1 aligné avec le premier morceau enclavé.

Pour récapituler, il existe bien 2 pics (horizontal et vertical) traversant l'ensemble des morceaux. Le pic vertical passe par les morceaux 1 de départ ou ceux restant après la permutation de morceaux enclavés et de morceaux 1. Le pic horizontal peut passer soit uniquement par le morceaux périphériques et enclavés (s'il y a des morceaux dans plusieurs zones enclavées), soit également par des morceaux 1, s'il n'y a des morceaux enclavés que dans une zone enclavée.

Il va sans dire que j'ai pris un schéma relativement simple par rapport à tous les cas possibles, mais le raisonnement reste le même pour toutes autres dispositions de morceaux 1, il faut juste raisonner avec plus de zones enclavées.

[miikou]

oh edward tu as fait bien long ;)
Imod a le don de rendre compliquées des choses qui en réalite ne le sont pas!
pour les morceau horizontaux on les assimile a un segment, et on les projete sur une meme droite paralèlle ( ;) ) . le fait que qu'on puisse embrocher chaqun des couples avec un piquet perpendiculaire traduit simplement le fait que ' l'intersection de ces segments sur la droite n'est pas vide', donc l'ensemble l'intersection de tout les segments non plus, on peut directement conclure :++:

[Patastronch]

oh edward tu as fait bien long
Imod a le don de rendre compliquées des choses qui en réalite ne le sont pas!
pour les morceau horizontaux on les assimile a un segment, et on les projete sur une meme droite paralèlle ( ) . le fait que qu'on puisse embrocher chaqun des couples avec un piquet perpendiculaire traduit simplement le fait que ' l'intersection de ces segments sur la droite n'est pas vide', donc l'ensemble l'intersection de tout les segments non plus, on peut directement conclure :++:

C'est quoi que t'appelles les morceau horizontaux ? Ceux qui seront embroché horizontalement dans une des solutions possibles ? Tu serais pas en train de supposer que la solution existe pour prouver son existence ?

[Edward]

oh edward tu as fait bien long
Imod a le don de rendre compliquées des choses qui en réalite ne le sont pas!

J'avais remarqué ^^. Et ce don va de pair avec le mien qui me pousse à toujours chercher une solution compliquée à un problème simple !

pour les morceau horizontaux on les assimile a un segment, et on les projete sur une meme droite paralèlle ( ) . le fait que qu'on puisse embrocher chaqun des couples avec un piquet perpendiculaire traduit simplement le fait que ' l'intersection de ces segments sur la droite n'est pas vide', donc l'ensemble l'intersection de tout les segments non plus, on peut directement conclure :++:

J'ai du mal à te suivre, il est passé ou le pic horizontal ?

[Imod]

D'abord on repère tous les morceaux que l'on ne peut pas joindre avec un trait horizontal ; nous appellerons ces morceaux les "morceaux 1".

Je ne comprends pas cette définition . Tu considères une partie extrémale de l'ensemble des morceaux telle que deux éléments de cette partie ne puisse pas être joints par un pic horizontal ?

Imod

[Edward]

Je ne comprends pas cette définition . Tu considères une partie extrémale de l'ensemble des morceaux telle que deux éléments de cette partie ne puisse pas être joints par un pic horizontal ?

Imod

C'est ça !

[Imod]

Les zones enclavées : les morceaux placés dans cette zone peuvent être coupés par 2 pics, l'un horizontal et l'autre vertical, de telle sorte que ces pics traversent le dit morceau et au moins un morceau 1. Tout autre bloc ne remplissant pas cette condition devient un morceau 1.

L'apparition d'un nouveau morceau 1 ne risque pas de créer de nouvelles zones enclavées ?

Imod

PS : désolé je lis très lentement :marteau:

[Edward]

L'apparition d'un nouveau morceau 1 ne risque pas de créer de nouvelles zones enclavées ?

Oui j'en parle dans mon raisonnement :
"Ajoutons d'autres morceaux dans la même zone enclavée, plusieurs possibilités s'offrent à nous :
- [...]
- le morceau ajouté est "aligné" verticalement avec le précédent. Ces deux morceaux deviennent des morceaux 1, et le morceau 1 précédent devient un morceau enclavé "

[miikou]

C'est quoi que t'appelles les morceau horizontaux ? Ceux qui seront embroché horizontalement dans une des solutions possibles ? Tu serais pas en train de supposer que la solution existe pour prouver son existence ?

salut, il est possible que j'ai mal compris le pb
les morceaux horizontaux sont les morceaux jaunes du dessin de imod.
il dit que toute paire peut etre embrochée par un piquet vertical.
si tu met tout ces morceaux jaunes au meme niveau ( sur la meme ligne) cela veut dire que pour toute paire l'intersection est non vide es tu d'accord ?
donc l'ensemble des intersection est non vide egalement, d'ou lexistance d'un piquet vertical traversant tout les morceau jaunes.
On applique le meme raisonement pour les verticaux et on conclus

[Patastronch]

salut, il est possible que j'ai mal compris le pb
les morceaux horizontaux sont les morceaux jaunes du dessin de imod.
il dit que toute paire peut etre embrochée par un piquet vertical.
si tu met tout ces morceaux jaunes au meme niveau ( sur la meme ligne) cela veut dire que pour toute paire l'intersection est non vide es tu d'accord ?
donc l'ensemble des intersection est non vide egalement, d'ou lexistance d'un piquet vertical traversant tout les morceau jaunes.
On applique le meme raisonement pour les verticaux et on conclus

Oui j'ai compris ton raisonnement, mais la partition en morceau jaune et bleu ne peut se faire que qaund on a deja une solution (Imod nous l'a fait pour clarifier son dessin et une soution qui s'y applique). Supposer que cette partition existe dejà c'est supposer qu'une solution existe (ou alros j'ai rien compris au probleme). La seule chose qu'on sait sur les morceaux et leur disposition c 'est que toutes paires de morceaux peut etre traversé par une droite verticale OU horizontale.

Bon j'ai une solution assez laborieuse qui fait appel a la théorie des graphe. Si chaque morceau est un sommet, on trace le graphe complet composé de ces sommets dans lequel on a 2 type d'arrete : le bleu et les jaune. Si une arrete est bleue ca signifie que les 2 morceau correspondant aux sommets qu'elle relie sont placé sur une meme horizontale (et jaune pour la verticalité).

Une solution dans ce graphe est alors un couple de clique (une jaune et une bleu) dont l'union des sommets est egale à la totalité des sommets. En effet la clique bleu correspond aux morceaux qui peuvent etre traversé par une unique droite horizontale tous a la fois (et la clique jaune pour la verticale) => justification par l'argument de Nodgim. Avec une démonstration laborieuse par récurrence, je pense avoir reussi a prouver que dans tous graphe complet composé de 2 types d'arretes on peut toujours trouver ces 2 cliques "complémentaires". Je ne sais pas si j'ai été clair mais c'est pas tres grave au fond, cette solution est trop bourrin a mon gout :p

[Doraki]

J'ai un graphe complet à 4 sommet, avec des arêtes jaunes et bleues sans pour autant avoir de partition des 4 sommets en 1 clique jaune et 1 clique bleue, c'est grave ?

[Patastronch]

J'ai un graphe complet à 4 sommet, avec des arêtes jaunes et bleues sans pour autant avoir de partition des 4 sommets en 1 clique jaune et 1 clique bleue, c'est grave ?

Oui car ca voudrait dire que ma demo est fausse ou que ma modélisation sous forme de graphe n'est pas equivalente au probleme d'Imod.
Donne le graphe stp
Oublie pas qu'un sommet seul forme une clique d'un sommet.

[Patastronch]

Bon je viens de revoir ma démo, elle est fausse :(

En plus ma modélisation n'est pas une equivalence !! Tous les graphes complets avec 2 types d'arretes ne correspondent pas forcément à une disposition de blocks possiible (alors que l'inverse si).

Enfin tout ca pour dire que j'ai tout faux :D

[scelerat]

Bon, deja en dimension 1, prenons un intervalle. Il a au moins un point commun avec chacun des autres donc chacun des autres a une borne superieure >= a sa borne inferieure. Quels que soient i et j, Si >= Ij, donc min{Si}>=max{Ij}, l'intervalle [max{Ij},min{Si}] est defini non vide et represente l'intersection de tous les intervalles.