Page 44 - MATINF Nr. 7

˘
MATEMATICA PENTRU PROGRAMATORI SI
,
PROGRAMARE PENTRU MATEMATICIENI

Multimi legate 1
,

Nicolae St˘aniloiu 2

La etapa judet , ean˘a a olimpiadei de matematic˘a din anul 2006, una din problemele propuse la
clasa a VII-a definea mult , imile legate ca fiind mult , imile M de 4 numere naturale cu proprietatea
c˘a pentru orice x din mult , ime cel put , in unul dintre numerele x − 1, x + 1 este ˆın M. Vom
ˆıncerca ˆın aceast˘a lucrare s˘a definim mult , imile legate de ordin k eliminˆand condit , ia ca mult , imea
s˘a cont , in˘a patru elemente s , i apoi vom ˆıncerca s˘a identific˘am o metod˘a de calcul a diferitelor
tipuri de submult , imi legate ale mult , imii A n = {1, 2, ..., n}.
Definit , ia 1. O mult , ime M de numere naturale se numes , te simplu legat˘a dac˘a este mult , imea
vid˘a sau dac˘a pentru orice x din mult , ime cel put , in unul dintre numerele x − 1, x + 1 este ˆın M.
Observat ,ia 1. O mult , ime nevid˘a de numere naturale simplu legat˘a este format˘a din ,,blocuri”
de numere consecutive de lungime cel put , in 2.
Definit , ia 2. Fie k ≥ 1. O mult , ime M de numere naturale se numes , te legat˘a de ordin k
dac˘a este mult , imea vid˘a sau dac˘a pentru orice x din M, cel put , in una din mult , imile {x − i, x −
i + 1, . . . , x − i + k} cu 0 ≤ i ≤ k, este inclus˘a ˆın M.

Observat ,ia 2. O mult , ime nevid˘a de numere naturalelegat˘a de ordin k este format˘a din ,,blocuri”
de numere consecutive de lungime cel put , in k + 1. Dac˘a k = 1 se obt , ine definit , ia mult , imilor
simplu legate. Mult , imile legate de ordin 2 le vom numi s , i mult , imi dublu legate.

k
Fie acum mult , imea A n = {1, 2, ..., n}. Pentru k ∈ N, k < n, vom nota cu X submult , imile
n
ˆ
1
lui A n legate de ordin k. In particular X reprezint˘a submult , imile lui A n simplu legate iar X 2
n n
reprezint˘a submult , imile lui A n dublu legate.
Cu aceste notat , ii sunt evidente urm˘atoarele relat , ii:
1
2
1
1
2
2
2
1. |X n n−1 | = 2, |X | = 1, |X | = 1, |X | = 2, |X | = 1, |X | = 1, |X | = 1, |X | = 2;
1
1
3
2
2
0
0
0
0
∗
0
k
2. Dac˘a k, k , n ∈ N cu k < k , k < n, k < n atunci X k 0 ⊂ X ;
n n
k
∗
k
3. Dac˘a n, m, k ∈ N cu k < n < m atunci X ⊂ X .
m
n
Ne punem mai departe, problema determin˘arii num˘arului submult , imilor lui A n simplu legate,
apoi dublu legate s , i ˆın final a submult , imilor legate de ordin k cu k < n.
Vom considera ˆın acest sens mult , imea: C n = {(a 1 , a 2 , . . . , a n )|a i ∈ B, ∀i = 1 . . . n} unde
B = {0, 1}. Un element al mult , imii C n ˆıl vom numi s , i n-cuvˆant. Vom asocia de asemenea fiec˘arei
submult , imi X a lui A n un n-cuvˆant (a 1 , a 2 , . . . , a n ), format ˆın felul urm˘ator: Dac˘a i ∈ Xatunci
a i = 1, altfel a i = 0.
1
Acest articol a fost comunicat la Simpozionul Judet , ean de Matematic˘a ,,Marinescu-Ghemeci Octavian”,
Edit , ia I, Potcoava, 8 mai 2021.
2
Profesor, Bocs , a, staniloiun@yahoo.com
44