63

˘rare Tutorial: Probleme de numa

Probleme de num˘arare

1

Dou˘ a principii de num˘ arare de baz˘ a • Principiul adun˘ arii: Dac˘a A ¸si B sunt mult¸imi finite disjuncte, atunci | A ∪ B |=| A | + | B | . • Principiul multiplic˘ arii: Dac˘a A ¸si B sunt mult¸imi finite, atunci | A × B |=| A | · | B | .

1.1

Intreb˘ ari:

(1) In cˆate moduri se pot acorda calificativele A, B, C, D, E la o grupa de 20 de student¸i? (2) Cˆate numere de telefon de 7 cifre se pot forma dac˘a: (i) Exist˘a numere de telefon care ˆıncep cu 0; (ii) Nu exist˘a numere de telefon care ˆıncep cu 0; (iii) Toate numerele de telefon ˆıncep cu 0. (3) G˘asit¸i num˘arul divizorilor lui 26 × 58 . Dac˘a num˘arul natural n are descompunerea ˆın factori primi distinct¸i n = pa11 · . . . · par r , determinat¸i num˘arul divizorilor lui n. Caracterizat¸i numerele naturale cu exact 2, 3, 4, 5 sau 6 divizori. Problema 1.1. Intr-o colonie format˘a din 60000 de bacterii intr˘a un virus. In primul minut el omoar˘a o bacterie, apoi se divizeaz˘a ˆın 2 viru¸si ¸si concomitent fiecare dintre bacteriile r˘amase se divizeaz˘a de asemenea ˆın alte dou˘a. In minutul urm˘ator cei doi viru¸si omoar˘a dou˘a bacterii, apoi cei doi viru¸si ¸si toate bacteriile r˘amase din nou se divizeaz˘a ¸si a¸sa mai departe. Colonia de bacterii va tr˘ai nelimitat sau va fi omorˆat˘a dup˘a un timp?

˘ ¸si Informatica ˘ Facultatea de Matematica

1

Centrul de pregatire pentru copiii performant ¸i

2

Principiul includerii ¸si excluderii • Verificat¸i pe un desen c˘a dac˘a A1 ¸si A2 sunt dou˘a mult¸imi, atunci | A1 ∪ A2 |=| A1 | + | A2 | − | A1 ∩ A2 | . • Verificat¸i pe un desen c˘a dac˘a A1 , A2 ¸si A3 sunt trei mult¸imi, atunci | A1 ∪ A2 ∪ A3 |=| A1 | + | A2 + | A3 | − − | A 1 ∩ A2 | − | A 2 ∩ A3 | − | A 1 ∩ A3 | + | A 1 ∩ A2 ∩ A3 | . • Deducet¸i, prin induct¸ie dup˘a n, |

