RSS Feed
Precedenta
Următoarea

Problema 289

23 Aprilie 2010

Cicli Eulerieni


Fie C(x,y) un cerc care trece prin punctele (x, y), (x, y+1), (x+1, y) și (x+1, y+1).

Pentru numerele întregi pozitive m și n, fie E(m,n) o configurație care constă din cercurile m·n:
{ C(x,y): 0 ≤ x < m, 0 ≤ y < n, x și y sunt numere întregi }

Un ciclu Eulerian pe E(m,n) e o cale închisă care trece prin fiecare arc exact 1 dată.
Sunt multe astfel de căi posibile pe E(m,n), dar suntem interesați doar de cele care nu se interesectează cu ele însele: O astfel de cale doar se atinge în anumite puncte, dar nu se interesectează niciodată.

Imaginea de mai jos ilustrează E(3,3) și un exemplu al unui ciclu Eulerian care nu se interesectează.

Fie L(m,n) numărul de cicli Eulerieni pe E(m,n) care nu se intersectează.
De exemplu, L(1,2) = 2, L(2,2) = 37 si L(3,3) = 104290.

Găsește restul împărțirii lui L(6,10) la 1010.


>> Vezi problema originală <<