JEUX & PROBLÈMES
par Jill-Jênn Vie
Grolopin
et les plans projectifs finis
Un petit problème de combinatoire peut cacher de grandes
théories. Arithmétique des congruences, corps finis, espaces
projectifs (en passant par une conjecture non résolue) , voilà
des notions qu'il vaut mieux connaître pour trouver
l'algorithme qui construise la solution optimale.
P
ro log in (voir page 25) est une
association d 'étudiants de l'EPJTA
(une école d ' ingénieurs en info rmatique), des Éco les norma les s upérieures et de !'École po lytechnique , qui
orga ni se c haqu e ann ée un co nco urs
nati onal d ' info rmatique ouvert à tous
les j eunes de 20 ans et mo ins.
Cette assoc iation a organi sé du rant trois
se ma ines , à la re ntrée 201 2, un mini -
j e u sur le s ite www.grol opin .co m (le
pourquo i de ce nom est la issé en exerc ice au lecteur), dont on peut tirer de
nombreux enseignements.
Les pre mie rs à trouver to us les pin 's
remportaient , entre autres , les éditions
spéci a les Alan Turing et Doctor Who
du jeu Monopo ly.
Le jeu des pin's compatibles
Vo ic i pour commencer la règle du jeu :
Le laborato ire d ' Okabé ne cesse de
compter de nouveaux membres, et
il s'attache à di stribue r à chac un
d 'eux un pin 's, e n res pectant les
contraintes sui vantes :
• Les pin 's sont tous composés d' un
engrenage de M dents dont N percées d ' un tro u.
• La superpos iti o n de de ux pin 's
quelconques do it toujours laisser
apparaître un unique trou.
Les concurre nts devaient afficher
le plu s de pin 's poss ibl e qui respectent la propriété .
Et il fa llai t se dépêcher, car les autres
ré fl échi ssaient au même défi !
Les pin ' s éta ie nt re prése ntés par des
chaînes de M caractères contenant N fo is
le symbole « 0 » correspondant à un trou.
Par exemple , pour tro is « 0 » parm i sept,
le jeu sui vant de trois pin 's est correct
(de ux pin 's que lco nques ont toujours
exactement un O à la même pl ace) :
ooo••••
o••oo••
o••••oo
Mais celui-ci ne l'est pas , car les premier
et dernier pin 'sont deux trous à la même
pos ition :
oo•o•••
o•o•o••
o••o•o•
Tangente Hors-série n°52. Mathématiques & informatique
par Jill-Jênn Vie
Grolopin
et les plans projectifs finis
Un petit problème de combinatoire peut cacher de grandes
théories. Arithmétique des congruences, corps finis, espaces
projectifs (en passant par une conjecture non résolue) , voilà
des notions qu'il vaut mieux connaître pour trouver
l'algorithme qui construise la solution optimale.
P
ro log in (voir page 25) est une
association d 'étudiants de l'EPJTA
(une école d ' ingénieurs en info rmatique), des Éco les norma les s upérieures et de !'École po lytechnique , qui
orga ni se c haqu e ann ée un co nco urs
nati onal d ' info rmatique ouvert à tous
les j eunes de 20 ans et mo ins.
Cette assoc iation a organi sé du rant trois
se ma ines , à la re ntrée 201 2, un mini -
j e u sur le s ite www.grol opin .co m (le
pourquo i de ce nom est la issé en exerc ice au lecteur), dont on peut tirer de
nombreux enseignements.
Les pre mie rs à trouver to us les pin 's
remportaient , entre autres , les éditions
spéci a les Alan Turing et Doctor Who
du jeu Monopo ly.
Le jeu des pin's compatibles
Vo ic i pour commencer la règle du jeu :
Le laborato ire d ' Okabé ne cesse de
compter de nouveaux membres, et
il s'attache à di stribue r à chac un
d 'eux un pin 's, e n res pectant les
contraintes sui vantes :
• Les pin 's sont tous composés d' un
engrenage de M dents dont N percées d ' un tro u.
• La superpos iti o n de de ux pin 's
quelconques do it toujours laisser
apparaître un unique trou.
Les concurre nts devaient afficher
le plu s de pin 's poss ibl e qui respectent la propriété .
Et il fa llai t se dépêcher, car les autres
ré fl échi ssaient au même défi !
Les pin ' s éta ie nt re prése ntés par des
chaînes de M caractères contenant N fo is
le symbole « 0 » correspondant à un trou.
Par exemple , pour tro is « 0 » parm i sept,
le jeu sui vant de trois pin 's est correct
(de ux pin 's que lco nques ont toujours
exactement un O à la même pl ace) :
ooo••••
o••oo••
o••••oo
Mais celui-ci ne l'est pas , car les premier
et dernier pin 'sont deux trous à la même
pos ition :
oo•o•••
o•o•o••
o••o•o•
Tangente Hors-série n°52. Mathématiques & informatique