Générer un nombre aléatoire à partir d'une liste de nombres aléatoires
Générer un nombre aléatoire à partir d'une liste de nombres aléatoires
Bonjour,
nous disposons de $ x_1, x_2, ..., x_n $ nombres entiers naturels choisis aléatoirement, ordonnés, et inférieurs à $ N $.
Ces nombres sont demandés à des candidats, et le candidat $ i $ a accès aux nombres $ x_1, x_2, ..., x_{i-1} $ et choisit le nombre $ x_i $
Je cherche un procédé qui permet de construire un nombre $ y $ à partir des $ x_i $ mais qui soit difficilement manipulable par un candidat $ i $
Je m'explique : disons que l'on fasse la somme $ y = x_1 + x_2 + ... + x_n $
Alors si le candidat $n$ a envie de manipuler le résultat $ y $, il choisir $ x_n = y - x_1 - x_2 - ... - x_{n-1} $
Si on fait le produit, c'est déjà plus difficile de manipuler et choisir $y$ : il faut que le produit des nombres $ x_1, x_2, ..., x_{n-1} $ divise $y$, ce qui limite les choix du candidat $n$
Voyez-vous une quelconque opération déterministe qui me permet de garantir le minimum de choix (voire idéalement "1 choix") pour le candidat $n$ ?
Je ne sais si j'ai été suffisamment clair, je reste à votre disposition, n'hésitez pas à poser vos questions.
Je vous remercie d'avance.
nous disposons de $ x_1, x_2, ..., x_n $ nombres entiers naturels choisis aléatoirement, ordonnés, et inférieurs à $ N $.
Ces nombres sont demandés à des candidats, et le candidat $ i $ a accès aux nombres $ x_1, x_2, ..., x_{i-1} $ et choisit le nombre $ x_i $
Je cherche un procédé qui permet de construire un nombre $ y $ à partir des $ x_i $ mais qui soit difficilement manipulable par un candidat $ i $
Je m'explique : disons que l'on fasse la somme $ y = x_1 + x_2 + ... + x_n $
Alors si le candidat $n$ a envie de manipuler le résultat $ y $, il choisir $ x_n = y - x_1 - x_2 - ... - x_{n-1} $
Si on fait le produit, c'est déjà plus difficile de manipuler et choisir $y$ : il faut que le produit des nombres $ x_1, x_2, ..., x_{n-1} $ divise $y$, ce qui limite les choix du candidat $n$
Voyez-vous une quelconque opération déterministe qui me permet de garantir le minimum de choix (voire idéalement "1 choix") pour le candidat $n$ ?
Je ne sais si j'ai été suffisamment clair, je reste à votre disposition, n'hésitez pas à poser vos questions.
Je vous remercie d'avance.
Re: Générer un nombre aléatoire à partir d'une liste de nombres aléatoires
Juste une association d'idée avec l'OEIS
Si cette encyclopédie répertorie des séquences "concrètes", elle peut donner des idées
Si cette encyclopédie répertorie des séquences "concrètes", elle peut donner des idées
отец (un autre père ENSICAENnais) сынок (& fils PCSI▸PC▸PC* 2020-23 à B.Pascal (63) ➠ EC Lille) и Дух мира (& esprit de 🕊)
Re: Générer un nombre aléatoire à partir d'une liste de nombres aléatoires
Elle ne contient pas toutes les listes possibles malheureusement, par exemple 1,2,3,6,11,23,47,106,235,875 n'y est
en plus, idéalement je préfère disposer d'un résultat fiable, qui ne peut être modifié dans le temps, je ne pense pas que je puisse dépasser le stade d'opérations simples : +, -, //, %
Re: Générer un nombre aléatoire à partir d'une liste de nombres aléatoires
C’est dans le cadre d’un TIPE ?
« Occupez-vous d’abord des choses qui sont à portée de main. Rangez votre chambre avant de sauver le monde. Ensuite, sauvez le monde. » (Ron Padgett, dans Comment devenir parfait)
Re: Générer un nombre aléatoire à partir d'une liste de nombres aléatoires
Bonsoir,
Je suis navré mais j'ai beaucoup de questions.
0) Qu'entends-tu par "ordonnés" ? $x_1 < x_2 < ... < x_n$ ou simplement que c'est une suite ?
1) Je n'ai pas bien compris comment sont choisis les $x_i$. S'ils sont choisis indépendamment selon une loi uniforme sur les entiers entre $1$ et $N$, la connaissance des entiers $x_1$,...,$x_{i-1}$ par le candidat $i$ n'influe pas sur le "choix" de $x_i$ ? En quoi cette information est-elle alors utile ? Sinon, comment ta suite d'entiers est-elle construite ?
2) Je ne comprends pas ce que signifie "difficilement manipulable".
3) Tel que tu exprimes la suite de ton message, j'ai l'impression que ton nombre $y$ est fonction de $x_1$, ..., $x_n$ mais aussi que le candidat $n$ pose $x_n$ connaissant $y$... Comment et à quel moment définis-tu $y$ ?
4) Si le candidat $n$ dispose d'une fonction $f$ et choisit $x_n$ tel que $f(x_1,...x_n)=y$ alors le "choix" de $x_n$ n'est certainement pas "aléatoire" (surtout que tu sembles désirer qu'il n'y ait qu'un seul "choix" à la fin)
Bonne soirée
Je suis navré mais j'ai beaucoup de questions.
0) Qu'entends-tu par "ordonnés" ? $x_1 < x_2 < ... < x_n$ ou simplement que c'est une suite ?
1) Je n'ai pas bien compris comment sont choisis les $x_i$. S'ils sont choisis indépendamment selon une loi uniforme sur les entiers entre $1$ et $N$, la connaissance des entiers $x_1$,...,$x_{i-1}$ par le candidat $i$ n'influe pas sur le "choix" de $x_i$ ? En quoi cette information est-elle alors utile ? Sinon, comment ta suite d'entiers est-elle construite ?
2) Je ne comprends pas ce que signifie "difficilement manipulable".
3) Tel que tu exprimes la suite de ton message, j'ai l'impression que ton nombre $y$ est fonction de $x_1$, ..., $x_n$ mais aussi que le candidat $n$ pose $x_n$ connaissant $y$... Comment et à quel moment définis-tu $y$ ?
4) Si le candidat $n$ dispose d'une fonction $f$ et choisit $x_n$ tel que $f(x_1,...x_n)=y$ alors le "choix" de $x_n$ n'est certainement pas "aléatoire" (surtout que tu sembles désirer qu'il n'y ait qu'un seul "choix" à la fin)
Bonne soirée
Re: Générer un nombre aléatoire à partir d'une liste de nombres aléatoires
Pas sûr d'avoir compris la question.
Par contre, il y a déjà plein de PRNG (sans aller chercher du MersenneTwister) qui tournent autour de ça, et ils pourraient être source d'inspiration.
Par contre, il y a déjà plein de PRNG (sans aller chercher du MersenneTwister) qui tournent autour de ça, et ils pourraient être source d'inspiration.
Masséna (PC*) -- X15 -- Spatial.
Re: Générer un nombre aléatoire à partir d'une liste de nombres aléatoires
Utiliser x_1 pour brouiller x_0. On obtient y_1.
Utiliser x_2 pour brouiller y_1. On obtient y_2.
...
Utiliser x_n pour brouiller y_{n-1}. On obtient y_n.
On affecte y_n à x_{n+1}
Une méthode de brouillage pourrait être de calculer k_i = x_i modulo N (valeur à choisir) et de faire k_i permutations circulaires des chiffres de y_{i-1}. La valeur de N pourrait même être une fonction de i.
Bon courage. Pierre
Utiliser x_2 pour brouiller y_1. On obtient y_2.
...
Utiliser x_n pour brouiller y_{n-1}. On obtient y_n.
On affecte y_n à x_{n+1}
Une méthode de brouillage pourrait être de calculer k_i = x_i modulo N (valeur à choisir) et de faire k_i permutations circulaires des chiffres de y_{i-1}. La valeur de N pourrait même être une fonction de i.
Bon courage. Pierre