Elemente de Combinatorică

Elemente de Matematică și Informatică. Teorie, Probleme. Discuții.
User avatar
Admin
Site Admin
Posts: 750
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

Elemente de Combinatorică

Postby Admin » 01 Jan 2013, 18:47

În subForumul Olimpiade şi Concursuri de Matematică (subForumul Diverse) am creat topicul :
"Combinatorics and Graph Theory" – by Ioan Tomescu.
Topicul are însă o dificultate mai accentuată, unele lucruri (mai ales cele referitoare la Grafuri) nefăcându-se până la Facultate. De aceea am preferat să deschid un Topic special aici.

Elementele de Combinatorică (în principiu fără Teoria Grafurilor) includ şi "combinatorica mulţimilor".
Noţiunile de aici pot acoperi studiul făcut pe parcursul tuturor anilor de Liceu, unele dintre probleme sunt accesibile şi "juniorilor", adică celor din învăţământul gimnazial. De aceea am preferat să deschid topicul aici şi nu la clasa a 10-a.



User avatar
Admin
Site Admin
Posts: 750
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

Elemente de Combinatorică

Postby Admin » 01 Jan 2013, 19:51

Problemă

Fie $A_1, A_2, ..., A_n$ mulţimi de cardinal $n$.
Oricare $2$ mulţimi de mai sus au intersecţia diferită de $\varnothing$ iar intersecţia oricăror $3$ mulţimi este $\varnothing$.
Să se arate că $|A_1 \cup A_2 \cup ... \cup A_n | \leqslant \frac{n(n+1)}{2}$.

(Problema a fost dată şi la clasa a 9-a, la Etapa finală a Concursului "Arhimede", 22 ianuarie 2005, Bucureşti)

Rezolvare :

Probabil soluţia autorilor (aşa cum o văd într-o carte) este cea bazată pe principiul includerii şi al excluderii.
(Eu am abordat un studiu separat, de aceea am postat problema aici .. aşa că ulterior o să discut despre unele aspecte ...)

Principiul (Formula) :

$|A_1 \cup A_2 \cup ... \cup A_n |$ = $\displaystyle\sum\limits_{i=1}^{n} |A_i| -$ $\displaystyle\sum\limits_{i<j} |A_i \cap A_j| +$ $\displaystyle\sum\limits_{i<j<k} |A_i \cap A_j \cap A_k| - ... +$

$... +(-1)^{n+1} |A_1 \cap A_2 \cap ... \cap A_n|$

OBS : In cazul a $2$ mulţimi principiul includerii şi al excluderii este aşa :

$|A \cup B|$ = $|A| + |B| - |A \cap B|$.

(Deci cardinalul unei reuniuni de $2$ mulţimi este suma cardinalelor mulţimilor minus cardinalul intersecţiei mulţimilor)




Revenind la problema de bază, observăm că (în situaţia problemei, cu ipoteza sa) toate sumele care conţin intersecţii de minim 3 mulţimi sunt nule. Deci în problema de faţă principiul devine :

$|A_1 \cup A_2 \cup ... \cup A_n |$ = $\displaystyle\sum\limits_{i=1}^{n} |A_i| -$ $\displaystyle\sum\limits_{i<j} |A_i \cap A_j| \stackrel{not}{=}$ (**)

Din ipoteză, intersecţia oricăror $2$ submulţimi este nevidă deci $1 \leqslant |A_i \cap A_j|$ sau $- |A_i \cap A_j| \leqslant -1$.
Atunci după (**) se poate continua aşa :

(**) $\leqslant \displaystyle\sum\limits_{i=1}^{n} n - \displaystyle\sum\limits_{i<j} 1$ $= n^2 - \frac{n(n-1)}{2} = \frac{n(n+1)}{2}$

QED

PS. O discuţie cu înţelegerea "mecanismului" în cazul acestei probleme, plus $2$ soluţii (fără principiul includerii şi al excluderii) şi o completare cu exemplu de mulţimi $A_i$ care realizează maximul într-o postare ulterioară.

