[Probas] Jeu idiot

[invite6de5f0ac]

Bonjour à tous,

J'ai un peu hésité, ce post aurait peut-être plus sa place en "Sciences Ludiques", mais comme c'est un calcul de proba... (chers modos, ne vous gênez pas pour le déplacer si vous le jugez utile).

Voilà, j'ai sur mon PC un petit jeu idiot ("time waster" comme ils disent), Znax pour ceux qui connaissent. Ca se présente comme un genre de damier 10x10 dont les cases sont coloriées (aléatoirement?) en 4 couleurs (bleu, vert, jaune, rouge). Le but du jeu est de repérer 4 cases de même couleur qui forment un rectangle (côtés parallèles à ceux du damier, pour les vicieux qui envisageraient des rectangles "obliques"), de les délimiter à la souris, alors le rectangle disparaît et est remplacé par de nouvelles cases coloriées "aléatoirement". Et on marque d'autant plus de points que le rectangle ainsi éliminé est grand.

Depuis que je m'amuse avec, je n'ai jamais eu le cas où aucun rectangle "homogène" n'existerait. Si le coloriage est aléatoire, quelle serait la probabilité que le cas se présente? Il est facile de calculer la probabilité qu'aucun rectangle bleu, par exemple, n'existe. Mais qu'aucun rectangle d'aucune couleur? J'avoue qu'on est dimanche, que je n'ai pas tout à fait fini mon petit déjeûner, et que la réponse est peut-être plus simple que je ne l'envisage...

-- françois
-----

[invite986312212]

cette probabilité n'est pas nulle en tout cas.

[GuYem]

Je ne comprends pas ce qu'il faut repérer :

-un rectangle formé de carrés TOUS de la même couleur

ou bien

-les quatre coins d'un rectangle qui sont de la même couleur

?

[GuYem]

Après reflexion, je me dis que c'est certainement la deuxième solution. Le jeu aurait moins d'intêret si c'était la première.

Du coup, je suis pressé de voir le screen de ambrosio !

[A voir en vidéo sur Futura]

[GuYem]

Ah oui, très pathologique ton exemple ambrosio !

Comment as-tu fait pour le trouver ? Tu as demandé à un logiciel quelconque ? Parce que si c'est de tête, chapeau !

[invite986312212]

c'est parce qu'on peut remplir un 5x5 avec 2 couleurs sans faire apparaître de rectangle (sur le dessin j'ai colorié la case centrale de chaque 5x5 avec une troisième couleur mais ce n'est pas nécessaire).

question 1: quelle est la plus grande taille de znax généralisé qui admette une configuration à 4 couleurs sans rectangle?

question 2: et avec n couleurs?

[invite6de5f0ac]

Merci de vos réponses. Et en particulier à ambrosio pour ce magnifique (contre) exemple bien pervers.
En regardant comment il est fait je soupçonne que c'est généralisable à une taille quelconque, mais je n'ai pas encore vérifié.

-- françois

[yat]

c'est parce qu'on peut remplir un 5x5 avec 2 couleurs sans faire apparaître de rectangle (sur le dessin j'ai colorié la case centrale de chaque 5x5 avec une troisième couleur mais ce n'est pas nécessaire).

Ta solution en 10x10 avec 4 couleurs est tout à fait valide, mais ce que tu dis là me surprend...

D'abord, si on colorie la case centrale d'un 5x5 avec une des deux couleurs, ça ne marche plus. Et de manière plus générale, remplir un 5x5 avec 2 couleurs sans faire apparaitre de rectangle, ce n'est pas possible.

[invite6de5f0ac]

@ yat : Si si, ça marche. Voir mon dessin ci-joint. Qui confirme ce que je pensais quant à la taille maximale...

-- françois

[yat]

@ yat : Si si, ça marche. Voir mon dessin ci-joint.

Je te laisse le soin de regarder un peu mieux le dessin, il y a de - très - nombreux rectangles, bleus et rouges. Donc, non, ça ne marche pas.

