Nombres de chemins

un_kiwi · September 2018

Bonjour, j'ai un problème de dénombrement que je ne comprends pas bien.

Déjà, je ne comprends pas le sens de la question 1.
J'ai réussi à répondre à la question 2., mais je sèche à nouveau à partir de la 3.
(A plusieurs reprises, on parle de suites alors que je ne vois pas quelles suites).

Merci d'avance

YvesM · September 2018

Bonjour,

Je comprends du problème posé que l’on dépouille les votes et donc que l’on compte les votes pour chacun des candidats de différentes façons (selon l’ordre de dépouillement). Les suites sont alors données par le décompte des votes. Par exemple pour deux votes on ne peut avoir $x, x,y,y$ ou $x,y,y,x$ ou $y,y,x,x$ etc.

gerard0 · September 2018

Bonjour Un_kiwi.

Tu comprendras mieux cette idée de chemin si tu représente le dépouillement par un quadrillage rectangulaire de a+1 colonnes et b+1 lignes. Les colonnes correspondent à des étapes de dépouillement avec x votes pour A, les lignes à y votes pour B. On part de (0,0), en bas à gauche; et par exemple si les bulletins donnent BBAAAB, on monte 2 fois, puis on décale trois fois à droite, et on monte de 1.
Un dépouillement complet est un chemin sur le quadrillage, où on a suivi les lignes ou les colonnes, et qui arrive en haut à droite (puisqu'il y a eu a et b votes). Regarde quels sont les chemins qui respectent x>y.

Cordialement.

un_kiwi · September 2018

Je regrette, je n'arrive pas à faire le lien avec ce qui est demandé.

gerard0 · September 2018

Alors cherche encore. Je t'ai donné la clef du problème, c'est à toi de faire les dessins correspondants. Si tu veux, tu peux traiter avec a=6 et b=4, ça fait un petit quadrillage. mais c'est ton exercice, c'est toi qui réfléchis ...

un_kiwi · September 2018

Pour la 1., je ne sais pas trop comment le formuler, ça me semble clair : les arrivées de votes étant indépendantes, on peut supposer que les scrutins sont equiprobables. L'univers sur lequel on travaille sera l'ensemble des
scrutins, lequel sera muni de l’équiprobabilité.

Pour la 3. Un scrutin peut être représenté par la suite donnée par le nombre
de voix pour A - nombre de voix pour B, en fonction du numéro de la voix dépouillée :
cela correspond à un chemin entre (0; 0) et (a+b; ?), au dessus de y=x, c-à-d à un chemin entre (0; 0) et (a+b; a-b), puisque tout au long du dépouillement A reste strictement en tête par rapport à B.

Un petit coup de main pour la question 4. ?

gerard0 · September 2018

As-tu fait la question ii ?

Je m'aperçois que la grille utilisée n'est pas la même que la mienne, elle est tournée de 45° vers la droite et on utilise les diagonales. C'est vrai que c'est plus pratique, lorsqu'on arrive sur l'axe des x, c'est qu'il y a égalité entre les candidats.

Pour le i, il suffit de dire qu'une suite de votes pour A ou pour B comprenant a votes pour A et b pour B est exactement ce qu'on obtient dans un dépouillement.

La iv est une conséquence immédiate du résultat du iii.

un_kiwi · September 2018

Oui, j'ai fait la question ii, je trouve $m_2-m_1$ parmi $(m_2-m_1+n_2-n_1)/2$. J'y pense, on peut montrer la question 3. en montrant que l'application f(x,y) =(x+y,x-y) est bijective, non ? Cela montrerait que chaque point du chemin allant de (0,0) à (a,b) restant en dessous de la première bissectrice correspond à un point du chemin allant de (0,0) à (a+b,a-b), êtes-vous d'accord ?

Eric · September 2018

Un petit tour du coté de L'Enseignement Mathématique, année 1923 https://www.unige.ch/math/EnsMath/EM_fr/welcome.html
pour consulter l'article de Aebly (p.185) et celui de Mirimanoff (p. 187).

Pour l'origine du problème, il faut consulter un article de Bertrand dans les Cras (année 1887, deuxième partie, tome 105) et les réponses de André et Barbier https://gallica.bnf.fr/services/engine/search/sru?operation=searchRetrieve&version=1.2&collapsing=disabled&query=arkPress all "cb343481087_date" and dc.date="1887" and (gallica all "bertrand") and (subgallica all "andré")&filter=#resultat-id-1
L'article de Bertrand est à la p. 369, la réponse de André (suivi d'un commentaire de Bertrand) aux pages 436-437, la remarque de Barbier à la page 407.