10% en commun

[Imod]

Un petit problème qui a l'air à priori assez abordable mais qui me laisse un peu désarmé .

On dessine deux figures identiques sur deux feuilles puis on découpe indépendamment chacune d'entre elles en dix morceaux ( par forcément les mêmes ) . On colorie ensuite les dix morceaux de la première figure en dix couleurs différentes , une par morceau . On retourne les morceaux de la deuxième feuille que l'on colorie aussi avec les mêmes couleurs que la première ( toujours une couleur par morceau ) . On reconstitue ensuite les deux figures et on les colle dos à dos pour faire apparaître un coloriage des deux côtés .

Question : peut-on toujours choisir un coloriage qui fasse apparaître au moins 10% de surface de la même couleur recto-verso ?

Ca semble évident mais comment justifier ???

Imod

[windows7]

salut,

On note la feuille A et la feuille B sur lesquelles on dessines les 2 figures identiques.
on ordonne les morceaux decoupé sur A en fonction de leur aire
a1>a2...... >a10
idem pour la figure B
b1>b2.....>b10

on colorie de la meme couleure a1 et b1, de la meme couleur a2,b2 ...

on a donc une surface de meme couleure egale a min(a1,b1)+ ... min(a10,b10)

> 1/10 sous la condition a1+... a10=b1+...b10

[Ben314]

Salut,
Si tu fait les deux découpes "simultanéments", tu te retrouve avec morceaux () de surface où avec =numéro par rapport au premier découpage, =numéro par rapport au deuxième découpage (bien entendu certain des morceaux risquent d'ètre vides, c'est à dire tels que )
"Faire un coloriage", c'est colorier les pieces du premier découpage de couleur 1 pour , de couleur 2 pour , ... de couleur n pour et celles du second découpage de couleur 1 pour , de couleur 2 pour , ... de couleur n pour où est une permutation de .
Dans ce cas, la surface de la même couleur recto-verso est .
Or il est clair que donc il existe au moins un tel que , c'est à dire tel que la surface de la même couleur recto-verso représente plus de du total (en fait, ce est la moyenne de ce que l'on peut espérer comme surface de la même couleur recto-verso si on fait un coloriage au hasard)

[windows7]

j'avais compris de travers le pb en effet

[Ben314]

j'avais compris de travers le pb en effet

Si ça peut te rassurer, à la première (et à la deuxième) lecture, j'avais pas bien compris non plus.

D'un autre coté, je sais pas si ma "preuve" est super claire...

[Imod]

J'ai bien compris l'idée et c'est vrai que ce n'est pas facile à exprimer d'autant qu'intuitivement c'est assez évident ( on ne recommence pas la polémique ) . Ton développement est plutôt convainquant , je ne sais pas si on peut faire plus simple ?

Imod

[Doraki]

J'avais pensé à la même chose mais au lieu de faire agir tout le groupe S10, je fais juste agir un 10-cycle.

[Ben314]

J'avais pensé à la même chose mais au lieu de faire agir tout le groupe S10, je fais juste agir un 10-cycle.

Ce qui, en plus, montre qu'il y a au moins 9! solutions (bien sûr aprés choisi le coloriage d'un des deux découpages)...

[nodjim]

La même démo mais avec une autre approche:
On réalise la découpe 1 en n morceaux, la découpe 2 en m morceaux (on suppose n>=m)
On fait un tableau. En tête de chaque ligne les ni morceaux, i=1 à n , et en tête de chaque colonne les mj morceaux, j=1 à m. On remplit chacune des n*m cases par la surface commune à ni et mj.
Tous les ensembles de cases (ni;mj) où chaque colonne est sélectionnée une et une seule fois et chaque ligne 1 fois au plus représente une solution. L'ensemble de toutes les solutions possibles est un multiple de la surface S de la figure, puisque toutes les cases sont représentées un nombre de fois égal, et que le total des données du tableau vaut S. On est donc en mesure d'établir une moyenne: S/n. Donc soit toutes les combis sont égales et valent toutes S/n soit elles ont des différences et donc on aura des combis >S/n.
Je ne suis pas trop sûr de la manière, avec ce tableau, de trouver la solution max. J'ai bien une idée mais je ne suis pas certain qu'elle marche.

[Ben314]

Je ne suis pas trop sûr de la manière, avec ce tableau, de trouver la solution max. J'ai bien une idée mais je ne suis pas certain qu'elle marche.

Si tu cherche juste "UNE" solution (et que m=n), la méthode Doraki est beaucoup plus "applicable" : une fois que tu as choisi "un élément par colonne", tu considère les n-1 autres coloriages obtenus en "décalant vers la droite" celui de départ (et bien sûr en considérant que la première colonne est à droite de la dernière). Parmi ces n coloriages, il y en a un forcément un qui est solution.
Par contre, je sais pas si "l'optimum" est facile à trouver.

[nodjim]

Si tu cherche juste "UNE" solution (et que m=n), la méthode Doraki est beaucoup plus "applicable" : une fois que tu as choisi "un élément par colonne", tu considère les n-1 autres coloriages obtenus en "décalant vers la droite" celui de départ (et bien sûr en considérant que la première colonne est à droite de la dernière). Parmi ces n coloriages, il y en a un forcément un qui est solution.
Par contre, je sais pas si "l'optimum" est facile à trouver.

D'accord, Ben. Mais il n'est pas besoin de faire la recherche d'une solution, on sait déja qu'elle existe, par la seule notion de la moyenne.

[Doraki]

Je ne suis pas trop sûr de la manière, avec ce tableau, de trouver la solution max. J'ai bien une idée mais je ne suis pas certain qu'elle marche.

Mais il n'est pas besoin de faire la recherche d'une solution, on sait déja qu'elle existe, par la seule notion de la moyenne.

J'ai corrigé ta citation, t'as du te tromper de post.

[Doraki]

J'vois pas d'autre manière de calculer toutes les possibilités si tu veux trouver le maximum

[nodjim]

J'vois pas d'autre manière de calculer toutes les possibilités si tu veux trouver le maximum

Moi non plus. On peut tout de même trouver une valeur approchée en choisissant en 1er la case de + forte valeur, puis la seconde compatible, etc...mais ça ne garantit pas le max. Je ne suis même pas certain que cette méthode donne un résultat > la moyenne.