Pagina 1 din 1

Tabara MathTime, ziua V-Combinatorica-Marcel Teleuca

Scris: Mie Oct 12, 2011 9:31 pm
de Mr. Ady
Curs sustinut de domnul profesor Marcel Teleuca

Problema 1. In fiecare varf al unui poligon regulat cu $$100$$ de varfuri sunt scrise $$2$$ numare diferite. Demonstrati ca oricare ar fi numerele scrise, putem sterge cate un numar de la fiecare varf astfel incat numerele ramase sa fie diferite la oricare varfuri adiacente.

Problema 2. Fie $$ S $$ o multime cu $$ n $$ elemente si $$0$$ $\le$ $$ N $$ $$ < $$ $$ 2^n$. Demonstrati ca submultimile lui $$ S $$ pot fi colorate in alb si negru astfel incat reuniunea oricaror $$2$$ submultimi albe sa fie alba, iar reuniunea oricaror $$2$$ negre sa fie tot neagra.De asemenea, se stie ca exista doar $$ N $$ submultimi albe.

Problema 3. Fie $$ n $$ $\in$ $\Bbb{N}$. Gasiti numarul natural maxim $$ k $$ astfel incat putem selecta $$ k $$ submultimi diferite ale unei multimi cu $$ n $$ elemente, oricare $$ 2 $$ avand intersectia nevida.

Problema 4. Intr-o tara sunt $$ 100 $$ de orase, iar cateva dintre ele sunt unite cu drumuri astfel incat din fiecare oras se poate ajunge in oricare altul. In total exista $$ 1000 $$ de drumuri. Cateva drumuri se vor inchide astfel incat din fiecare oras sa porneasca un numar par de drumuri spre celelalte orase. In cate moduri se poate indeplini acest lucru?

Problema 5. Intr-o tara sunt $$ 2000 $$ de orase.Unele perechi de orase sunt unite printr-un drum astfel incat din orice oras se poate ajunge in oricare altul.Aratati ca tara poate fi impartita in cateva republici(chiar si $$1$$ singura) astfel incat in oricare republica, din fiecare oras se poate ajunge in oricare altul (in mod unic) fara a iesi in afara republicii.

Problema 6. Avem $$ n $$ puncte in plan, oricare $$2$$ sunt unite printr-un segment, iar oricare $$3$$ necoliniare.Toate segmentele sunt colorate in $$4$$ culori. Care este valoarea minima a lui $$ n $$ pentru care exista un triunghi monocolor cu varfurile in aceste puncte?