Algorithme Lotofoot

Bonjour à tous,

J'aimerais créer un logiciel sur le lotofoot.
Mon problème est le calcul pour réduire les mises.
Ex:
lotofoot à 15 matches.
Je veux jouer 3 doubles.
Soit Match 1 : 1N
Match 2 : N2
Match 3 : 1N
Match 4 : 1
Match 5 : 1
...
Match 15 : 1
En jouant directement 3 doubles à la Française des jeux, je devrait jouer 8 grilles pour avoir 15 bons résultats sur 15 matchs. (2^3 = 8)
Mais si je voulais un mimum de 14 matchs gagnants, il me faudrait moins de grille.Donc je fais appel aux différents matheux de ce forum pour m'aider à trouver une formule de réduction.

Merci de votre attention.
@++ :D

Bonjour
La question n'est pas très clairement posée...

Citation:

---

En jouant directement 3 doubles à la Française des jeux, je devrait jouer 8 grilles pour avoir 15 bons résultats sur 15 matchs.

---

Pour moi, pour etre sur d'avior 15 bons matchs, il faut jouer TOUTES les possibilités, c'est à dire les 32768 gilles possibles (mais ca fait beaucoup non ?)
Mais pour ce raisonnement, j'y mets de la mauvaise foi.

Si en jouant 8 grilles, on est sur d'avoir 15 bons matchs, alors 4 grilles suffiront pour en avoir 14 de bons : on joue un des match sans espoir de le gagner (par ex : match 1 : 1 au lieu de 1N)

Mais je n'ai peut être pas très bien compris le problème... Peux tu etre plus explicite ? Merci

Salut mabu,

Nous avons 15 matchs =>
01 - 1N
02 - N2
03 - 1N
04 - 1
05 - 1
06 - 1
07 - 1
08 - 1
09 - 1
10 - 1
11 - 1
12 - 1
13 - 1
14 - 1
15 - 1

Les matchs 4 à 15 sont gagnats car 1 seule possibilité.
Par contre les matchs 1 à 3 ont plusieurs combinaisons possibles.
Nous pouvons avoir :
1ere possibilité
01 - 1
02 - N
03 - 1

2eme possibilité
01 - 1
02 - N
03 - N

3eme possibilité
01 - N
02 - N
03 - 1

4eme possibilité
01 - N
02 - N
03 - N

5eme possibilité
01 - 1
02 - 2
03 - 1

6eme possibilité
01 - 1
02 - 2
03 - N

7eme possibilité
01 - N
02 - 2
03 - 1

8eme possibilité
01 - N
02 - 2
03 - N

En jouant 2 grilles nous pouvons avoir 14 resultats bons sur 15 à tous les coups

4eme possibilité
01 - N
02 - N
03 - N

5eme possibilité
01 - 1
02 - 2
03 - 1

Ce logiciel permettrait de réduire mes grilles au lotofoot en ayant une garantie d'avoir 14 bons résultats sur 15 en jouant dans cet exemple 2 € au lieu de 8 €.

Donc j'aimerais savoir quelle formule de calcul me permettrait d'obtenir ce résultat.

Merci.

Okay, j'ai pigé le problème....
En fiat, c'est côté cobinatoire qu'il faudra chercher je pense :
les 3 premiers matchs peuvent etre soit gagnant soit perdant (vrai ou faux).
Sur le papier, c'est facile de dire qu'il suffit de jouer deux fois pour avoir 14 bonne réponses (pareil pour en avoir 13), mais ca me parrait dur de déterminer une formule mathématique miracle...

Une idée serait de générer tous les cas de figure possible et tester des ensembles de solutions pour savoir lesquels sont à coup sur gagnant : c'est facile à faire mais très très très couteux en temps de calcul...

Pour une formule générale, je vais chercher dans mais souvenir d'automatisme...
Peut être un réponse plus tard :)

Merci bien Mabu de m'avoir répondu :)

je comprend en gros ce que tu veux faire mais je vois pas ou ca va te mener !
tu crois que tu rentrera ds tes frait ?
puis il y a plus de cas :
1-1-1
1-1-n
1-1-2
1-n-1
1-n-n
1-n-2
1-2-1
1-2-n
1-2-2
etc .....donc 9*3 possibilté

