"Combinatorics and Graph Theory" – by Ioan Tomescu

[Iulian]

... probleme dintr-o carte celebră ...
La unele din ele am dat soluții diferite și mai scurte - pun aici doar pozele (.. capturi din postări mai vechi)

La primele probleme care urmează am găsit soluțiile pur și simplu "jucându-mă" cu pb. 3.28 (dar la un moment dat mi-am dat seama și de ce găsisem acum vreo 4-5 ani ... adică de demonstrația la pb 3.24 ...)

Puteți compara cu soluțiile din carte (la Gigapedia vă faceți cont gratuit și descărcați foarte multe cărți (din orice domeniu) în format pdf sau djvu - pt care instalați WinDjView, un soft gratuit și e cam la fel ca Adobe Acrobat Reader)

[Iulian]

Din păcate unele imagini nu au fost păstrate de "ImageShack" - nu cunosc motivul - dar postez alte imagini mai jos.
Pentru postări de imagini - fără logare - am implementat un buton în dreapta casetei de editare, pentru Upload foarte simplu şi rapid, fără cod Captcha, la PostImage.
Alte site-uri foarte bune de acelaşi tip, pe care le prefer : ImgUr, TinyPic, ImgBox.
Multe detalii în topicul : Tutoriale, Informaţii şi Teste legate de Imagini

[Iulian]

Prin 2004 am dat o soluţie diferită faţă de cea din carte la problema 4.15, o soluţie "mai naturală" (şi făcut notarea "soluţie personală mai bună pe caietul nr ..").

Abia în vara trecută (2011) când am refăcut soluţia (mă "jucam" cu problema) mi-am dat seama că demonstrasem de fapt şi mai mult decât în enunţul problemei (în 2004 nu-mi dădusem seama că demonstrasem mai mult !...)

Mai întâi să public enunţul problemei şi soluţia din cartea maestrului Ioan Tomescu, profesorul meu de la Universitate (un om atât de îndrăgit de mine .. şi de mulţi, mulţi alţi colegi ...)

Enunţ (din cartea de la Gigapedia, unde o găsim doar în limba engleză)

Soluţia din carte

Într-o postare viitoare o să dau soluţia de care am vorbit, precum şi observaţiile de rigoare ...

[Iulian]

Observ că am uitat să scriu aici demonstraţia problemei anterioare.
(Demonstraţie în care nu am nevoie ca submulţimile $A_i$ să aibă acelaşi cardinal) ...

===========================================

a) Prima parte a problemei :

Presupunem $x \notin A_{i_1} \bigcup ... \bigcup A_{i_{k-1}}$ si $y \notin A_{j_1} \bigcup ... \bigcup A_{j_{k-1}}$ , doua $(k-1)$ - reuniuni diferite.

Atunci $x \neq y$ , fiindcă dacă prin absurd $x=y$ atunci $x \notin (A_{i_1} \bigcup ... \bigcup A_{i_{k-1}}) \bigcup (A_{j_1} \bigcup ... \bigcup A_{j_{k-1}})$,
însă reuniunea anterioară are cel puţin $k$ mulţimi $A_i$ (reuniunile iniţiale fiind diferite) deci reuniunea va fi egală cu $S$, deci contradicţie.

Ideea este deci, că la $(k-1)$-reuniuni diferite avem elemente diferite care lipsesc (elemente din mulţimea totala $S$).

Avem $\binom{n}{k-1}$ astfel de reuniuni deci $|S| \geq \binom{n}{k-1}$.

Observatie: Nu am avut nevoie de egalitatea în cardinal a mulţimilor $A_i$.

b) Presupunem acum $|S| = \binom{n}{k-1}$

Mai întâi facem observaţia că la fiecare $(k-1)$-reuniune de submulţimi $A_i$ lipseşte FIX $1$ element, altminteri $|S| > \binom{n}{k-1}$.

1). Fixăm pe $A_1$. Avem $\binom{n-1}{k-1}$ reuniuni de $k-1$ submulţimi $A_i$ care nu îl conţin pe $A_1$.
De fiecare dată lipseşte un singur element, acesta trebuind neapărat să se regăsească în $A_1$, altminteri, dacă la una din reuniuni acel element lipsă nu este în $A_1$ reunim şi pe $A_1$, obţinem reunine de $k$ submulţimi $A_i$ adică exact mulţimea totală $S$, şi totuşi nu este prezent un element. Contradicţie.
Deci la fiecare $(k-1)$-reuniune de submulţimi $A_i$ dar fără să fie $A_1$ avem lipsă FIX un element iar acesta este în $A_1$.

