Forum de mathématiques - Bibm@th.net

En fait j'ai bien peur qu'on ne sache pas trop quelle est la question...
Si les nombres sont dans l'ordre et qu'on dispose des numéros des cases dans lesquels il se trouve, il suffit en effet de lire les nombres l'un après l'autre et quand un nombre ne correspond pas au numéro de sa case c'est que le numéro de la case est q est le nombre qui est répété est le contenu de la case.
Effectivement la deuxième réponse de freddy permet d'éviter de devoir disposer des numéros des cases : dès qu'on repère un [tex]a_{i+1}-a_i[/tex], on sait que [tex]q=a_i + 1\; (=i+1[/tex])et que [tex]p=a_q=a_{i+1}[/tex]. Mais il faut quand même lire [tex]q[/tex] nombres.
Mais ce qui me gêne surtout c'est que le nombre maximal de lectures dépend de [tex]q[/tex]. Parce que si la personne qui fait l'opération choisit [tex]q=100[/tex], la méthode de Freddy conduit à lire tous les nombres ! Donc je ne vois pas ce qu'on gagne. Et en plus dans ce cas, la méthode qui consiste à prendre les nombres à partir du centième sera beaucoup plus efficace !!! Une lecture suffira ! Donc en quoi être certain de trouver [tex]q<[/tex] lectures est-il le plus intéressant ? De manière générale si la méthode consiste à lire les nombres et à les comparer au numéro de leur case, alors quel que soit l'ordre dans lequel on lit les nombres il sera toujours possible que par malchance on ne trouve [tex]p[/tex] et [tex]q[/tex]  qu'à la fin, tout comme il est possible qu'on les trouve au début. D'où cette question que je posais, est-ce qu'on cherche à minimiser le maximum de lectures que requiert la méthode, ou à prendre un point de vue probabiliste ? Dans le premier cas, je ne vois pas comment s'en sortir à coup sûr en étant certain de ne pas devoir lire tous les nombres. Et si on prend le point de vue probabiliste et qu'on considère que les nombres [tex]p[/tex] et [tex]q[/tex]  sont choisis aléatoirement, alors j'ai l'impression que toutes les méthodes consistant à lire les nombres et à les comparer au numéro de la case prennent en moyenne le même nombre de lectures, à savoir 50.
C'est pour cela que j'avais considéré comme sous-entendu d'une part que les nombres étaient dans un ordre arbitraire et que d'autre part on ne pouvait pas garder mémoire de la liste des nombres déjà lus.

Plus sérieusement, il faudrait savoir si ce qu'on cherche c'est une méthode telle que le maximum de comparaisons à faire soit le plus petit possible, ou telle que l'espérance du nombre de comparaisons soit la plus petite possible (le tableau étant supposé aléatoire, [tex]n[/tex] étant fixé).
Par exemple, la méthode suivante me semble assez efficace, surtout si l'ordre des nombres dans le tableau est très aléatoire.
On prend le 1er nombre [tex]a_1[/tex], on le compare à tous les autres et on compte combien de ces autres sont strictement inférieurs à [tex]a_1[/tex].
Si on ne retrouve jamais le même nombre et qu'on retrouve [tex]a_1-1[/tex] nombres qui lui sont inférieurs, c'est soit que [tex]p[/tex] et [tex]q[/tex] sont tous deux strictement inférieurs à [tex]a_1[/tex], soit qu'ils lui sont tous deux strictement supérieurs. Si on en retrouve [tex]a_1-2[/tex] c'est que [tex]q[/tex] est strictement inférieur à [tex]a_1[/tex] et [tex]p[/tex] lui est strictement supérieur. Si on en retrouve [tex]a_1[/tex], c'est le contraire. Aucun autre cas n'est possible. Et si jamais je retrouve une deuxième fois la valeur [tex]a_1[/tex], alors c'est que cette valeur est [tex]p[/tex], quant à [tex]q[/tex] il est strictement inférieur si on trouve [tex]a_1-2[/tex] nombres inférieurs à [tex]a_1[/tex] et il lui est strictement supérieur si on en trouve [tex]a_1-1[/tex]. En continuant le même processus avec [tex]a_2[/tex] puis [tex]a_3[/tex] on a des chances de délimiter assez vite des intervalles possibles et de cerner les deux nombres par une sorte de dichotomie. Je serais incapable de déterminer si cette méthode est d'un point de vue probabiliste plus efficace que de comparer tous les nombres deux à deux, intuitivement je pense tout de même que oui. Mais si par malheur les nombres sont bêtement placés dans l'ordre croissant et que [tex]p=n[/tex] et [tex]q=n-1[/tex], cette méthode nécessitera bien de comparer deux à deux tous les nombres.