Citation:

---

Envoyé par schmur1

je comprend en gros ce que tu veux faire mais je vois pas ou ca va te mener !
tu crois que tu rentrera ds tes frait ?
puis il y a plus de cas :
1-1-1
1-1-n
1-1-2
1-n-1
1-n-n
1-n-2
1-2-1
1-2-n
1-2-2
etc .....donc 9*3 possibilté

---

Les cas que tu cites sont des triples et non des doubles
On aurait eu dans ton cas :
01 - 1N2 et non 1N
02 - 1N2 et non N2
03 - 1N2 et non 1N
04 - 1
05 - 1
06 - 1
07 - 1
08 - 1
09 - 1
10 - 1
11 - 1
12 - 1
13 - 1
14 - 1
15 - 1

Je crois que vous êtes en train de vous faire des films, s'il était possible d'avoir les bons résultats avec 8 grilles seulement, ça fait longtemps que la francaise des jeux aurait abandonnée le lotofoot. :wink:

Je suis daccord avec c-top

Ou alors je ne comprend pas ou vous voulez en venir

Salut,

Citation:

---

Envoyé par c-top

Je crois que vous êtes en train de vous faire des films, s'il était possible d'avoir les bons résultats avec 8 grilles seulement, ça fait longtemps que la francaise des jeux aurait abandonnée le lotofoot. :wink:

---

Citation:

---

Envoyé par kacedda

Je suis daccord avec c-top

Ou alors je ne comprend pas ou vous voulez en venir

---

D'après ce que je comprend, le but du jeu n'est pas d'avoir les 15 résultats bons (enfin... si on les a, tant mieux :D ), mais d'en avoir 14. Et sur ces 14, d'optimiser le nombres de grilles à jouer.

Là, c'est sur les 3 premiers matches que yoyo44 veut optimiser.

Je vais prendre un exemple plus causant... en supposant que le résultat du match soit soit une bille bleue, soit une bille rouge. Vu que les 13 autres matches n'entrent pas dans l'optimisation (on suppose qu'on est suffisament chanceux pour trouver le bon résultat), on parie sur le résultat des 3 autres. MAIS, on ne veut que 2 résultats de bons minimum sur les 3 (c'est là qu'intervient le critère 14 de bons sur 15). Donc au choix, chaque match se voit associer soit une bille bleue B, soit une rouge R. On va donc avoir les possibilités suivantes:

a - BBB
b - BBR
c - BRB
d - RBB
e - RRR
f - RRB
g - RBR
h - BRR

Dans ces combinaisons, on voit que l'on peut ne jouer que les combinaisons (a) et (e). Pourquoi? Parce que le résultat final sera soit trois billes de la même couleur, soit deux billes d'une couleur et la troisième de l'autre. Donc si on joue les combinaisons BBB et RRR, on est sûr d'avoir 2 bonnes couleurs quelque soit le résultat final.
Et au lieu de jouer 8 grilles, on n'en joue que 2.

Mais ça ne veut pas dire qu'on est sûr de gagner, vu qu'il y a douze matches pour lesquels on ne gère pas les multiples résultats! C'est seulement une optimisation des combinaisons afin de réduire la mise.

Par contre, à appliquer au LotoFoot, je sèche un peu...

Ou alors il faut tester en prenant comme résultat final l'une des grilles possibles. On regarde combien cette grille "couvre" d'autres grilles (en prenant les résultats ordonnés), et on ne conserve que les grilles qui en couvrent le plus.

Par exemple, si on prend la grille (a) comme masque, on obtient:

a- 3 bons résultats (BBB)
b- 2 bons résultats (BBx)
c- 2 bons résultats (BxB)
d- 2 bons résultats (xBB)
etc etc... résultat: 4 grilles couvertes

si on prend la grille (b):

a- 2 bons résultats (BBx)
b- 3 bons résultats (BBR)
c- 1 bon résultats (Bxx) => pas couvert
d- 1 bon résultat (xBx) => pas couvert
etc etc... résultat: 3 grilles couvertes

pareil pour les autres. Dans ce cas, on garde la (a), on supprime toutes les grilles couvertes par cette combinaison, et on recommence avec les grilles restantes (ce qui fait ressortir la combinaison (e) parmi les combinaisons (e), (f), (g) et (h)).

Salut plegat,

Tu as tout compris :), ça fait plaisir je croyais que je m'étais mal exprimé