n [

Ai |=

i=1

2.1

n X i=1

| Ai | −

X

| Ai ∩ Aj | + . . . + (−1)n |

i<j

n \

Ai | .

i=1

Aplicat¸ii

Problema 2.1. Toate numerele de telefon din ora¸sul Denic˘aieri au cˆate ¸sapte cifre ¸si ˆıncep cu 56 sau se termin˘a cu 7. Cˆate numere de telefon exist˘a ˆın ora¸sul Denic˘aieri ¸stiind c˘a celelalte cifre pot fi oricare din cifrele 0, 1, . . . , 9? Problema 2.2. (a) Cˆate numere ˆıntregi ˆıntre 1 ¸si 2006 nu se divid cu niciunul din numerele 2, 3 ¸si 5? (b) Cˆate numere ˆıntregi din mult¸imea {1, 2, . . . , 360} au cel put¸in un divizor prim comun cu 360? (c) Cˆate numere din mult¸imea {1, 2, . . . , 2005} sunt relativ prime cu 2006? (d) Fie n natural, n ≥ 2. Calculat¸i ϕ(n) (ϕ este indicatorul lui Euler). Problema 2.3 (Num˘ arul funct¸iilor surjective). Num˘arul funct¸iilor surjective definite pe o mult¸ime cu n elemente ¸si cu valori ˆıntr-o mult¸ime cu m elemente (n ≥ m) este       m m m n n n m sn,m = m − (m − 1) + (m − 2) − . . . + (−1) 1n . 1 2 m−1 In particular, pentru m = n se obt¸ine identitatea:       n n n n n n n n! = n − (n − 1) + (n − 2) − . . . + (−1) 1n . 1 2 n−1

˘ ¸si Informatica ˘ Facultatea de Matematica

2

˘rare Tutorial: Probleme de numa

Indicat¸ie. Fie Y = {y1 , . . . , ym } ¸si Ai = {f : X → Y | yi 6∈ Imf }. Rezult˘a c˘a sn,m = mn − |A1 ∪ . . . ∪ Am |. Pentru 1 ≤ k ≤ m − 1 ¸si 1 ≤ i1 < . . . < ik ≤ m, n |Ai1 ∩. . . Aik | = (m−k) . Pe de alt˘a parte, mult¸imea de indici i1 < . . . < ik se
m poate alege ˆın k moduri. Acum aplic˘am Principiul includerii ¸si excluderii.  Problema 2.4. n persoane sunt a¸sezate pe n scaune. La un moment dat se cere tuturor persoanelor sa se ridice ¸si sa-¸si schimbe scaunul. In cˆate moduri se pot rea¸seza cele n persoane? Indicat¸ie. Problema se poate reformula astfel: cˆate permut˘ari de grad n (= biject¸ii : {1, 2, . . . , n} → {1, 2, . . . , n}) f˘ar˘a puncte fixe exist˘a? Dac˘a Ai = {σ ∈ Sn | σ(i) = i}, pentru 1 ≤ i ≤ n ¸si Dn este mult¸imea permut˘arilor f˘ar˘a puncte fixe, atunci n [ Dn = S n − Ai . i=1

Apoi se aplic˘a Principul includerii ¸si excluderii pentru a calcula | 

3

Sn

i=1

Ai |.

Principiul cutiei

Dac˘a n obiecte se plaseaz˘a ˆın r cutii cu r < n, exist˘a cel put¸in o cutie care cont¸ine cel put¸in dou˘a obiecte. In limbajul funct¸iilor, principiul cutiei se poate formula astfel: fie N, R dou˘a mult¸imi finite cu | N |= n, | R |= r ¸si f : N → R o funct¸ie. Dac˘a r < n, atunci exist˘a a ∈ R astfel ˆıncˆat | f −1 (a) |≥ 2.

3.1

Aplicat¸ii

Problema 3.1. Intr-o p˘adure sunt un milion de brazi. Se ¸stie c˘a niciun brad nu are mai mult de 600 000 de ace. Demonstrat¸i c˘a sunt cel put¸in doi brazi ˆın p˘adure care au acela¸si num˘ar de ace. Problema 3.2. Mult¸imea cifrelor de la 1 la 9 se ˆımparte ˆın trei submult¸imi. Demonstrat¸i c˘a, pentru cel put¸in una din submult¸imi, produsul elementelor submult¸imii este mai mare decˆat 71. Problema 3.3. Dat˘a o mult¸ime de 12 numere ˆıntregi, demonstrat¸i c˘a exist˘a cel put¸in dou˘a care au diferent¸a divizibil˘a cu 11. Problema 3.4. Intr-un cub de latur˘a 1 se afl˘a 2001 de fluturi. Ar˘atat¸i c˘a 1 exist˘a cel put¸in 3 fluturi care se afl˘a ˆıntr-o sfer˘a cu raza < 11 . ˘ ¸si Informatica ˘ Facultatea de Matematica

3

Centrul de pregatire pentru copiii performant ¸i

4

Probleme

Problema 4.1. La o petrecere sunt 60 de invitat¸i. Unii dintre invitat¸i dau mˆana cu alt¸ii. Demonstrat¸i c˘a exist˘a dou˘a persoane care dau mˆana cu acela¸si num˘ar de persoane. Se presupune c˘a pot exista persoane care nu dau mˆana cu nimeni. Indicat¸ie. Fie 1, 2, . . . , 60 cele 60 de persoane ¸si h(i) num˘arul de persoane c˘arora le strˆange mˆana persoana i. Evident c˘a, pentru orice 1 ≤ i ≤ 60, avem 0 ≤ h(i) ≤ 59. Cazul 1. Fiecare persoan˘a strˆange mˆana unui alt invitat cel put¸in. Atunci h : {1, 2, . . . , 60} → {1, 2, . . . , 59} ¸si aplic˘am Principiul cutiei. Cazul 2. Exist˘a un unic participant “ursuz”, adic˘a unul care nu strˆange mˆana nim˘anui. S˘a spunem c˘a acesta este invitatul 60. (Dac˘a sunt mai mult¸i “ursuzi” am terminat!). Atunci putem considera restrict¸ia lui h la mult¸imea {1, 2, . . . , 59}.  Problema 4.2. Se consider˘a o mult¸ime A de n numere ˆıntregi distincte. Ar˘atat¸i c˘a exist˘a o submult¸ime a lui A cu proprietatea c˘a suma elementelor din submult¸ime este divizibil˘a cu n. Indicat¸ie. Fie A = {a1 , . . . , an }. Consider˘am sumele S1 = a1 , S2 = a1 + a2 , . . . , Sn = a1 + a2 + . . . + an . Dac˘a S1 , S2 , . . . , Sn dau resturi distincte la ˆımp˘art¸irea cu n, am terminat. Altfel, exist˘a i < j astfel ˆıncˆat Si ≡ Sj mod n, deci suma ai+1 + . . . + aj este divizibil˘a cu n.  Problema 4.3. Se aleg n + 1 numere din mult¸imea {1, 2, . . . , 2n}. Ar˘atat¸i c˘a printre aceste n + 1 numere exist˘a dou˘a relativ prime. Indicat¸ie. Cu Principiul cutiei deducem c˘a printre cele n + 1 numere exist˘a cel put¸in dou˘a consecutive. Acestea sunt relativ prime.  Problema 4.4. Se aleg n + 1 numere din mult¸imea {1, 2, . . . , 2n}. Ar˘atat¸i c˘a printre aceste n + 1 numere exist˘a dou˘a a, b astfel ˆıncˆat a | b sau b | a. Indicat¸ie. Scriem numerele sub forma 2t m, unde m este impar ˆıntre 1 ¸si 2n − 1. Cu Principiul cutiei g˘asim dou˘a numere printre cele n + 1 c˘arora le corespunde acela¸si m. Acestea au proprietatea din enunt¸.  Problema 4.5. Demonstrat¸i c˘a, pentru orice num˘ar impar a, exist˘a un num˘ar natural nenul b astfel ˆıncˆat a | 2b − 1. Indicat¸ie. Dac˘a printre numerele 21 − 1, 22 − 1, . . . , 2a − 1 nu exist˘a niciunul care da restul 0 la ˆımp˘art¸irea cu a, g˘asim dou˘a, 2t − 1, 2s − 1, t < s, astfel ˆıncˆat a | (2s − 1) − (2t − 1) = 2t (2s−t − 1). Cum a este impar, rezult˘a c˘a a | 2s−t − 1.  ˘ ¸si Informatica ˘ Facultatea de Matematica

4

˘rare Tutorial: Probleme de numa

Problema 4.6. Demonstrat¸i c˘a, pentru orice num˘ar natural n, exist˘a un num˘ar format numai cu cifrele 1 ¸si 2 care se divide cu 2n . Indicat¸ie. Vom demonstra c˘a cele 2n numere de n cifre formate numai cu 1 ¸si 2 dau resturi diferite la ˆımp˘art¸irea cu 2n , deci unul din ele trebuie s˘a fie divizibil cu 2n . Fie dou˘a numere x, y care dau acela¸si rest la ˆımp˘art¸irea cu 2n . Atunci ele au aceea¸si ultim˘a cifr˘a, s˘a spunem u. Fie x = 10x1 + u ¸si y = 10y1 + u. Rezult˘a c˘a 2n | 10(x1 − y1 ), de unde 2n−1 | x1 − y1 ¸si x1 , y1 sunt numere cu 2n−1 cifre. Repet˘am rat¸ionamentul ¸si, din aproape ˆın aproape, deducem c˘a x ¸si y au acelea¸si cifre, deci sunt egale.  Problema 4.7. Se dau mult¸imile finite A1 , . . . , An . S˘a se determine num˘arul elementelor care se g˘asesc exact ˆıntr-un num˘ar impar din mult¸imile date. Indicat¸ie. Analizat¸i mai ˆıntˆai cazul n = 2. Constatat¸i c˘a se cere de fapt cardinalul mult¸imii A1 ∆A2 . Calculat¸i | A1 ∆A2 | folosind formula diferent¸ei simetrice. Repetat¸i rat¸ionamentul ¸si calculele pentru 3 mult¸imi. E un prilej bun s˘a revedet¸i sau s˘a descoperit¸i propriet˘a¸tile diferent¸ei simetrice. Apoi, g˘asit¸i u¸sor, prin induct¸ie dup˘a n, c˘a num˘arul cerut este cardinalul mult¸imii A1 ∆A2 ∆ . . . ∆An . Tot prin induct¸ie se verific˘a egalitatea: |A1 ∆A2 ∆ . . . ∆An | =

n X

|Ai | − 2

i=1

+22

X

X

|Ai ∩ Aj |+

1≤i<j≤n

|Ai ∩ Aj ∩ Ak | − . . . + (−1)n−1 2n−1 |A1 ∩ . . . ∩ An |.

1≤i<j
 Problema 4.8. Fie X o mult¸ime nevid˘a ¸si m ≥ 2 submult¸imi ale lui X care formeaz˘a o familie F . Ar˘atat¸i c˘a printre mult¸imile A∆B, unde A, B ∈ F , exist˘a cel put¸in m mult¸imi diferite dou˘a cˆate dou˘a. Indicat¸ie. Fie o mult¸ime fixat˘a A ∈ F . Din propriet˘a¸tile diferent¸ei simetrice rezult˘a c˘a funct¸ia f : F → P(X), B 7→ A∆B, este injectiv˘a. Cum F are m elemente, deducem afirmat¸ia din enunt¸. Problema 4.9. Fie F = {X1 , . . . , Xr } o familie de submult¸imi distincte ale unei mult¸imi X cu proprietatea c˘a oricare dou˘a nu sunt disjuncte. Ar˘atat¸i c˘a dac˘a mult¸imea X are n elemente, atunci num˘arul mult¸imilor din familie, r, este cel mult 2n−1 .

˘ ¸si Informatica ˘ Facultatea de Matematica

5

Centrul de pregatire pentru copiii performant ¸i

Indicat¸ie. Fie S = {X − X1 , . . . , X − Xr }. Atunci, din ipotez˘a, S ∩ F = ∅. Rezult˘a c˘a 2r ≤ 2n . Pentru a construi o familie de submult¸imi ca ˆın enunt¸ cu 2n−1 elemente proced˘am astfel: Fix˘am un x ∈ X ¸si fie Y = X − {x}. Fie {Yi | 1 ≤ i ≤ 2n−1 } toate submult¸imile lui Y. Atunci familia F = {Yi ∪ {x} | 1 ≤ i ≤ 2n−1 } are proprietatea din enunt¸ ¸si are 2n−1 elemente.  Problema 4.10. Determinat¸i num˘arul funct¸iilor cresc˘atoare definite pe mult¸imea {1, 2, . . . , n} cu valori ˆın {1, 2, . . . , r}. Indicat¸ie. La fiecare funct¸ie cresc˘atoare f : {1, 2, . . . , n} → {1, 2, . . . , r} punem ˆın corespondent¸a˘ o funct¸ie strict cresc˘atoare g : {1, 2, . . . , n} → {2, . . . , r + n} definit˘a de g(i) = f (i) + i, pentru orice i. Reciproc, dat˘a o funct¸ie strict cresc˘atoare g : {1, 2, . . . , n} → {2, . . . , r + n}, ˆıi asociem funct¸ia f definit˘a de f (i) = g(i)−i. f este cresc˘atoare ¸si ia valori ˆın mult¸imea {1, 2, . . . , r}. Deci num˘arul funct¸iilor cresc˘atoare f : {1, 2, . . . , n}
→ {1, 2, . . . , r} este egal cu num˘arul funct¸iilor strict cresc˘atoare g, adic˘a n+r−1 . n

Problema 4.11. Determinat¸i num˘arul monoamelor din dezvoltarea (X1 + X2 + . . . + X n ) d .

Indicat¸ie. Vom ar˘ata c˘a acest num˘ar este egal cu num˘arul funct¸iilor cresc˘atoare definite
pe {1, 2, . . . , n − 1} ¸si cu valori ˆın mult¸imea {0, 1, 2, . . . , d} care este n+d−1 . Fie X1i1 . . . Xnin un monom de grad d, adic˘a i1 + . . . + in = d. Atunci d funct¸ia f : {1, 2, . . . , n − 1} → {0, 1, 2, . . . , d}, f (j) = i1 + . . . + ij , ∀ j, este cresc˘atoare. Reciproc, fie f : {1, 2, . . . , n−1} → {0, 1, 2, . . . , d} o funct¸ie cresc˘atoare ¸si i1 = f (1), ij = f (j) − f (j − 1), j = 2, n − 1, in = d − (i1 + . . . + in−1 ). Atunci i1 , . . . , in ≥ 0 ¸si i1 + . . . + in = d, deci f determin˘a monomul de grad d, X1i1 . . . Xnin .  Problema 4.12. Fie a1 < · · · < an , b1 > · · · > bn ¸si {a1 , . . . , an , b1 , . . . , bn } = {1, 2, . . . , 2n}. Ar˘atat¸i c˘a n X

| ai − bi |= n2 .

i=1

Indicat¸ie. Este evident c˘a numerele max(ai , bi ), i = 1, n, sunt distincte, pentru ca ai , bj sunt distincte. Din ipotez˘a, cu Principiul cutiei, deducem c˘a pentru orice 1 ≤ i ≤ n, max(ai , bi ) ≥ n + 1. Rezult˘a c˘a {max(ai , bi ), i = 1, n} = {n + 1, . . . , 2n}. Aplic˘am formula max(ai , bi ) =

ai +bi +|ai −bi | 2

¸si calcul˘am suma din enunt¸.

˘ ¸si Informatica ˘ Facultatea de Matematica

6