2) Avem restul de $\binom{n-1}{k-2}$ reuniuni de $(k-1)$ submulţimi care conţin pe $A_1$ şi toate elementele lipsă sunt în afara lui $A_1$ (acesta fiind prezent în fiecare reuniune).

Observăm că am numarat deja toate elementele lui $S$ deoarece $\binom{n-1}{k-1} + \binom{n-1}{k-2} = \binom{n}{k-1}$, cu alte cuvinte avem $\binom{n-1}{k-1}$ elemente în $A_1$ şi $\binom{n-1}{k-2}$ elemente în afara lui $A_1$, deci $|A_1| = \binom{n-1}{k-1}$.
La fel pentru orice altă submultime $A_i$.

[Admin]

Problema a fost dată la Olimpiada Națională de Matematică, 1980, la clasa a 10-a.
În postarea următoare voi încerca să dau o demonstrație prin inducție.

[Admin]

Demonstrație prin inducție după $n$.
După mai multe încercări am reușit să demonstrez prin inducție 2 lucruri:
- Există $p$ cu proprietatea cerută ($m$ și $n$ fiind date)
- Valoarea $m(m-1)p(p-1)$ este pătrat perfect.

Cazul $n=0$: $(\sqrt{m} + \sqrt{m-1})^0 = 1 = \sqrt{1} - \sqrt{0}$, deci $p=1$
iar valoarea $m(m-1)p(p-1) = 0$, pătrat perfect.

Cazul $n=1$: $(\sqrt{m} + \sqrt{m-1})^1 = \sqrt{m} + \sqrt{m-1}$, deci $p=m$
iar valoarea $m(m-1)p(p-1) = m(m-1)m(m-1)$ care e pătrat perfect.

Cazul $n=2$: $(\sqrt{m} + \sqrt{m-1})^2 = 2m-1 + 2\sqrt{m(m-1)} = \sqrt{(2m-1)^2} + \sqrt{4m^2-4m}$
deci $p=(2m-1)^2$ iar $m(m-1)p(p-1) = 2^2m^2(2m-1)^2(m-1)^2$, pătrat perfect.

Fie $m$ dat, natural oarecare și presupunem că cerințele sunt adevărate pentru exponentul $0, 1, 2, ...,n$,
și trebuie să arătăm pentru $n+1$. Reținem deci că există $p$ iar $m(m-1)p(p-1)$ e pătrat perfect.

$(\sqrt{p} + \sqrt{p-1})(\sqrt{m} + \sqrt{m-1}) = \sqrt{mp}+\sqrt{(m-1)(p-1)} + \sqrt{(m-1)p} + \sqrt{m(p-1)}$ $~~~(1)$
Observăm că dacă notăm $\sqrt{q}$ suma primilor 2 radicali atunci, prin ridicare la pătrat obținem că suma
următorilor 2 radicali este $\sqrt{q-1}$. Dar rămâne de arătat că $q \in \mathbb{N}$

Aceasta se verifică imediat fiindcă $q = mp + 2\sqrt{m(m-1)p(p-1)} + (p-1)(m-1)$
iar $m(m-1)p(p-1)$ e pătrat perfect.

(Deci am lucrat cu $q$ pentru nivelul $n+1$)
Mai trebuie demonstrat partea cea mai dificilă. Anume că: $m(m-1)q(q-1)$ este pătrat perfect.
Altfel spus, că $\sqrt{m(m-1)q(q-1)}$ e natural. Folosim egalitatea $(1)$.

$\sqrt{m(m-1)q(q-1)} = \sqrt{m}\sqrt{m-1}\sqrt{q}\sqrt{q-1} = $

$= \sqrt{m}\sqrt{m-1}\Big(\sqrt{mp} + \sqrt{(p-1)(m-1)}\Big) \Big(\sqrt{(m-1)p} + \sqrt{m(p-1)} \Big) = $

$= \sqrt{m}\sqrt{m-1}\Big(p\sqrt{m}\sqrt{m-1} +m\sqrt{p}\sqrt{p-1} + (m-1)\sqrt{p}\sqrt{p-1} + $

$+ (p-1)\sqrt{m}\sqrt{m-1} \Big) = m(m-1)p + m\sqrt{m(m-1)p(p-1)} + $

$+ (m-1)\sqrt{m(m-1)p(p-1)} + (p-1)m(m-1)$

care este natural fiindcă $m(m-1)p(p-1)$ e pătrat perfect.