Je ne sais pas s'il n'est pas inutile de rappeler que pour avoir 14 bons résultats il faut jouer 3^14 = 4 782 969 combinaisons. Sachant qu'une grille avec 3 doubles permet de jouer 8 combinaisons il faut donc un minimum de 597 872 grilles. Après ça il faut savoir les combiner, et après ces chiffres je ne suis pas sûr que ce soit utile d'y réfléchir.

Si on a une incertitude sur 3 doubles, il faut comme cela a été dit, 2 grilles pour être sûr d'avoir 14 bons résultats. Cela se démontre simplement en énumérant les 8 cas possibles. (S'il n'y a qu'un double, il faut un une seule grille. S'il y a 2 doubles, il faut 2 grilles).

En revanche, s'il y a une incertitude sur k>2 doubles, il faut 2^(k-2) grilles. Pour le démontrer, j'ai modélisé chaque grille par un chemin dans un graphe et dénombré le nombre de chemins qu'il fallait. C'est un peu long à écrire mais je peux m'y atteler ce soir ou demain si cela intéresse quelqu'un (et pour vraiment valider la démonstration :koi:)

Erratum: Voir correctif à ce message un peu plus loin dans le fil de la discussion...

Citation:

---

Envoyé par FrancisSourd

Si on a une incertitude sur 3 doubles, il faut comme cela a été dit, 2 grilles pour être sûr d'avoir 14 bons résultats. Cela se démontre simplement en énumérant les 8 cas possibles. (S'il n'y a qu'un double, il faut un une seule grille. S'il y a 2 doubles, il faut 2 grilles).

En revanche, s'il y a une incertitude sur k>2 doubles, il faut 2^(k-2) grilles. Pour le démontrer, j'ai modélisé chaque grille par un chemin dans un graphe et dénombré le nombre de chemins qu'il fallait. C'est un peu long à écrire mais je peux m'y atteler ce soir ou demain si cela intéresse quelqu'un (et pour vraiment valider la démonstration :koi:)

---

Salut FrancisSourd,

Ca m'intéresse bien
Merci @++

Citation:

---

Envoyé par FrancisSourd

En revanche, s'il y a une incertitude sur k>2 doubles, il faut 2^(k-2) grilles. Pour le démontrer, j'ai modélisé chaque grille par un chemin dans un graphe et dénombré le nombre de chemins qu'il fallait. C'est un peu long à écrire mais je peux m'y atteler ce soir ou demain si cela intéresse quelqu'un (et pour vraiment valider la démonstration :koi:)

---

Je suis curieux de voir cette démonstration, ou même simplement un exemple de 8 grilles pour le cas k=5.

En réfléchissant cette nuit, je me suis aperçu qu'il y avait un problème dans la démo.... Voilà donc où j'en suis:

• - Il y a une solution avec 2^(k-2) grilles
  - Il faut au moins 2^k/(k+1) grilles

Pour construire une solution avec 2^(k-2) grilles, je me suis basé sur ta solution à k=3. Par exemple, pour le problème (k=7)
1N
N2
N2
1N
1N
12
1N
on doit générer les deux familles de grilles (notations type expressions régulières):
1NN[1N][1N][12][1N] et N22[1N][1N][12][1N]
Cela fait donc 2 fois 2^(k-3) grilles soit 2^(k-2) grilles.

Pour la borne inférieure: soit S l'ensemble des grilles jouées.
Pour une grille x de S, soit S(x) l'ensemble des grilles qui diffèrent d'un résultat par rapport à x. Par exemple avec le problème précédent
S(1NN1111)={NNN1111, 12N1111, 1N21111, 1NNN111, 1NN1N11, 1NN1121, 1NN111N}
Clairement |S(x)| = k.
Pour être sûr d'avoir au plus un résultat faux, il faut que tous les résultats possibles soient dans l'union de S et de tous les S(x) (pour x variant dans S). Comme il y a 2^k résultats possibles, il faut que
2^k <= |S union U_x S(x) | <= |S| + sum_x |S(x)|
Or, pour tout x, |S(x)| = k donc
sum_{x in S} |S(x)| = sum_{x in S} k = k|S|
Donc l'inégalité s'écrit
2^k <= (k+1)|S| et donc |S| >= 2^k/(k+1)