C'est normal : ici on a un carré de 7x7, c'est déjà impossible avec un carré de 5x5...

[invite986312212]

ah oui c'est vrai que ça marche pas le 5x5 comme je croyais. Yat, sais-tu démontrer que c'est impossible?

pour revenir à la question initiale, je ne vois pas du tout comment calculer cette probabilité. On pourrait l'estimer par simulation, mais j'imagine qu'elle est très faible, donc ce serait difficile d'avoir une estimation précise.

[yat]

ah oui c'est vrai que ça marche pas le 5x5 comme je croyais. Yat, sais-tu démontrer que c'est impossible?

C'est plutôt intuitif, mais je peux tenter par l'absurde avec les mains.

Admettons qu'il existe une solution. La première ligne contient nécessairement au moins trois cases de la même couleur. Pour la suite, j'appellerai les cases de cette couleur les cases A, et celles qui sont de l'autre couleur les cases B. Sur la première ligne, on a donc 3, 4 ou 5 cases A, je peux en choisir 3 au hasard s'il y en a plus, et ne considérer que les colonnes correspondantes. On se retrouve donc avec une grille de 3 par 5, la première ligne ne contenant que des cases A. Comme il n'y a pas de rectangle dans la figure de base, il n'y en a pas non plus dans cette figure extraite. On peut donc affirmer qu'à l'exception de la première ligne, aucune ligne ne contient plus d'une case A : si une ligne en contenait 2, celles-ci seraient à la verticale de deux cases A de la première ligne, et on aurait un rectangle. On peut alors ne considérer que les lignes 2 à 5, on se retrouve dans une configuration en 3 par 4 qui ne peut toujours pas contenir de rectangle, et dont chaque ligne contient au moins deux cases B. Si une de ces 4 lignes contenait 3 cases B, il suffirait de prendre une autre ligne au hasard, ses deux cases B seraient à la verticales de 2 cases B de la ligne à 3 cases B. Chaque ligne contient donc exactement 2 cases B. Si deux des 4 lignes avaient la même disposition, là encore elles formeraient un rectangle. Donc les 4 lignes ont toutes des configurations différentes.
Le problème c'est que des configurations de 2 cases B parmi 3, il n'en existe que 3.
donc, pas de solution.

[invite6de5f0ac]

Oups... J'étais tellent persuadé de mon coup que je m'étais mis de la m... dans les yeux. Désolé.
Cela dit, il me semble que le 5x5 d'ambrosio est quand même correct (du moins celui avec la case centrale d'une troisième couleur). Mais je préfère ne plus jurer de rien...

Pour ce qui est de la probabilité, c'est bien pour ça que je posais la question. J'ai beau le retourner dans tous les sens, je ne vois pas par quel bout le prendre!

-- françois

[yat]

Cela dit, il me semble que le 5x5 d'ambrosio est quand même correct (du moins celui avec la case centrale d'une troisième couleur). Mais je préfère ne plus jurer de rien...

Oui, avec la case centrale d'une troisième couleur ça marche. Sinon le 10x10 ne marcherait pas non plus. C'est juste en 2 couleurs que ça ne marche pas.

[invite986312212]

c'est un sujet passionnant. J'essayais hier de le relier aux problèmes de coloration de graphes et aux nombres de Ramsey, mais je n'ai pas trouvé quel graphe associer à la grille du znax.

[invite986312212]

voir: http://en.wikipedia.org/wiki/Ramsey_theory

[Stibium]

Bonjour,

ce probleme me fait penser a celui de l'existence des plans projectifs finis d'ordre n. Un plan projectif fini est une geometrie basee sur un corps fini. C'est un espace contenant
N=n^2+n+1 points et N droites, avec certaines proprietes. L'existence de ces espaces est un probleme delicat. On peut le ramener au probleme suivant:

Il s'agit de trouver une matrice NxN de 0 et de 1, avec N=n^2+n+1, telle que chaque ligne et chaque colonne possedent exactement n+1 fois le chiffre 1, avec la contrainte qu'il n'y ait aucun "rectangle" dont les quatre coins soient des 1.

