Les coupl es (N ; M) po ur lesquels il fal -
la it réso udre l' é ni g me é taie nt (3 ; 7) ,
(4 : 13), (6 ; 3 1 ) , (9 ; 73) pui s fin a leme nt (28; 757) (notez qu 'on a to uj o urs
M = N
2 - N + 1).
Po ur (N; M) = (3; 7) , le nombre max imal de pin 's constructibles est 7, dont voici
un je u admi ss ibl e :
o•o•o••
•o•oo••
o••o•o•
•oo••o•
oo••••o
••oo••o
••••ooo
L'avantage de ce problè me est que c hac un , pe u impo rte so n bagage mathématique, po uva it soume ttre des pin 's
e t co ntribue r à dévo il e r des pi xe ls de
la carte.
m est un majorant du nombre de pin's
Le problè me consiste donc à réali ser un
tableau de M = N
2 - N + 1 colo nnes e t
le plus de lignes possible , tel que chaque
ligne comporte N trous et que deux lignes
quelconques aie nt exacte me nt un trou
à la mê me positio n .
On peut comme ncer par remarque r qu ' il
est impossible d 'obtenir plus de M pin 's.
En effet, si o n di sposa it d ' un te l jeu , o n
aura it stri cte me nt plu s de MN trou s à
ré partir parmi les M co lo nnes . D 'après
le « principe des ti ro irs » , il ex isterait une
colonne comportant au moins N + 1 trous.
Considérons alo rs les N + 1 pin 's ayant
un tro u da ns cette co lo nne, il reste pour
chac un d 'entre e ux N - 1 tro us à ré partir parmi les M - 1 = N
2 - N co lo nnes
res ta ntes , so it en to ut
( N + l )( N - 1) = N
2 - 1 trou s parmi
N
2 - N co lo nnes . Une co lo nne co m -
po rtera au moin s de ux trous : les de ux
pin 's ainsi mi s e n év ide nce auro nt de ux
trous aux mêmes positions, ce qui constitue un e cont radi cti o n.
CHANGER LE MONDE
L' intuitio n qui se cache derriè re la soluti o n est de voir les pin 's co mme des
droites du pl an e t les trous co mme les
po ints par lesque ls e ll es passent : de ux
droites que lco nqu es sont séca ntes o u
parallè les. Ain si, ajo ute r un po int « à
l' infini » po ur chaque cl asse de droites
parallè les pe rme t de garantir un po int
d ' inte rsec ti o n po ur c haqu e pa ire de
d ro ites , do nc un unique trou e n commun po ur c haque paire de pin 's. C ' est
la base de ce qu ' o n appe ll e la géométri e
projecti ve.
Po ur construire un je u de pin 's max imal, o n di sting ue ra de ux cas :
• N = p + 1 o ù p est un no mbre pre mie r,
• N = / + 1 po ur p pre mie r e t k > 1.
la résolution pour n = 3
Comme nçons par le cas de l' e xe mpl e ,
so itN= 3.
Cons idé rons to utes les droites à coeffi -
Code Pvthon résolvant le cas
N = o+ 1 où onremier
N ; 3
p ; N -1
Np ; range(p)
points; [(x, y) fo r x in Np for y in Np] \
+ [('infini', k) fo r k in Np) \
+ [('infi ni', 'infi ni'))
for a in Np :
for b in Np:
pins ; "" # droi te y ; ax + b
for x, y in points:
pins+ ; 'o' if (x ;; 'infini' and y ; ; a) \
print(pins)
fo r a in Np:
or (x J; 'infini' and y;; (a * x + b) % p) else ' '
pins ; "" # verticale x ; c
for x, y in points :
pins+; 'o' if ((x, y);; ('infini ', 'infini') or x ;; a) else ''
print(pins)
pins ; "" # infini
for x, y in points :
pins+; 'o' if x ;; 'infini' else ''
print(pins)
Hors-série n° 52. Mathématiques & informatique Tangente
la it réso udre l' é ni g me é taie nt (3 ; 7) ,
(4 : 13), (6 ; 3 1 ) , (9 ; 73) pui s fin a leme nt (28; 757) (notez qu 'on a to uj o urs
M = N
2 - N + 1).
Po ur (N; M) = (3; 7) , le nombre max imal de pin 's constructibles est 7, dont voici
un je u admi ss ibl e :
o•o•o••
•o•oo••
o••o•o•
•oo••o•
oo••••o
••oo••o
••••ooo
L'avantage de ce problè me est que c hac un , pe u impo rte so n bagage mathématique, po uva it soume ttre des pin 's
e t co ntribue r à dévo il e r des pi xe ls de
la carte.
m est un majorant du nombre de pin's
Le problè me consiste donc à réali ser un
tableau de M = N
2 - N + 1 colo nnes e t
le plus de lignes possible , tel que chaque
ligne comporte N trous et que deux lignes
quelconques aie nt exacte me nt un trou
à la mê me positio n .
On peut comme ncer par remarque r qu ' il
est impossible d 'obtenir plus de M pin 's.
En effet, si o n di sposa it d ' un te l jeu , o n
aura it stri cte me nt plu s de MN trou s à
ré partir parmi les M co lo nnes . D 'après
le « principe des ti ro irs » , il ex isterait une
colonne comportant au moins N + 1 trous.
Considérons alo rs les N + 1 pin 's ayant
un tro u da ns cette co lo nne, il reste pour
chac un d 'entre e ux N - 1 tro us à ré partir parmi les M - 1 = N
2 - N co lo nnes
res ta ntes , so it en to ut
( N + l )( N - 1) = N
2 - 1 trou s parmi
N
2 - N co lo nnes . Une co lo nne co m -
po rtera au moin s de ux trous : les de ux
pin 's ainsi mi s e n év ide nce auro nt de ux
trous aux mêmes positions, ce qui constitue un e cont radi cti o n.
CHANGER LE MONDE
L' intuitio n qui se cache derriè re la soluti o n est de voir les pin 's co mme des
droites du pl an e t les trous co mme les
po ints par lesque ls e ll es passent : de ux
droites que lco nqu es sont séca ntes o u
parallè les. Ain si, ajo ute r un po int « à
l' infini » po ur chaque cl asse de droites
parallè les pe rme t de garantir un po int
d ' inte rsec ti o n po ur c haqu e pa ire de
d ro ites , do nc un unique trou e n commun po ur c haque paire de pin 's. C ' est
la base de ce qu ' o n appe ll e la géométri e
projecti ve.
Po ur construire un je u de pin 's max imal, o n di sting ue ra de ux cas :
• N = p + 1 o ù p est un no mbre pre mie r,
• N = / + 1 po ur p pre mie r e t k > 1.
la résolution pour n = 3
Comme nçons par le cas de l' e xe mpl e ,
so itN= 3.
Cons idé rons to utes les droites à coeffi -
Code Pvthon résolvant le cas
N = o+ 1 où onremier
N ; 3
p ; N -1
Np ; range(p)
points; [(x, y) fo r x in Np for y in Np] \
+ [('infini', k) fo r k in Np) \
+ [('infi ni', 'infi ni'))
for a in Np :
for b in Np:
pins ; "" # droi te y ; ax + b
for x, y in points:
pins+ ; 'o' if (x ;; 'infini' and y ; ; a) \
print(pins)
fo r a in Np:
or (x J; 'infini' and y;; (a * x + b) % p) else ' '
pins ; "" # verticale x ; c
for x, y in points :
pins+; 'o' if ((x, y);; ('infini ', 'infini') or x ;; a) else ''
print(pins)
pins ; "" # infini
for x, y in points :
pins+; 'o' if x ;; 'infini' else ''
print(pins)
Hors-série n° 52. Mathématiques & informatique Tangente