Le nombre minimal de grilles à remplir est donc compris entre (2^k)/(k+1) et 2^(k-2).
Lorsque k=3, ces deux valeurs valent 2. Pour k>3, le problème reste ouvert.

J'ai modélisé le problème comme un programme linéaire en nombres entiers pour trouver les solutions optimales pour les petites valeurs de k. Pour représenter les solutions, j'ai codé les grilles par k valeurs 0/1. Un 0 signifie qu'il faut sélectionner le premier choix et 1 le second choix.

Par exemple, pour le problème avec k = 4:
1N
N2
N2
1N

Les 4 solutions sont 1000 1110 0101 et 0011, ce qui veut dire qu'il faut cocher les cases NNN1 N221 12NN et 1N2N.

Je me suis arrêté à k=9 car ce problème demande presque trois heures de calcul. Voici donc les résultats (ils sont compatibles avec les bornes trouvées dans le mail précédent :D ):

Citation:

---

k = 3 Optimal Value = 2 grilles
110 001

k = 4 Optimal Value = 4 grilles
1000 1110 0101 0011

k = 5 Optimal Value = 7 grilles
00100 10010 01110 01001
11001 11101 00111

k = 6 Optimal Value = 12 grilles
001000 010100 110100 100010 111010 101110
001001 101001 110101 010011 000111 011111

k = 7 Optimal Value = 16 grilles
1100000 0011000 1010100 0101100 0110010 1001010
0000110 1111110 0000001 1111001 0110101 1001101
1010011 0101011 1100111 0011111

k = 8 Optimal Value = 32 grilles
10100000 01010000 10001000 01111000 00000100 01100100
11011100 10111100 11000010 11110010 00101010 00011010
10010110 00110110 01001110 11101110 10010001 00110001
01001001 11101001 11000101 11110101 00101101 00011101
00000011 01100011 11011011 10111011 10100111 01010111
10001111 01111111

---

Je suis de moins en moins convaincu sur le fait qu'on puisse trouver une formule générale pour tout k.

J'ai soumis en termes mathématiques le problème à un forum de recherche et j'ai reçu en réponse ce lien très intéressant qui donne plusieurs références sur ce problème. En particulier, il n'y a pas de formule "magique" pour générer la suite (pour k=9, il faut 62 grilles mais ensuite le problème est ouvert...)

http://www.research.att.com/projects/OEIS?Anum=A000983

Commentaire: Ce site est rigolo: on rentre les premiers termes d'une suite et le moteur de recherche renvoie ce qui est connu sur la suite (problèmes où elle apparaît, formule de récurrence, termes connus...)

Merci FrancisSourd pour toutes ces réponses :)

tous tes résultats sont bons et comme tu dis :

Citation:

---

Je suis de moins en moins convaincu sur le fait qu'on puisse trouver une formule générale pour tout k

---

On ne sait jamais ...

Bonjour à tous

Je tombe par hasard sur ce (vieux) sujet et j'avoue que je suis surpris : tous ces problèmes ont été traités depuis fort longtemps et la consultation des sites de LOTOFOOT vous en apprendra beaucoup. C'est même un élément essentiel des logiciels consacrés au LF.

Juste pour information (même si c'est très tardif) pour réduire 4T en N-1 (c'est à dire 3 bons résultats garantis) il suffit de jouer 9 grilles.


A titre d'exemple, la formule donnant pour N triples donnés, le nombre de grilles minimal pour une réduction au rang inférieur étant : 2*N+1.

Le seul problème est que pour certaines combinaisons de triples et de doubles, la meilleure réduction obtenue par les logiciels actuels est loin du théorique. Par exemple, pour un 7 triples, l'idéal serait d'obtenir 146 grilles alors que la meilleure réduction actuelle est de 186...


J'espère vous avoir un peu aidé.