User avatar
Admin
Site Admin
Posts: 750
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

Elemente de Combinatorică

Postby Admin » 01 Jan 2013, 19:54

Încă o dată, reamintesc că într-o situaţie în care se întâmplă să vedeţi simbolurile LaTeX în locul formulelor matematice obişnuite daţi Reload / Refresh la pagină.

Un asemenea lucru se întâmplă totuşi foarte rar ... Mai degrabă poate fi vorba de o încărcare mai greoaie a paginii cu formulele matematice scrise în LaTeX folosind MathJax .. fiindcă la scrierea cu butonul tex nu e nici o problemă ...
Personal prefer scrierea cu MathJax (deci scrierea LaTeX e încadrată de simbolurile dollar în loc de TAG-urile tex) deoarece alinierea formulelor este mai bună faţă de "textul înconjurător".

User avatar
Admin
Site Admin
Posts: 750
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

Elemente de Combinatorică

Postby Admin » 01 Jan 2013, 20:43

O altă soluţie la problema postată 2 mesaje mai sus.

Fie deci $A_1, A_2, ..., A_n$ cele $n$ mulţimi de mai sus care respectă condiţiile din ipoteză.

$|A_1| = n$ atunci prin reuniunea $A_1 \cup A_2$ obţinem pe lângă cele $n$ elemente ale lui $A_1$ cel mult încă $n-1$ elemente.
In caz contrar, dacă am obţine încă $n$ elemente, am obţine $A_1 \cap A_2 = \varnothing$, lucru ce contrazice ipoteza.

Reunind acum $A_1 \cup A_2 \cup A_3$ am obţine în plus faţă de $A_1 \cup A_2$ încă cel mult $n-2$ elemente.

Aceasta deoarece deja avem măcar un element $x \in A_1 \cap A_3$ şi $y \in A_2 \cap A_3$ iar $x \neq y$, în caz contrar, dacă $x=y$ am obţine $A_1 \cap A_2 \cap A_3 \neq \varnothing$ lucru ce iarăşi contrazice ipoteza.

Din aproape în aproape, plecând de la $A_1$ şi reunind pe rând celelalte mulţimi vom obţine cel mult încă : $(n-1) + (n-2) + ... + 1$ . Deci în total am avea cel mult :

$n +(n-1) + (n-2) + ... + 1 = \frac{n(n+1)}{2}$. QED




O altă soluţie este prin inducţie (lucru "nerevelator", în unele cazuri ...).
Dar până la pregătirea aplicării inducţiei se mai observă şi alte lucruri.

Despre aceasta şi despre un exemplu în care se atinge maximul, adică $\frac{n(n+1)}{2}$ , într-o postare viitoare.

User avatar
Admin
Site Admin
Posts: 750
Joined: 22 Jan 2012, 14:23
Location: România
Contact:

Elemente de Combinatorică

Postby Admin » 29 Dec 2021, 19:43

Numerele întregi se colorează în $n$ culori astfel încât dacă $x, y \in \mathbb{Z}$
și $|x-y| \in \{ 2,3,5 \}$ , atunci $x$ și $y$ au culori diferite. Să se arate că $n \geqslant 4$.
(Baraj OIM 2002 - Ioan Tomescu)

Rezolvare

Presupunem prin absurd $n \leqslant 3$ și fie numerele $0,2,3,5$.

$|0-2|, |0-3|, |0-5| \in \{2,3,5 \}$ deci $2,3,5$ au altă culoare decât $0$.

Dar și $|5-2|, |5-3| \in \{2,3,5 \}$ deci $2,3$ au altă culoare decât $5$.

Deci avem deja $3$ culori iar $2, 3$ trebuie să aibă aceeași culoare.

Repetăm raționamentul pentru numerele $1,3,4,6$ deci $3$ și $4$ au aceeași culoare.

Atunci $2$ și $4$ au aceeași culoare - însă $|2-4|=2 \in \{2,3,5 \}$, contradicție.


Return to “Teorie și Probleme”

Who is online

Users browsing this forum: No registered users and 3 guests

mateinfo
UP
cron