2 zadania: grafy i kombinatoryka

[jraven]

Zad1 Czy istnieje podział zbioru liczb naturalnych od 1 do 8 na dwa podzbiory takie że żaden z nich nie zawiera postępu arytmetycznego długości trzy? Spróbować odpowiedzieć na to samo pytanie, ale w odniesieniu do liczb od 1 do 9.

Odpowiedź brzmi dla 1-8: "tak"; dla 1-9: "nie"; jak to uzasadnić?

Zad2 Grubość grafu \(\displaystyle{ G = ft( V,E \right)}\) jest najmniejszą liczbą grafów planarnych \(\displaystyle{ \left( V,E _{1} \right) ,..., ft( V,E _{t} \right)}\) takich, że \(\displaystyle{ E _{1}\cup...\cupE _{t}=E}\). Pokazać, że dla \(\displaystyle{ \left| V\right| qslant 3}\) grubość grafu \(\displaystyle{ G}\) wynosi co najmniej \(\displaystyle{ { ft| E\right| /(3 ft| V\right| - 6)}}\) i wywnioskować, że grubość grafu pełnego \(\displaystyle{ K _{n}}\) wynosi co najmniej \(\displaystyle{ \left[ \frac{1}{6} ft( n+7\right) \right]}\).[/code][/latex]

[bosz]

Nie znajduje jakiegoś ogólnego.. tak by brutal force:


A - zbior do ktorego nalezy 1
mamy dwiemozliwosci
1.- 2 nalezy do A

wtedy 3 i 4 musza nalezec do B 5i 6 do a 7 i 8 znow do B
A= {1,2,5,6} B= {3,4,7,8}

2.- 2 nalezy do B

tu mamy znow dzie mozliwosci
3 nalezy do A i wtedy mamy

A= {1,3,6,8} B= {2,4,5,7}

lub 3 nalezy do B

A= {1,4,5,8} B= {2,3,6,7}

wiec wskazalem wszystkie podzialy .
do zadnego z nich nie da sie dolozyc 9