In cate moduri poate fi partitionata multimea {1,2,...,2003} in 3 submultimi nevide a.i. nici una nu contine vre-o pereche de numere consecutive?

[Citat] In cate moduri poate fi partitionata multimea {1,2,...,2003} in 3 submultimi nevide a.i. nici una nu contine doua numere consecutive?

Facem rost de trei sertare numerotate cu 0,1,2. (Sunt programator.)

Luam bila 1. In cate moduri putem sa-i alegem sertarul? In 3 moduri. Bun.
Luam bila 2. In cate moduri putem sa-i alegem sertarul? In 2 moduri, trebuie sa evitam sertarul in care am pus bila 1. Bun.
Luam bila 3. In cate moduri putem sa-i alegem sertarul? In 2 moduri, trebuie sa evitam sertarul in care am pus bila 2. Bun.

Facem asa mai departe pana la capat.
Se intrezareste solutia, numarul cazurilor este

Daca problema are origine din fizica sau programare ne putem opri aici.
In matematica mai trebuie sa demonstram cele afirmate. Pentru a face riguroasa argumentarea putem proceda asa.

(1)
Fie N numar natural nenul.
Atunci urmatoarea propozitie P(N) este adevarata:

P(N):
"Fie a in multimea {0,1,2}. Numarul de aplicatii
f : {1,2,...,N} -> {0,1,2}
-- care il trimit pe 1 in a, f(1) = a,
-- si pentru care oricum luam n natural intre 1 si N-1 avem f(n) diferit de f(n+1)
este egal cu 2 la puterea (N-1)."

Demonstram inductiv propozitia P(N):
Pentru N=1 am terminat repede.
Trecerea de la N la N+1, adica demonstrarea implicatiei P(N) => P(N+1), este simpla. Anume. Plecam cu F, o functie ca cea de care se leaga in P(N+1).

Ne uitam la F(2), diferit de a, pe care putem sa-l luam in doua moduri,
apoi la f functia de la [1,N] la {0,1,2}, f(k) = F(k+1).
Cred ca de aici nu mai sunt probleme.


(2) Aceeasi solutie, dar usurata prin inventare de structura.
Consideram multimea {0,1,2} de mai sus a fi multimea claselor de resturi modulo 3.
Atunci putem sa-i asociem unei functii f de tipul celei de mai sus tupletul:

( f(1); f(2)-f(1), f(3)-f(2), ... , f(N)-f(N-1) ) .

Este clar ca f determina unic un astfel de element din multimea tupletelor cu prima componenta in {0,1,2}, cu celelalte in {1,2} .
Reciproc, deoarece putem aduna telescopic componentele, un astfel de tuplet determina f-ul. Trebuie sa mai numaram acum elementele din produsul cartezian
{0,1,2} x {1,2} x ... x {1,2}

Tema de casa:
In cate moduri putem pune bilele/numerele
1, 2, ... , 2012
in trei sertare, astfel incat nici unul din sertare nu contine trei bile/numere consecutive ?

Generalizarile sunt desigur bine venite.
(Romania are traditie in combinatorica. Atat ne-au tot sucit...)

[Citat] Facem rost de trei sertare numerotate cu 0,1,2. (Sunt programator.) Luam bila 1. In cate moduri putem sa-i alegem sertarul? In 3 moduri. Bun. Luam bila 2. In cate moduri putem sa-i alegem sertarul? In 2 moduri, trebuie sa evitam sertarul in care am pus bila 1. Bun. Luam bila 3. In cate moduri putem sa-i alegem sertarul? In 2 moduri, trebuie sa evitam sertarul in care am pus bila 2. Bun. Facem asa mai departe pana la capat.

Hai s? nu mergem pân? la cap?t. S? presupunem c? avem doar bilele 1,2,3 de a?ezat.
Conform ra?ionamentului de mai sus, exist? 6 moduri de a?ezare a bilelor. Bun.
Dar nu cumva singura parti?ie în submul?imi nevide este

?

Desigur, sunt 3! permutari ale celor 3 submultimi.

[Citat] Hai s? nu mergem pân? la cap?t. S? presupunem c? avem doar bilele 1,2,3 de a?ezat. Conform ra?ionamentului de mai sus, exist? 6 moduri de a?ezare a bilelor. Bun. Dar nu cumva singura parti?ie în submul?imi nevide este ?

Da, multumesc, am probleme mereu cu multimile vide (si conditiile care ma fac sa incep o miniproblema in problema).
De asemenea am considerat ca cele trei multimi vin ordonate. (Eu le-am pus etichete distincte.) Daca nu se considera asa, trebuie sa impartim la 3! numarul 3.2.2. ... .2 (normand ca 1 sa fie in primul sertar, 2 in al doilea si al treilea este cel nenumerotat).

Atunci trebuie sa mai scadem 1, singura constelatie in care a treia multime devine vida, cea cu
(primul sertar) 1,3,5,...
(al doilea sertar) 2,4,6,...
(al treilea sertar) (este gol).

Dam de

posibilitati de partitionare (cum ni s-a cerut) ale multimii {1,2...,N}, N natural > 1 .

Multumesc!

As dori o mica indicatie pentru "tema de casa". O sa expun si o parte din ideea mea (nu sunt multumit cu ea):
Luam pentru inceput cazul in care nu exista numere consecutive in submultimi.
Apoi permitem unei perechi sa fie in aceeasi submultime (la fel de bine le putem permite si celorlalte n-2 perechi (fiecare pe rand) ). Si continuam rationamentul.