Ah ? C'est vrai, mais il me semble qu'on n'en a pas besoin. Mon raisonnement, exprimé de façon brouillonne il est vrai, consistait à observer que si on exclut les parties qui sont infinies parce qu'on a une bleue, une rouge et d'autres boules, e où on tire toujours une bleue et une rouge ad infinitum (on peut les exclure car elles sont en nombre fini et chacune de probabilité nulle), et si pour simplifier le discours on dit que la partie se termine à l'avantage du commissaire si on aboutit à une rouge et une bleue, alors toute partie se termine soit par une rouge, soit une blanche, soit une bleue, soit une rouge et une bleue. Cela me paraît évident en voyant la forme des règles, mais si on veut en donner une preuve mathématique, il suffit de voir que  dans toute autre situation (qu'une boule, ou une bleue et une rouge), il reste possible d'appliquer la règle 1, la 2 ou la 3 or chacune de ces règles diminue strictement le nombre de boules, ou le nombre de points attribués selon la méthode de mon dernier message, ou la somme du nombre de boules blanches et de boules bleues, et n'augmente jamais l'un de ces trois nombres : la seule possibilité pour une partie infinie est donc celle que je citais plus haut, le tirage systématique d'une bleue et d'une rouge alors qu'il y a au moins trois boules. A noter que chaque règle laisse inchangés, ou peut laisser inchangés, deux de ces trois nombres, c'est pour ça que j'ai été obligé de considérer les trois.
Puisque 1 bleue = 1 pt, une blanche = 2 pts, 1 rouge = 3 points et 1 bleue + 1 rouge = 4 points et que les règles ne modifient jamais le nombre de points modulo 4, il vient que toute partie avec au départ n boules aboutira inexorablement à 1 bleue si n est congru à 1 (mod 4), une blanche s'il est congru à 2, une rouge s'il est congru à 3 et une bleue et une rouge s'il est congru à 4.

A plus, goz.

Je dirais un nombre de la forme 4n...
Ce qui est certain c'est que si le nombre est impair alors le joueur 1 gagne. En effet on se convainc plus ou moins aisément (euh j'espère que c'est juste) que le commissaire gagne à coup sûr si et seulement si à tout moment de la partie il est encore possible que la situation évolue vers une boule bleue et une rouge (et rien d'autre) tandis que le joueur 1 gagne à coup sûr si à tout moment de la partie la situation peut évoluer vers une seule boule (donc préalablement vers une rouge et une blanche ou une blanche et une bleue ou deux bleues ou deux rouges). Si on attribue 1 point par boule rouge ou bleue et deux points par boule blanche, on voit qu el'application des règles ne modifie jamais la parité du total des points (tant qu'on peut jouer, c'est-à-die tant qu'avant le tirage il reste au moins deux boules). Donc si au départ il y a un nombre impair de boules on ne peut évoluer que vers une situation impaire (sachant que la probabilité de suivre une branche infinie autre que le blocage rouge-bleu : situation inchangée parce qu'on tire systématiquement une bleue et une rouge alors qu'il y a au moins trois boules) est nulle).
Je pense que si le nombre de boules est de la forme 4n + 2, alors toutes les situations (autres que les branches infinies) évoluent vers une unique boule blanche, et que s'il a la forme 4n alors il évolue vers une rouge et une bleue. J'ai une idée pour le démontrer par récurrence mais je n'y arrive pas tout à fait.