L'existence d'une telle matrice est prouvee pour n puissance d'un nombre premier. Sa non-existence est prouvee si n est congru a 1 ou 2 modulo 4 et n'est pas sommme de deux carres. La non-existence est conjecturee pour tout autre n, mais c'est un probleme ouvert.

En particulier pour n=12, repartir 13 chiffres 1 dans chaque ligne et chaque colonne d'une matrice 157x157 sans faire apparaitre de rectangle de 1 est donc une question ouverte. Je ne suis donc pas certain que le probleme general du Znax soit facile!!

[invite986312212]

si je comprends bien, cette matrice est la matrice d'incidence points/lignes, la condition sur les rectangles dexprimant que deux droites ne peuvent se couper qu'en un unique point (?)
il y a quelques différences avec le znax : d'une part il y a 4 couleurs, qui chacune peuvent former des rectangles (alors que les rectangles de zéros ne posent pas de problème si j'ai bien compris), d'autre part, les contraintes sont moins strictes: rien ne dit par exemple qu'il faut 25 cases de chaque couleur. Est-ce que ça rend les choses plus compliquées ou moins compliquées, je ne saurais le dire.

est-ce qu'une interprétation en termes de géométrie de dimension supérieure pourrait éclairer le problème? par exemple en dimension 4, l'intersection entre un 2-plan et un 3-plan peut prendre 4 valeurs (vide, 1 point, 1 droite, inclusion) mais on n'aura jamais la contrainte des rectangles sur les intersections vides...

[invite6de5f0ac]

Ouille ouille ouille... je me doutais bien que ce ne serait pas facile, mais à ce point! Je cherche plus une démonstration du style de celle de yat pour l'impossibilité du 5x5 en 2 couleurs, mais ça risque de ne pas être possible. Je réfléchis quand même...

-- françois

[Stibium]

En effet, le probleme des plans projectifs finis est plus specifique (deux couleurs, et on ne s'interesse qu'aux rectangles de la couleur 1). La condition sur les rectangles impose que deux points definissent une droite et une seule, et que deux droites se coupent en un point et un seul.

La generalisation de ce probleme est une branche de la combinatoire qui traite des "block designs" (je ne connais pas le mot francais). Il faudrait peut-etre regarder dans cette direction. Mais le Znax est encore plus general puisqu'il n'impose pas le nombre de cases d'une couleur dans chaque ligne, ni meme si j'ai bien compris le nombre total de cases de chaque couleur (meme si intuitivement si une solution existe elle aurait plutot des couleurs equidistribuees...)

[invite986312212]

La generalisation de ce probleme est une branche de la combinatoire qui traite des "block designs" (je ne connais pas le mot francais).

plans d'expérience en blocs (en général on précise: blocs complets, blocs incomplets, équilibrés, etc). Je connais mal mais il me semble qu'on cherche des matrices d'expérience avec des contraintes particulières (matrices orthogonales ou orthogonales par blocs je crois).

juste par curiosité (je ne connais rien aux géométries finies): est-ce que l'interprétation géométrique aide à résoudre le problème dont tu as parlé, ou bien est-ce un pur problème de combinatoire?

[Stibium]

Ca fait bizarre en francais!

Les resultats que j'ai mentionnes sont des resultats de combinatoire (theoreme de Bruck-Ryser-Chowla). On peut se passer de l'interpretation geometrique.

[invite986312212]

ce nom vient des statistiques:
http://archive.numdam.org/ARCHIVE/MS...__23__37_0.pdf

[kNz]

Bonjour à tous,

Je suis ce thread depuis sa création, et ça m'intéresse assez. Je voudrais juste vous soumettre une idée, qui je pense doit être fausse, c'est pour ça que je poste en fait

Si on note "n'avoir aucun rectangle",



Avec "avoir au moins un rectangle"

Pourquoi ne pourrait-on pas dire que :



où k représente le nombre de couleurs, ce qui donnerait :



Merci de m'éclairer,

A+

[kNz]

Ah ba non c'est bon je vois