Imi cer scuze pentru insistenta, dar doresc doar o sugestie pentru cum sa incep problema.

[Citat] In cate moduri poate fi partitionata multimea {1,2,...,2003} in 3 submultimi nevide a.i. nici una nu contine vreo pereche de numere consecutive?

O solutie alternativa:

O sa incerc sa scriu cum m-am gandit ca se poate ataca...

[Citat] Tema de casa: In cate moduri putem pune bilele/numerele 1, 2, ... , N in trei sertare, astfel incat nici unul din sertare nu contine trei bile/numere consecutive ?

O posibilitate este cea de a ataca direct "cazul N", folosind principiul includerii si excluderii.

Cealalta posibilitate se incadreaza in tema "transferului de informatie" de la un N la urmatorul, cred ca am invatat principiul de la domnul Tomescu cateva decenii in urma. Nu exista un nume pentru acest principiu, dar daca ar trebui sa ii gasesc un nume probabil ca "transfer de informatie" este numele potrivit.

In problema vrem sa obtinem o relatie de "recursiune de la N la (N+1)".
Vrem sa "transmitem informatia" de la partitiile "valide" ale lui {1,2,...,N} la cele ale lui {1,2,3,...,N+1}, validitatea fiind proprietatea de a nu avea trei numere consecutive in nici o parte a partitiei.

De aceea este natural sa definim:

A(N; k) este multimea partitiilor

{S,T,U} ale multimii X(N) in partile (vide sau nevide) S,T,U (a caror ordine NU conteaza) in care
- S contine 1
- T contine cel mai mic element care nu este in S, daca acesta exista, altfel T=U=multimea vida.
- U este a treia multime din partitie.
(...am ordonat deci partitia in ordinea in care vin elementele minime pe care le contin...)
in care nici in S, nici in T, nici in U nu apar trei elemente consecutive
si in care in S exact primele k elemente sunt consecutive, k fiind 1 sau 2.

De exemplu, in cazul in care scriem S,T,U cu elementele in ordine,
S = { 1,4,7, ...}
T = { 2,3,9, ...}
U = { 5,6,21,27,...}
partitia (S,T,U) este in A(N; 1) .

La trecerea de la N la N+1, asociem unei partitii (S,T,U) a lui {1,...,N} partitia corespunzatoare (S',T',U') a lui {2,...,(N+1)}, aplicand operatia n->(n+1) pe elemente, in exemplul de mai sus obtinand
S' = { 2,5,8, ...}
T' = { 3,4,10, ...}
U' = { 6,7,22,28, ...}
si incercam sa il donam pe 1 uneia sau alteia dintre multimi.

Daca il donam lui S', ceea ce putem de data asta, dam de un element din A(N+1,2).
Daca il donam lui T' sau U', ceea ce putem intotdeauna, dam de un element din A(N+1,1).

Sa notam cu a(N,k) numarul de elemente din A(N,k), N natural>2, k in {1,2} .
Obtinem recursiunile:

a(N+1,1) = 2 a(N,1) + 2 a(N,2)
a(N+1,2) = 1 a(N,1) + 0 a(N,2)

Calculam a(3,1). Elementele lui A(3,1) sunt
( {1}, {2,3}, {} )
( {1,3}, {2}, {} )
( {1}, {2}, {3} )
deci a(3,1) = 3.
Mai calculam a(3,2). Elementele lui A(3,2) sunt... doar unul,
( {1,2}, {3}, {} )
deci a(3,2) = 1.

Cu formula de recursiune de mai sus dam de
a(4,1) = 8
a(4,2) = 3.
Pe noi ne intereseaza de fapt suma
a(N) = a(N,1) + a(N,2)
pentru fiecare N. Destul de repede ajungem la relatia de recurenta

a(N+2) = 2a(N+1) + 2a(N) , N>2 .

Exista desigur si o formula explicita pentru a(N).
Trec la formatul in care pot scrie normal formulele.

Valorile sunt asadar pentru primele cateva cazuri:

sage: F.<u> = QuadraticField(3)
sage: F
Number Field in u with defining polynomial x^2 - 3
sage: u
u
sage: u^2
3
sage: for k in [3..10]:
....: print "a(%d) = %d" % ( k, ( (1+u)^(k-2) * (9+5*u) + (1-u)^(k-2) * (9-5*u) ) / 12 )
....:
a(3) = 4
a(4) = 11
a(5) = 30
a(6) = 82
a(7) = 224
a(8) = 612
a(9) = 1672
a(10) = 4568

Multumesc. O sa prezint putin mai detaliat ideea mea, pentru a vedea daca se poate valorifica.
Pornim de la partitiile in care nu exista nicio pereche de numere consecutive in aceeasi submultime. (adica 3.2.2.2...)

Dar daca permitem unei perechi sa fie in aceeasi submultime?
Sa punem de exemplu numerele 1 si 2 impreuna. Atunci o sa avem 3.1.2.2.... .
Tot atatea partitii erau si daca puneam alta pereche de numere consecutive impreuna, deci o sa fie

.


Trecem la cazul in care punem impreuna doua perechi.
Sa punem de exemplu 1 cu 2 si 3 cu 4. Atunci o sa avem 3.1.2.1.2.2.2... .

Ma opresc aici, asteptand o confirmare sau o infirmare a ideii.

EDIT: Am corectat.