Ce sujet m'interresse également, aurais-tu des liens ou ces methodes sont EXPLIQUEES ?

Quand tu dis :

Citation:

---

Juste pour information (même si c'est très tardif) pour réduire 4T en N-1 (c'est à dire 3 bons résultats garantis) il suffit de jouer 9 grilles.

A titre d'exemple, la formule donnant pour N triples donnés, le nombre de grilles minimal pour une réduction au rang inférieur étant : 2*N+1.

---

La je suis d'accords... Mais plus loin, tu indiques :

Citation:

---

Par exemple, pour un 7 triples, l'idéal serait d'obtenir 146 grilles alors que la meilleure réduction actuelle est de 186...

---

Ta formule ne s'applique plus (2*N + 1) puisque dans ce cas, N=7.

Merci

Citation:

---

Envoyé par FrancisSourd

Je me suis arrêté à k=9 car ce problème demande presque trois heures de calcul. Voici donc les résultats (ils sont compatibles avec les bornes trouvées dans le mail précédent :D ):

Citation:

---

k = 3 Optimal Value = 2 grilles
110 001

k = 4 Optimal Value = 4 grilles
1000 1110 0101 0011

k = 5 Optimal Value = 7 grilles
00100 10010 01110 01001
11001 11101 00111

k = 6 Optimal Value = 12 grilles
001000 010100 110100 100010 111010 101110
001001 101001 110101 010011 000111 011111

k = 7 Optimal Value = 16 grilles
1100000 0011000 1010100 0101100 0110010 1001010
0000110 1111110 0000001 1111001 0110101 1001101
1010011 0101011 1100111 0011111

k = 8 Optimal Value = 32 grilles
10100000 01010000 10001000 01111000 00000100 01100100
11011100 10111100 11000010 11110010 00101010 00011010
10010110 00110110 01001110 11101110 10010001 00110001
01001001 11101001 11000101 11110101 00101101 00011101
00000011 01100011 11011011 10111011 10100111 01010111
10001111 01111111

---

Je suis de moins en moins convaincu sur le fait qu'on puisse trouver une formule générale pour tout k.

---

D'après des recherches de Rowan Davies et Godon F. Royle, on obtient le nombre de grille suivant k (en garantie N-1) :
1 2 2 4 7 12 16 32 62 120 192 380 736

Soit 736 grilles "théorique" avec 13 doubles.

Lien : http://www.cs.cmu.edu/afs/cs/user/ro.../domination.ps

Bonsoir à tous,
ce sujet m'intéresse également.
Je ne me suis pas vraiment plongé dans la théorie, mais j'ai abordé deux aspects pratiques.
1: j ai simplifié en prenant a chaque étape la grille qui simplifiait le plus
2: je teste toutes les possibilités de simplification

Le problème est le temps de calcul... Dès que l'on veut monter dans les 'k', ca prend un temps fou. Mes codes ne sont certainement pas optimisés et si quelqu'un est intéressé pour en discuter, ce sera avec plaisir! :)
je reste attentif à d'autres nouvelles sur la théorie!
Bonne soirée!

Sinon il ya moyen de copier la dessus:

https://market.android.com/details?i...=search_result

Il y a pas mal de choses sur le sujet mais en anglais.

Bonjour,

Je voulais savoir quelqu'un pourrait m'aider

j'aimerai connaitre le nombre de combinaisons possible avec

14 matchs avec 3 choix possible ( 1 /N /2 ) mais avec possibilité de cocher 3 doubles et 4 triples

exemple ticket

match 1 1N2
match 2 1N2
match 3 1N2
match 4 1N2
match 5 1N
match 6 1N
match 7 1N
match 8 1
match 9 1
match 10 1
match 11 1
match 12 1
match 13 1
match 14 1

Si quelqu'un pourrait me dire combien de ticket il faudrait

merci d'avance

Bonjour :coucou:

Citation:

---

j'aimerai connaitre le nombre de combinaisons possible avec 14 matchs avec 3 choix possible ( 1 /N /2 ) mais avec possibilité de cocher 3 doubles et 4 triples

---

7092965880 combinaisons.

Citation:

---

Si quelqu'un pouvait me dire combien de ticket il faudrait

---

648 grilles par combinaison.