BxMO 2012
2 participants
Page 1 sur 1
BxMO 2012
http://omb.sbpm.be/bxmo2012/bxmo2012_questions.pdf
Voici est le lien du questionnaire de l' Olympiade du Benelux de cette année qui c' est déroulée ce week-end à La Marlagne, Wépion (près de Namur).
Avis aux amateurs de résoudre les questions!
La première est assez facile (elle a été résolue par deux tiers des participants), la deuxième est assez dure (il faut les bonnes idées...), pour la troisième une bonne figure peut faciliter les choses (notons qu' on n' avait pas le droit d' utiliser des équerres-rapporteur comme à l' Olympiade internationale) et la quatrième n' a pas été résolue entièrement...
Si j' ai le temps, je pourrai poster ma solution de la première question ainsi que le début des questions 2 et 4 (je ne posterai pas tout comme on a eu des solutions-modèles qui sont également en ligne, mais ce n' est pas ce lien).
Notons encore que l' équipe luxembourgeoise a emporté une médaille de bronze et trois mentions honorables .
Les résultats détaillés se trouvent ici: http://omb.sbpm.be/bxmo2012/procla_bxmo.pdf
La prochaine compétition sera donc les finales des OMB mercredi prochain!
Voici est le lien du questionnaire de l' Olympiade du Benelux de cette année qui c' est déroulée ce week-end à La Marlagne, Wépion (près de Namur).
Avis aux amateurs de résoudre les questions!
La première est assez facile (elle a été résolue par deux tiers des participants), la deuxième est assez dure (il faut les bonnes idées...), pour la troisième une bonne figure peut faciliter les choses (notons qu' on n' avait pas le droit d' utiliser des équerres-rapporteur comme à l' Olympiade internationale) et la quatrième n' a pas été résolue entièrement...
Si j' ai le temps, je pourrai poster ma solution de la première question ainsi que le début des questions 2 et 4 (je ne posterai pas tout comme on a eu des solutions-modèles qui sont également en ligne, mais ce n' est pas ce lien).
Notons encore que l' équipe luxembourgeoise a emporté une médaille de bronze et trois mentions honorables .
Les résultats détaillés se trouvent ici: http://omb.sbpm.be/bxmo2012/procla_bxmo.pdf
La prochaine compétition sera donc les finales des OMB mercredi prochain!
carole- Expert
- Messages : 181
Date d'inscription : 11/05/2010
Age : 31
Re: BxMO 2012
Solution du problème 1
Regardons la suite des puissances de 2 modulo 100 jusqu'à ce qu'un terme se répète : `1,2,4,8,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52,4,\ldots`. La séquence `4,8,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52` est donc la période de cette suite. On constate que :
- lorsque le chiffre `2` ou `6` apparaît à la fin d'un terme de cette période, il est toujours précédé d'un chiffre impair (`32,12,92,72,52` et `16,56,96,36,76`) ;
- lorsque le chiffre `4` ou `8` apparaît à la fin de cette période, il est toujours précédé d'un chiffre pair (`04,64,24,84,44` et `08,28,48,68,88`).
Si `a_1` est divisible par `5`, alors `a_1` se termine par le chiffre `0` ou le chiffre `5`, et `a_2` se termine par le chiffre chiffre `0`, puis la suite est constante. Bref, si `a_1` est divisible par `5`, la suite ne comprend aucune puissance de `2`.
Si `a_1` n'est pas divisible par `5`, alors `a_2` se termine par le chiffre `2`, `4`, `6` ou `8`. Mais alors `a_6` vaut alors respectivement `a_2+2+4+8+6=a_2+20`, `a_2+4+8+6+2=a_2+20`, `a_2+6+2+4+8=a_2+20` ou `a_2+8+6+2+4=a_2+20`, et le nombre `a_6=a_2+20` est donc le plus petit nombre entier strictement supérieur à `a_2` se terminant à la fois par :
- le même chiffre que `a_2` ;
- un avant dernier chiffre de même parité que celui de `a_2` .
En fait, la sous-suite `a_{2+4n}` va balayer tous les nombres se terminant à la fois par :
- le même chiffre que `a_2` ;
- un avant dernier chiffre de même parité que celui de `a_2`.
Cette sous-suite va donc balayer l'infinité de puissances de `2` de cette forme-là.
Regardons la suite des puissances de 2 modulo 100 jusqu'à ce qu'un terme se répète : `1,2,4,8,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52,4,\ldots`. La séquence `4,8,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52` est donc la période de cette suite. On constate que :
- lorsque le chiffre `2` ou `6` apparaît à la fin d'un terme de cette période, il est toujours précédé d'un chiffre impair (`32,12,92,72,52` et `16,56,96,36,76`) ;
- lorsque le chiffre `4` ou `8` apparaît à la fin de cette période, il est toujours précédé d'un chiffre pair (`04,64,24,84,44` et `08,28,48,68,88`).
Si `a_1` est divisible par `5`, alors `a_1` se termine par le chiffre `0` ou le chiffre `5`, et `a_2` se termine par le chiffre chiffre `0`, puis la suite est constante. Bref, si `a_1` est divisible par `5`, la suite ne comprend aucune puissance de `2`.
Si `a_1` n'est pas divisible par `5`, alors `a_2` se termine par le chiffre `2`, `4`, `6` ou `8`. Mais alors `a_6` vaut alors respectivement `a_2+2+4+8+6=a_2+20`, `a_2+4+8+6+2=a_2+20`, `a_2+6+2+4+8=a_2+20` ou `a_2+8+6+2+4=a_2+20`, et le nombre `a_6=a_2+20` est donc le plus petit nombre entier strictement supérieur à `a_2` se terminant à la fois par :
- le même chiffre que `a_2` ;
- un avant dernier chiffre de même parité que celui de `a_2` .
En fait, la sous-suite `a_{2+4n}` va balayer tous les nombres se terminant à la fois par :
- le même chiffre que `a_2` ;
- un avant dernier chiffre de même parité que celui de `a_2`.
Cette sous-suite va donc balayer l'infinité de puissances de `2` de cette forme-là.
le_magicien- Pro
- Messages : 56
Date d'inscription : 11/04/2012
Re: BxMO 2012
On aurait pu travailler avec des modulo 20, moi j' ai travaillé modulo 10 pour faire ensuite les mêmes remarques sur les chiffres des dizaines (mais formulé un peu autrement).
Tu aurais pu le formuler un peu plus explicitement. Ce n' est pas très clair qu' il existe toujours une sous-suite comportant des puissances de 2 comme tu ne raisonnes que sur les `a_(2+4n)` . Même si tu dis dans ta dernière phrase que les puissances sont alors du même type que `a_2`... (on peut faire le raisonnement pour tout `a_n`, car si `a_(2+4n)` ne comporte pas de puissance, alors il y a une autre sous-suite avec les puissances ).
Je ne sais pas si ceci était suffisant pour 7 points...
Tu aurais pu le formuler un peu plus explicitement. Ce n' est pas très clair qu' il existe toujours une sous-suite comportant des puissances de 2 comme tu ne raisonnes que sur les `a_(2+4n)` . Même si tu dis dans ta dernière phrase que les puissances sont alors du même type que `a_2`... (on peut faire le raisonnement pour tout `a_n`, car si `a_(2+4n)` ne comporte pas de puissance, alors il y a une autre sous-suite avec les puissances ).
Je ne sais pas si ceci était suffisant pour 7 points...
carole- Expert
- Messages : 181
Date d'inscription : 11/05/2010
Age : 31
Re: BxMO 2012
carole a écrit:On aurait pu travailler avec des modulo 20
C'est vrai que le modulo 20 raccourcirait les choses.
carole a écrit:Tu aurais pu le formuler un peu plus explicitement. Ce n' est pas très clair qu' il existe toujours une sous-suite comportant des puissances de 2 comme tu ne raisonnes que sur les `a_(2+4n)`. Même si tu dis dans ta dernière phrase que les puissances sont alors du même type que `a_2`... (on peut faire le raisonnement pour tout `a_n`, car si `a_(2+4n)` ne comporte pas de puissance, alors il y a une autre sous-suite avec les puissances ).
Je ne sais pas si ceci était suffisant pour 7 points...
Bien vu, Carole.
Avec cette solution, je n'aurais peut-être eu que 2 ou 3 points sur 7, à mon avis. Ce n'est pas juste un manque de clarté, c'est carrément une faute : j'ai fait comme si la parité de l'avant dernier chiffre de `a_2` convenait et ce n'est évidemment pas nécessairement le cas. Pour ma défense, je revenais d'un bar à cocktail avant de rédiger.
On peut adapter la fin de ma preuve en traitant 4 cas selon le dernier chiffre de `a_2`. Si `a_2` ne convient pas et que le dernier chiffre de `a_2` est :
- `2`, alors `a_3` convient ;
- `4`, alors `a_5` convient ;
- `6`, alors `a_3` convient ;
- `8`, alors `a_4` convient.
Bien entendu, il faut aussi expliquer cela avec plus de clarté.
le_magicien- Pro
- Messages : 56
Date d'inscription : 11/04/2012
Re: BxMO 2012
Bon, je le recommence avec le conseil du modulo 20 et sans l'oubli d'initialisation.
********
Voici la suite des puissances de `2` modulo `20` : `1,2,4,8,16,12,4,\ldots`. On constate qu'elle est périodique à partir de son 3ème terme et que sa période est `4,8,16,12`.
********
Si `a_1` est un multiple de `5`, alors `a_1` se termine par le chiffre `0` ou le chiffre `5`, et donc `a_2` se termine par le chiffre `0`. La suite `a_n` est donc constante à partir de son second terme et ne comporte aucune puissance de `2`.
********
Si `a_1` n'est pas un multiple de `5`, alors `a_2` modulo `20` est `2`, `4`, `6`, `8`, `12`, `14`, `16` ou `18`.
Si c'est `4`, `8`, `12` ou `16`, on pose `k=2`.
Si c'est `2` ou `6`, alors remarque que `a_3` modulo `20` est `2+2\equiv 4` ou `6+6\equiv 12` et on pose `k=3`.
Si c'est `18`, alors remarque que `a_4` modulo `20` est `(18+8 )+6\equiv 12` et on pose `k=4`.
Si c'est `14`, alors remarque que `a_5` modulo `20` est `((14+4)+8 )+6\equiv 12` et on pose `k=5`.
Le nombre `a_k` modulo `20` est `4`, `8`, `12` ou `16`, c'est-à-dire un élément de la période de la suite des puissances de `2` modulo `20`. Selon le cas, il vient respectivement : `a_{k+4}=(((a_k+4)+8 )+6)+2`, `a_{k+4}=(((a_k+8 )+6)+2)+4`, `a_{k+4}=(((a_k+2)+4)+8 )+6` ou `a_{k+4}=(((a_k+6)+2)+4)+8`. Bref, dans les quatre cas, `a_{k+4}=a_k+20` et le nombre `a_{k+4}` est le plus petit nombre strictement supérieur à `a_k` qui est de même congruence que `a_k` modulo `20`. En procédant de proche en proche, on obtient une sous-suite `(a_{k+4n})_{n\in\mathbb{N}}=(a_k+20n)_{n\in\mathbb{N}}` de la suite de départ qui balaye l'ensemble des nombres qui sont strictement supérieurs à `a_k` et congrus à `a_k` modulo `20`. Comme il y a une infinité de puissances de `2` qui sont de même congruence modulo `20` que `a_k`, la sous-suite `a_{k+4n}` balaye une infinité de puissances de `2`.
********
Voici la suite des puissances de `2` modulo `20` : `1,2,4,8,16,12,4,\ldots`. On constate qu'elle est périodique à partir de son 3ème terme et que sa période est `4,8,16,12`.
********
Si `a_1` est un multiple de `5`, alors `a_1` se termine par le chiffre `0` ou le chiffre `5`, et donc `a_2` se termine par le chiffre `0`. La suite `a_n` est donc constante à partir de son second terme et ne comporte aucune puissance de `2`.
********
Si `a_1` n'est pas un multiple de `5`, alors `a_2` modulo `20` est `2`, `4`, `6`, `8`, `12`, `14`, `16` ou `18`.
Si c'est `4`, `8`, `12` ou `16`, on pose `k=2`.
Si c'est `2` ou `6`, alors remarque que `a_3` modulo `20` est `2+2\equiv 4` ou `6+6\equiv 12` et on pose `k=3`.
Si c'est `18`, alors remarque que `a_4` modulo `20` est `(18+8 )+6\equiv 12` et on pose `k=4`.
Si c'est `14`, alors remarque que `a_5` modulo `20` est `((14+4)+8 )+6\equiv 12` et on pose `k=5`.
Le nombre `a_k` modulo `20` est `4`, `8`, `12` ou `16`, c'est-à-dire un élément de la période de la suite des puissances de `2` modulo `20`. Selon le cas, il vient respectivement : `a_{k+4}=(((a_k+4)+8 )+6)+2`, `a_{k+4}=(((a_k+8 )+6)+2)+4`, `a_{k+4}=(((a_k+2)+4)+8 )+6` ou `a_{k+4}=(((a_k+6)+2)+4)+8`. Bref, dans les quatre cas, `a_{k+4}=a_k+20` et le nombre `a_{k+4}` est le plus petit nombre strictement supérieur à `a_k` qui est de même congruence que `a_k` modulo `20`. En procédant de proche en proche, on obtient une sous-suite `(a_{k+4n})_{n\in\mathbb{N}}=(a_k+20n)_{n\in\mathbb{N}}` de la suite de départ qui balaye l'ensemble des nombres qui sont strictement supérieurs à `a_k` et congrus à `a_k` modulo `20`. Comme il y a une infinité de puissances de `2` qui sont de même congruence modulo `20` que `a_k`, la sous-suite `a_{k+4n}` balaye une infinité de puissances de `2`.
le_magicien- Pro
- Messages : 56
Date d'inscription : 11/04/2012
Question 4a)
Voilà, c' est déjà beaucoup mieux!
Il ne faut peut-être pas faire les maths si on ne peut plus se concentrer... cela n' aboutit à pas trop de choses
Ma solution était plus longue et un peu moins élégante...
Question 4(a)
(je mets ma solution telle quelle du premier point, cela valait 1 point, j' ai un peu corrigé la grammaire et mis des informations supplémentaires entre crochets[])
`f(n)=n-3
Afin de replacer les personnes, il nous faut connaître n-3 réponses.
Si 2 personnes n' étaient pas été désignées "voisin" d' aucune personne interrogée, on ne pourrait pas les placer. Donc il nous faut au moins au plus une personne qui n' a pas été désignée "voisin", c' est-à-dire qu' on a le droit d' interroger toutes les personnes sauf ses voisins [et la personne elle-même] (donc n-3 personnes au plus).
Montrons qu' il faut au moins interroger [n-3 personnes]:
Supposons qu' on ne demande qu' à n-2 personnes. Il se pourrait qu' on ait choisies ces personnes auparavant toutes assises les unes à côté des autres et il resteraient 2 personnes non désignées "voisin", donc il faut au moins interroger n-3 personnes dans un groupe de n personnes.
`f(n)=n-3`
Il ne faut peut-être pas faire les maths si on ne peut plus se concentrer... cela n' aboutit à pas trop de choses
Ma solution était plus longue et un peu moins élégante...
Question 4(a)
(je mets ma solution telle quelle du premier point, cela valait 1 point, j' ai un peu corrigé la grammaire et mis des informations supplémentaires entre crochets[])
`f(n)=n-3
Afin de replacer les personnes, il nous faut connaître n-3 réponses.
Si 2 personnes n' étaient pas été désignées "voisin" d' aucune personne interrogée, on ne pourrait pas les placer. Donc il nous faut au moins au plus une personne qui n' a pas été désignée "voisin", c' est-à-dire qu' on a le droit d' interroger toutes les personnes sauf ses voisins [et la personne elle-même] (donc n-3 personnes au plus).
Montrons qu' il faut au moins interroger [n-3 personnes]:
Supposons qu' on ne demande qu' à n-2 personnes. Il se pourrait qu' on ait choisies ces personnes auparavant toutes assises les unes à côté des autres et il resteraient 2 personnes non désignées "voisin", donc il faut au moins interroger n-3 personnes dans un groupe de n personnes.
`f(n)=n-3`
carole- Expert
- Messages : 181
Date d'inscription : 11/05/2010
Age : 31
Re: BxMO 2012
carole a écrit:Voilà, c' est déjà beaucoup mieux!
Il ne faut peut-être pas faire les maths si on ne peut plus se concentrer... cela n' aboutit à pas trop de choses
Je ne peux pas m'en empêcher, de faire des maths.
carole a écrit:
Question 4(a)
Supposons qu' on ne demande qu' à n-2 personnes. Il se pourrait qu' on ait choisies ces personnes auparavant toutes assises les unes à côté des autres et il resteraient 2 personnes non désignées "voisin", donc il faut au moins interroger n-3 personnes dans un groupe de n personnes.
Euh... tu n'aurais pas fait `(n-3)-1=n-2` ? Mais bon, on comprend ce que tu veux dire, donc cela va.
le_magicien- Pro
- Messages : 56
Date d'inscription : 11/04/2012
Re: BxMO 2012
Ah oui, j' ai vraiment mal calculé...
J' essaie de ne plus me tromper sur ce genre de calculs. Maintenant j' ai honte de moi-même
Bien sur cela devrait être `n-3-1=n-4`
J' essaie de ne plus me tromper sur ce genre de calculs. Maintenant j' ai honte de moi-même
Bien sur cela devrait être `n-3-1=n-4`
carole- Expert
- Messages : 181
Date d'inscription : 11/05/2010
Age : 31
Re: BxMO 2012
C'est juste un détail de distraction, ce n'est pas grave. J'ai déjà fait la même erreur, c'est une erreur classique. C'est parce que dans ce genre de problème, on a tendance à ne pas réfléchir en terme algébrique `n-3-1=n-4` car on est concentré sur le reste du raisonnement (il n'est pas nécessaire de savoir si c'est `n-2` ou `n-4` pour raisonner correctement ; on écrit le `n-4` uniquement pour le lecteur-correcteur et on est distrait sur sa valeur, alors on écrit `n-2`).
le_magicien- Pro
- Messages : 56
Date d'inscription : 11/04/2012
Re: BxMO 2012
Solution du problème (4b)
C'est un problème que j'ai beaucoup apprécié. La solution que je propose n'a pas besoin de traiter un par un les différents cas modulo 3.
Notons `P` l'ensemble des personnes qui étaient assises autour de la table. Après qu'un nombre quelconque de questions (éventuellement aucune) aient été posées, on peut définir le sous-ensemble `R` de `P\times P` de la façon suivante : `(r,s)\in R` si et seulement si les deux personnes `r` et `s` étaient voisines autour de la table et au moins l'une d'entre elles a déjà été interrogée. Cela étant, on appelle chaîne de longueur `k` tout sous-ensemble `C` de `P` possédant exactement `k` éléments et dont les éléments peuvent être renommés `r_1,\ldots,r_k` de façon à vérifier ceci : `(r_1,r_2),(r_2,r_3),\ldots,(r_{k-1},r_k)\in R`. Tout élément de `P` fait évidemment parti d'une et d'une seule chaîne maximale (une chaîne maximale est une chaîne qui ne peut pas être agrandie pour former une chaîne plus grande). On qualifie d'isolée toute personne dont la chaîne maximale est composée d'une seule personne. Si `\{r_1,\ldots,r_k\}` est une chaîne maximale de longueur `k\geq2` pour laquelle `(r_1,r_2),(r_2,r_3),\ldots,(r_{k-1},r_k)\in R`, alors on qualifie de terminale chacune des `2` personnes `r_1` et `r_k` et de centrale chacune des `k-2` personnes `r_2,r_2,\ldots,r_{k-1}`.
À quelle condition possède-t-on assez d'informations pour asseoir tout le monde autour de la table ? On peut le faire si il n'y a plus qu'une seule chaîne maximale (cette chaîne peut alors être fermée sans soucis). On peut également le faire si il ne reste plus que deux chaînes maximales dont l'une est constituée d'une personne isolée (en effet, on peut asseoir autour de la table les personnes de la plus longue chaîne en respectant les informations dont on dispose et il ne reste alors qu'une seule place pour la personne isolée). Par contre, s'il reste au moins deux chaînes maximales de longueur au moins deux, alors on ne peut pas encore asseoir les personnes autour de la table, notamment faute de savoir dans quel sens (sens des aiguilles d'une montre ou sens inverse des aiguilles d'une montre) les orienter l'une par rapport à l'autre. De plus, s'il reste au moins trois chaînes maximales, alors on ne peut évidemment pas encore asseoir les personnes autour de la table (il est impossible qu'il n'y ait que trois chaînes maximales et qu'elles soient toutes les trois de longueur `1` car `n>3`). En résumé, la condition d'arrêt est : une seule chaîne maximale ou deux chaînes maximales dont une de longueur `1`.
Notons `a` le nombre de personnes isolées et `b` le nombre de chaînes maximales de longueur au moins deux. Bien entendu, `a` et `b` varient à chaque question posée. Au départ, `a=n` et `b=0`, donc `a+b=n`. À la fin, d'après la condition d'arrêt, il faut que `(a,b)=(0,1)` ou `(a,b)=(1,1)`, donc `a+b=1` ou `a+b=2`. Examinons de quelles façons possibles en fonction de la nature (isolée, terminale ou centrale) de la personne à qui on pose la question.
Si on pose une question à une personne centrale, ni `a` ni `b` ne varie et la somme `a+b` ne varie pas. On ne va de toute façon jamais interroger des personnes centrales. Ce serait complètement inutile et une question perdue pour rien.
Si on pose une question à une personne terminale et qu'il y a au moins encore deux chaînes maximales (dans le cas contraire, on peut déjà asseoir tout le monde), alors la personne interrogée désignera toujours un voisin faisant parti de sa propre chaîne maximale et un autre voisin en dehors de sa propre chaîne maximale. Si ce second voisin est une personne isolée, alors `a` diminue de `1` et `b` ne varie pas. Si ce second voisin est une personne terminale, alors `a` ne varie pas et `b` diminue de `1`. Bien entendu, ce second voisin ne peut pas être une personne centrale. Dans tous les cas, `a+b` diminue de `1`.
Si on pose une question à une personne isolée et qu'il reste aux moins trois chaînes maximales (dans le cas contraire, on peut déjà asseoir tout le monde car on a deux chaînes maximales dont une de longueur `1`), alors la personne interrogée peut désigner comme voisins deux personnes isolées, une personne isolée et une personne terminale, ou deux personnes terminales. S'il s'agit de deux personnes isolées, alors `a` diminue de `3` et `b` augmente de 1. S'il s'agit d'une personne isolée et d'une personne terminale, alors `a` diminue de `2` et `b` na varie pas. S'il s'agit de deux personnes terminales (elles ne peuvent pas être de la même chaîne maximale car on a supposé qu'il y a au moins trois chaînes maximales), alors `a` ne varie pas et `b` diminue de `2`. Dans tous les cas, `a+b` diminue de `2`.
Supposons avoir assis tout le monde. Notons `x` le nombre de questions ayant été posées à une personne isolée (isolée au moment où sa question lui a été posée) et `y` le nombre de questions ayant été posées à une personne terminale (terminale au moment où sa question lui a été posée) . On cherche à trouver la plus petite valeur possible de `x+y` sachant notamment que `2x+y=n-1` ou `2x+y=n-2`. On cherche donc à maximiser `x`. Le nombre de personnes isolées n'augmente jamais lorsqu'on pose des questions. Le nombre maximum de personnes isolées qu'on est certain de pouvoir interroger est évidemment le plus petit entier `m` supérieur ou égal à `n/3` puisque on ne peut pas contrôler avec certitudes les réponses à l'avance et qu'il se peut très bien que, tant qu'il reste des personnes isolées, chaque personne isolée interrogée désigne une autre personne isolée comme premier voisin et une autre personne isolée comme second voisin. La réponse du problème est donc le nombre `x+y=n-1-m` ou le nombre `x+y=n-2-m`.
On est en effet certain de pouvoir s'en sortir avec `n-1-m` questions. Si `n>4`, il suffit d'interroger d'abord des personnes isolées jusqu'à ce qu'il n'y en ait plus (il y en aura au moins `m` qui seront interrogées dans le pire des cas) puis d'interroger des personnes terminales. Si `n=4`, on n'a pas le choix : on interroge une personne isolée et on peut asseoir tout le monde (et `n-1-m=4-1-2=1` donc tout va bien).
La dernière question qui se pose est de savoir si on peut à coup sûr parvenir à interroger `m` personnes isolées en épargnant une personne isolée (afin d'obtenir `a=1` et `b=1` en `n-2-m` questions). Ce serait en effet l'unique façon de faire à coup sûr mieux qu'avec `n-1-m` questions. La réponse est négative car on ne contrôle pas sa chance. En effet, si `b\geq 2` après un nombre quelconque de questions, on prend le risque de ne jamais pouvoir revenir à `b=1` (les personnes terminales pouvant désigner un voisin isolé et les personnes isolées pouvant désigné des voisins isolés dans la limite du stock disponible) avant de passer irrémédiablement à `a=0`. Or, ne pas prendre le risque d'atteindre `b\geq 2`, cela revient à n'interroger que des personnes terminales après avoir interrogé la personne première (qui est nécessairement isolée). Donc, ne pas prendre ce risque revient à devoir poser en tout au moins `1+((n-3)-1)=n-3` questions. C'est au moins autant que `n-1-m` (et plus que `n-2-m`) car `m>1` car `n>3`.
La réponse est donc `g(n)=n-1-m` où `m` est le plus petit entier supérieur ou égal à `n/3`.
C'est un problème que j'ai beaucoup apprécié. La solution que je propose n'a pas besoin de traiter un par un les différents cas modulo 3.
Notons `P` l'ensemble des personnes qui étaient assises autour de la table. Après qu'un nombre quelconque de questions (éventuellement aucune) aient été posées, on peut définir le sous-ensemble `R` de `P\times P` de la façon suivante : `(r,s)\in R` si et seulement si les deux personnes `r` et `s` étaient voisines autour de la table et au moins l'une d'entre elles a déjà été interrogée. Cela étant, on appelle chaîne de longueur `k` tout sous-ensemble `C` de `P` possédant exactement `k` éléments et dont les éléments peuvent être renommés `r_1,\ldots,r_k` de façon à vérifier ceci : `(r_1,r_2),(r_2,r_3),\ldots,(r_{k-1},r_k)\in R`. Tout élément de `P` fait évidemment parti d'une et d'une seule chaîne maximale (une chaîne maximale est une chaîne qui ne peut pas être agrandie pour former une chaîne plus grande). On qualifie d'isolée toute personne dont la chaîne maximale est composée d'une seule personne. Si `\{r_1,\ldots,r_k\}` est une chaîne maximale de longueur `k\geq2` pour laquelle `(r_1,r_2),(r_2,r_3),\ldots,(r_{k-1},r_k)\in R`, alors on qualifie de terminale chacune des `2` personnes `r_1` et `r_k` et de centrale chacune des `k-2` personnes `r_2,r_2,\ldots,r_{k-1}`.
À quelle condition possède-t-on assez d'informations pour asseoir tout le monde autour de la table ? On peut le faire si il n'y a plus qu'une seule chaîne maximale (cette chaîne peut alors être fermée sans soucis). On peut également le faire si il ne reste plus que deux chaînes maximales dont l'une est constituée d'une personne isolée (en effet, on peut asseoir autour de la table les personnes de la plus longue chaîne en respectant les informations dont on dispose et il ne reste alors qu'une seule place pour la personne isolée). Par contre, s'il reste au moins deux chaînes maximales de longueur au moins deux, alors on ne peut pas encore asseoir les personnes autour de la table, notamment faute de savoir dans quel sens (sens des aiguilles d'une montre ou sens inverse des aiguilles d'une montre) les orienter l'une par rapport à l'autre. De plus, s'il reste au moins trois chaînes maximales, alors on ne peut évidemment pas encore asseoir les personnes autour de la table (il est impossible qu'il n'y ait que trois chaînes maximales et qu'elles soient toutes les trois de longueur `1` car `n>3`). En résumé, la condition d'arrêt est : une seule chaîne maximale ou deux chaînes maximales dont une de longueur `1`.
Notons `a` le nombre de personnes isolées et `b` le nombre de chaînes maximales de longueur au moins deux. Bien entendu, `a` et `b` varient à chaque question posée. Au départ, `a=n` et `b=0`, donc `a+b=n`. À la fin, d'après la condition d'arrêt, il faut que `(a,b)=(0,1)` ou `(a,b)=(1,1)`, donc `a+b=1` ou `a+b=2`. Examinons de quelles façons possibles en fonction de la nature (isolée, terminale ou centrale) de la personne à qui on pose la question.
Si on pose une question à une personne centrale, ni `a` ni `b` ne varie et la somme `a+b` ne varie pas. On ne va de toute façon jamais interroger des personnes centrales. Ce serait complètement inutile et une question perdue pour rien.
Si on pose une question à une personne terminale et qu'il y a au moins encore deux chaînes maximales (dans le cas contraire, on peut déjà asseoir tout le monde), alors la personne interrogée désignera toujours un voisin faisant parti de sa propre chaîne maximale et un autre voisin en dehors de sa propre chaîne maximale. Si ce second voisin est une personne isolée, alors `a` diminue de `1` et `b` ne varie pas. Si ce second voisin est une personne terminale, alors `a` ne varie pas et `b` diminue de `1`. Bien entendu, ce second voisin ne peut pas être une personne centrale. Dans tous les cas, `a+b` diminue de `1`.
Si on pose une question à une personne isolée et qu'il reste aux moins trois chaînes maximales (dans le cas contraire, on peut déjà asseoir tout le monde car on a deux chaînes maximales dont une de longueur `1`), alors la personne interrogée peut désigner comme voisins deux personnes isolées, une personne isolée et une personne terminale, ou deux personnes terminales. S'il s'agit de deux personnes isolées, alors `a` diminue de `3` et `b` augmente de 1. S'il s'agit d'une personne isolée et d'une personne terminale, alors `a` diminue de `2` et `b` na varie pas. S'il s'agit de deux personnes terminales (elles ne peuvent pas être de la même chaîne maximale car on a supposé qu'il y a au moins trois chaînes maximales), alors `a` ne varie pas et `b` diminue de `2`. Dans tous les cas, `a+b` diminue de `2`.
Supposons avoir assis tout le monde. Notons `x` le nombre de questions ayant été posées à une personne isolée (isolée au moment où sa question lui a été posée) et `y` le nombre de questions ayant été posées à une personne terminale (terminale au moment où sa question lui a été posée) . On cherche à trouver la plus petite valeur possible de `x+y` sachant notamment que `2x+y=n-1` ou `2x+y=n-2`. On cherche donc à maximiser `x`. Le nombre de personnes isolées n'augmente jamais lorsqu'on pose des questions. Le nombre maximum de personnes isolées qu'on est certain de pouvoir interroger est évidemment le plus petit entier `m` supérieur ou égal à `n/3` puisque on ne peut pas contrôler avec certitudes les réponses à l'avance et qu'il se peut très bien que, tant qu'il reste des personnes isolées, chaque personne isolée interrogée désigne une autre personne isolée comme premier voisin et une autre personne isolée comme second voisin. La réponse du problème est donc le nombre `x+y=n-1-m` ou le nombre `x+y=n-2-m`.
On est en effet certain de pouvoir s'en sortir avec `n-1-m` questions. Si `n>4`, il suffit d'interroger d'abord des personnes isolées jusqu'à ce qu'il n'y en ait plus (il y en aura au moins `m` qui seront interrogées dans le pire des cas) puis d'interroger des personnes terminales. Si `n=4`, on n'a pas le choix : on interroge une personne isolée et on peut asseoir tout le monde (et `n-1-m=4-1-2=1` donc tout va bien).
La dernière question qui se pose est de savoir si on peut à coup sûr parvenir à interroger `m` personnes isolées en épargnant une personne isolée (afin d'obtenir `a=1` et `b=1` en `n-2-m` questions). Ce serait en effet l'unique façon de faire à coup sûr mieux qu'avec `n-1-m` questions. La réponse est négative car on ne contrôle pas sa chance. En effet, si `b\geq 2` après un nombre quelconque de questions, on prend le risque de ne jamais pouvoir revenir à `b=1` (les personnes terminales pouvant désigner un voisin isolé et les personnes isolées pouvant désigné des voisins isolés dans la limite du stock disponible) avant de passer irrémédiablement à `a=0`. Or, ne pas prendre le risque d'atteindre `b\geq 2`, cela revient à n'interroger que des personnes terminales après avoir interrogé la personne première (qui est nécessairement isolée). Donc, ne pas prendre ce risque revient à devoir poser en tout au moins `1+((n-3)-1)=n-3` questions. C'est au moins autant que `n-1-m` (et plus que `n-2-m`) car `m>1` car `n>3`.
La réponse est donc `g(n)=n-1-m` où `m` est le plus petit entier supérieur ou égal à `n/3`.
le_magicien- Pro
- Messages : 56
Date d'inscription : 11/04/2012
Re: BxMO 2012
Solution du problème 2
Des égalités `a^2012+2012b=2012c+d^2012` et `2012a+b^2012=c^2012+2012d`, on tire `(c-b)=\frac{a^2012-d^2012}{2012}=\frac{(a-d)(\sum_{i=0}^2011a^id^{2011-i})}{2012}=\frac{\frac{c^2012-b^2012}{2012}\sum_{i=0}^2011a^id^{2011-i}}{2012}=(c-b)\frac{\sum_{i=0}^2011c^ib^{2011-i}}{2012}\frac{\sum_{i=0}^2011a^id^{2011-i}}{2012}`, puis `1=\frac{\sum_{i=0}^2011c^ib^{2011-i}}{2012}\frac{\sum_{i=0}^2011a^id^{2011-i}}{2012}` si `b\ne c`.
Mais, comme la moyenne arithmétique de nombres strictement positifs est supérieure ou égale à la moyenne géométrique de ces nombres et que l'égalité n'a lieu que si les nombres sont deux à deux égaux, il vient : `\frac{\sum_{i=0}^2011c^ib^{2011-i}}{2012}\frac{\sum_{i=0}^2011a^id^{2011-i}}{2012}>(\Pi_{i=0}^2011c^ib^{2011-i})^{1/2012}(\Pi_{i=0}^2011a^id^{2011-i})^{1/2012}=(c^{{2011*2012}/2}b^{{2011*2012}/2})^{1/2012}(a^{{2011*2012}/2}d^{{2011*2012}/2})^{1/2012}=(abcd)^{2011/2}=1^{2011/2}=1` si `b\ne c` grâce à l'égalité `abcd=1`. On a une contradiction (`1>1`) sauf si `b=c`. Mais si `b=c`, alors d'après les équations de départ, on tire `a=d` et `a^2b^2=1`. Les seules solutions du problème sont donc les quadruplets `(a,1/a,1/a,a)` où `a` est un nombre réel strictement positif (on vérifie immédiatement que tout marche bien pour ces quadruplets-là).
Des égalités `a^2012+2012b=2012c+d^2012` et `2012a+b^2012=c^2012+2012d`, on tire `(c-b)=\frac{a^2012-d^2012}{2012}=\frac{(a-d)(\sum_{i=0}^2011a^id^{2011-i})}{2012}=\frac{\frac{c^2012-b^2012}{2012}\sum_{i=0}^2011a^id^{2011-i}}{2012}=(c-b)\frac{\sum_{i=0}^2011c^ib^{2011-i}}{2012}\frac{\sum_{i=0}^2011a^id^{2011-i}}{2012}`, puis `1=\frac{\sum_{i=0}^2011c^ib^{2011-i}}{2012}\frac{\sum_{i=0}^2011a^id^{2011-i}}{2012}` si `b\ne c`.
Mais, comme la moyenne arithmétique de nombres strictement positifs est supérieure ou égale à la moyenne géométrique de ces nombres et que l'égalité n'a lieu que si les nombres sont deux à deux égaux, il vient : `\frac{\sum_{i=0}^2011c^ib^{2011-i}}{2012}\frac{\sum_{i=0}^2011a^id^{2011-i}}{2012}>(\Pi_{i=0}^2011c^ib^{2011-i})^{1/2012}(\Pi_{i=0}^2011a^id^{2011-i})^{1/2012}=(c^{{2011*2012}/2}b^{{2011*2012}/2})^{1/2012}(a^{{2011*2012}/2}d^{{2011*2012}/2})^{1/2012}=(abcd)^{2011/2}=1^{2011/2}=1` si `b\ne c` grâce à l'égalité `abcd=1`. On a une contradiction (`1>1`) sauf si `b=c`. Mais si `b=c`, alors d'après les équations de départ, on tire `a=d` et `a^2b^2=1`. Les seules solutions du problème sont donc les quadruplets `(a,1/a,1/a,a)` où `a` est un nombre réel strictement positif (on vérifie immédiatement que tout marche bien pour ces quadruplets-là).
le_magicien- Pro
- Messages : 56
Date d'inscription : 11/04/2012
Re: BxMO 2012
Solution du problème 3
Soit `a` la médiatrice du segment `[BP]` et `b` la tangente au cercle `\Gamma` passant par le point `B`. On ma montrer que `S_b(S_a([BC]))=[RQ]` où `S_x` désigne la symétrie orthogonale d'axe `x`, ce qui prouvera que la longueur du segment `[RS]` vaut la longueur du segment `[BC]` et est donc indépendante du choix du point `P` à l'intérieur du triangle `ABC`.
Il est immédiat que `S_b(S_a(B))=S_b(P)=R`.
Il ne reste donc qu'à prouver que `S_b(S_a(C))=Q`. Notons `D` le point `S_a(C)`, `E` le symétrique du point `P` par rapport au point `M` et `F` un point de `b` différent de `B`. On a `|BQ|=|BE|=|CP|=|BD|` (`*_1`) (`*_2`)(`*_3`) et `|FBQ|=|DBF|` (angles orientés) (`*_4`), ce qui suffit à conclure que `S_b(D)=Q` et donc que `S_b(S_a(C))=Q`.
*****************************************************************************
*****************************************************************************
*****************************************************************************
(Sous le tapis )
(`*_1`) Le triangle `BEQ` est isocèle. En effet, l'angle `QEB` a le même supplément (angle `PQB`) que l'angle `BQE`. En effet, le quadrilatère `ABQP` est inscriptible, les angles `PAB` et `CPM` sont égaux par hypothèse et les angles `PEB` et `EPC=MPC` sont symétrie par rapport à `M`.
(`*_2`) La symétrie centrale de centre `M` envoie le segment `[BE]` sur le segment `[CP]`.
(`*_3`) La symétrie orthogonale d'axe `a` envoie le segment `[PC]` sur le segment `[BD]`.
(`*_4`) Soient `O` le centre du cercle `\Gamma` et `G` le milieu du segment `[DE]` dans le triangle isocèle `BDE`. On a `2|GBF|=2|PBO|=2(180°-|BOP|)/2=180°-|BOP|=180°-2|BAP|=180°-2|QEB|=|EBQ|` et on en déduit que `|FBQ|=|FBE|+|EBQ|=|FBE|+2|GBF|=|GBE|+|GBF|=|DBG|+|GBF|=|DBF|`.
Soit `a` la médiatrice du segment `[BP]` et `b` la tangente au cercle `\Gamma` passant par le point `B`. On ma montrer que `S_b(S_a([BC]))=[RQ]` où `S_x` désigne la symétrie orthogonale d'axe `x`, ce qui prouvera que la longueur du segment `[RS]` vaut la longueur du segment `[BC]` et est donc indépendante du choix du point `P` à l'intérieur du triangle `ABC`.
Il est immédiat que `S_b(S_a(B))=S_b(P)=R`.
Il ne reste donc qu'à prouver que `S_b(S_a(C))=Q`. Notons `D` le point `S_a(C)`, `E` le symétrique du point `P` par rapport au point `M` et `F` un point de `b` différent de `B`. On a `|BQ|=|BE|=|CP|=|BD|` (`*_1`) (`*_2`)(`*_3`) et `|FBQ|=|DBF|` (angles orientés) (`*_4`), ce qui suffit à conclure que `S_b(D)=Q` et donc que `S_b(S_a(C))=Q`.
*****************************************************************************
*****************************************************************************
*****************************************************************************
(Sous le tapis )
(`*_1`) Le triangle `BEQ` est isocèle. En effet, l'angle `QEB` a le même supplément (angle `PQB`) que l'angle `BQE`. En effet, le quadrilatère `ABQP` est inscriptible, les angles `PAB` et `CPM` sont égaux par hypothèse et les angles `PEB` et `EPC=MPC` sont symétrie par rapport à `M`.
(`*_2`) La symétrie centrale de centre `M` envoie le segment `[BE]` sur le segment `[CP]`.
(`*_3`) La symétrie orthogonale d'axe `a` envoie le segment `[PC]` sur le segment `[BD]`.
(`*_4`) Soient `O` le centre du cercle `\Gamma` et `G` le milieu du segment `[DE]` dans le triangle isocèle `BDE`. On a `2|GBF|=2|PBO|=2(180°-|BOP|)/2=180°-|BOP|=180°-2|BAP|=180°-2|QEB|=|EBQ|` et on en déduit que `|FBQ|=|FBE|+|EBQ|=|FBE|+2|GBF|=|GBE|+|GBF|=|DBG|+|GBF|=|DBF|`.
le_magicien- Pro
- Messages : 56
Date d'inscription : 11/04/2012
Cours sur le calcul modulaire
Voici un lien vers le serveur de maths où il y a un cours sur le calcul modulaire (on l' a utilisé pour résoudre le premier problème.)
http://www.lmrl.lu/mathematiques/Club_Maths/Arithmetique_modulaire.pdf
Un exemple:
`8-=3 (mod 5)` car 8 et 3 ont le même reste dans la division euclidienne par 5
Le calcul modulaire est assez utile pour les problèmes d' arithmétique.
http://www.lmrl.lu/mathematiques/Club_Maths/Arithmetique_modulaire.pdf
Un exemple:
`8-=3 (mod 5)` car 8 et 3 ont le même reste dans la division euclidienne par 5
Le calcul modulaire est assez utile pour les problèmes d' arithmétique.
carole- Expert
- Messages : 181
Date d'inscription : 11/05/2010
Age : 31
Sujets similaires
» BxMO avril 2013
» THIRD BENELUX MATHEMATICAL OLYMPIAD : BxMO 2011
» SECOND BENELUX MATHEMATICAL OLYMPIAD : BxMO 2010
» FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009
» OMB- Eliminatoires 2012
» THIRD BENELUX MATHEMATICAL OLYMPIAD : BxMO 2011
» SECOND BENELUX MATHEMATICAL OLYMPIAD : BxMO 2010
» FIRST BENELUX MATHEMATICAL OLYMPIAD : BxMO 2009
» OMB- Eliminatoires 2012
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
|
|