Mulţimi legate

La etapa judeţeană a olimpiadei de matematică din acest an ( 2006 ), una din problemele propuse la clasa a VII-a definea mulţimile legate ca fiind mulţimi de 4 numere naturale cu proprietatea că pentru orice x din mulţime cel puţin unul dintre numerele x-1, x+1 este în M. Vom încerca în această notă să definim mulţimile legate de ordin k eliminând condiţia ca mulţimea să conţină patru elemente şi apoi vom încerca să identificăm o metodă de calcul a diferitelor tipuri de submulţimi legate ale mulţimii

A_n={1, 2, 3, ….., n}.

Definiţia 1: O mulţime M de numere naturale se numeşte simplu legată dacă este mulţimea vidă sau dacă pentru orice x din mulţime cel puţin unul dintre numerele x-1, x+1 este în M.

Observaţia 1: O mulţime nevidă de numere naturale simplu legată este formată din “blocuri” de numere consecutive de lungime cel puţin 2.

Definiţia 2: Fie . O mulţime M de numere naturale se numeşte legată de ordin k dacă este mulţimea vidă sau dacă pentru orice x din M, cel puţin una din mulţimile {x-i, x-i+1, …., x-i+k} cu este inclusă în M.

Observaţia 2: O mulţime nevidă de numere naturale legată de ordin k este formată din “blocuri” de numere consecutive de lungime cel puţin k+1. Dacă k=1 se obţine definiţia mulţimilor simplu legate. Mulţimile legate de ordin 2 le vom numi şi mulţimi dublu legate.

Fie acum mulţimea A_n={1, 2, 3, ….., n}. Ne punem problema să determinăm numărul submulţimilor lui A_n simplu legate şi respectiv dublu legate .

Vom considera în acest sens mulţimea n-uplelor în care pentru orice ; un astfel de n-uplu îl vom numi şi n-cuvânt. Vom asocia de asemenea fiecărei submulţimi X a lui A_n un n-cuvânt format în felul următor: Dacă atunci a_i=1 altfel a_i=0.

Definiţia 3: Se numeşte n-cuvânt legat de ordin k un n-cuvânt asociat unei mulţimi legate de ordin k.

Vom nota cu , numărul n-cuvintelor legate de ordin 1 pe care le vom numi şi

n-cuvinte simplu legate.

Propoziţia 1: Cu notaţiile anterioare avem următoarea relaţie de recurenţă:

pentru orice n > 4.

Demonstraţie: Într-adevăr, numărul n-cuvintelor simplu legate care încep cu 0 este . Numărul n-cuvintelor simplu legate care încep cu 1 îl vom calcula astfel: Vom observa pentru început că un astfel de n-cuvânt are în mod obligatoriu în poziţia a doua elementul 1. Dacă la primele două poziţii adăugăm toate (n-2)-cuvintele simplu legate care se formează cu restul poziţiilor dintr-un astfel de cuvânt se obţin n-cuvinte simplu legate. Deasemenea n-cuvinte simplu legate mai putem obţine şi dacă în poziţiile 3 şi 4 punem 1 şi respectiv 0 iar în rest (n-4)-cuvinte simplu legate. Prin urmare numărul n-cuvintelor simplu legate care încep cu 1 este: şi deci relaţia de recurenţă este acum justificată.

Folosind un program simplu de calculator creat în limbajul Pascal am completat (prin identificare si numarare a submulţimilor legate fără a folosi recurenţa anterioară) următorul tabel:

k
0	1
1	1
2	2
3	4
4	7
5	12
6	21
7	37
8	65
9	114

Bineînţeles că având calculate valorile cu , se pot calcula folosind relaţia de recurenţă dedusă şi celelalte date din tabel dar din curiozitate am continuat să calculez cu calculatorul şi pentru a verifica astfel relaţia de recurenţă dedusă.

Vom nota cu , numărul n-cuvintelor legate de ordin 2 pe care le vom numi şi n-cuvinte dublu legate.

Propoziţia 2: Cu notaţiile anterioare avem următoarea relaţie de recurenţă:

pentru .

Demonstraţie: Într-adevăr, numărul n-cuvintelor dublu legate care încep cu 0 este . Numărul n-cuvintelor dublu legate care încep cu 1 îl calculăm astfel: Un astfel de n-cuvânt are în mod obligatoriu în poziţiile 2 şi 3 cifra 1. Dacă completăm aceste cuvinte cu (n-3)-cuvinte dublu legate se obţin n-cuvinte dublu legate. Deasemenea n-cuvinte dublu legate se mai pot obţine şi dacă completăm poziţiile 4 şi 5 cu cifrele 1 şi respectiv 0 şi în rest (n-5)-cuvinte dublu legate, sau dacă poziţiile 4, 5 şi 6 se completează cu cifrele 1, 1 şi respectiv 0 iar în rest cu (n-6)-cuvinte dublu legate. Prin urmare numărul n-cuvintelor dublu legate care încep cu 1 este şi deci relaţia din propoziţia 2 este acum justificată.

Folosind calculatorul am reuşit să completez (prin identificarea şi numărarea submulţimilor legate) următorul tabel:

k
0	1
1	1
2	1
3	2
4	4
5	7
6	11
7	17
8	27
9	44
10	72

Observaţie: Relaţiile de recurenţă deduse în cele două propoziţii permit determinarea unei formule de calcul pentru , respectiv .

Se observă că numerele obţinute cu ajutorul calculatorului verifică relaţia de recurenţă.

Folosind relaţiile de recurenţă deduse şi un program corespunzător pe calculator putem calcula şi pentru valori suficient de mari ale lui n . ■

Stăniloiu Nicolae, profesor, Bocşa