Problem Tygodnia #3

Historia, regulamin, zadania i oceny Konkursów oraz Ligi prowadzonej na Forum.
Liga
Gość Specjalny
Gość Specjalny
Posty: 168
Rejestracja: 29 wrz 2006, o 18:17
Płeć: Mężczyzna
Lokalizacja: Forum Matematyka.pl

Problem Tygodnia #3

Post autor: Liga » 25 kwie 2011, o 00:03

Niech \(\displaystyle{ g_n}\) oznacza liczbę takich podzbiorów zbioru \(\displaystyle{ \{1,2,...,n\}}\), które nie zawierają żadnych dwu kolejnych liczb naturalnych. Na przykład \(\displaystyle{ g_3 = 5}\), gdyż zbiorami o żądanej własnosci sa zbiór pusty, zbiory jednoelementowe oraz \(\displaystyle{ \{1,3\}}\). Sprawdzić, czy prawdziwa jest tożsamość:
\(\displaystyle{ g_n=2^n-\sum_{k=2}^{n/2} \left[ (n-k+1)g_{n-k-2}+2g_{n-k-1} \right]}\)
jeżeli przyjmiemy, że \(\displaystyle{ n}\) jest liczbą parzystą większą lub równą 4.

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2626 razy

Problem Tygodnia #3

Post autor: » 25 kwie 2011, o 00:42

Nie zgadza się już dla \(\displaystyle{ n=4}\): wówczas lewa strona jest równa osiem, a prawa dziewięć.

Q.

Awatar użytkownika
Damianito
Użytkownik
Użytkownik
Posty: 68
Rejestracja: 25 kwie 2007, o 13:44
Płeć: Mężczyzna
Lokalizacja: Zabrze
Pomógł: 7 razy

Problem Tygodnia #3

Post autor: Damianito » 25 kwie 2011, o 00:48

Zauważmy, że zachodzi tożsamość \(\displaystyle{ g_{n+1}=g_{n}+g_{n-1}}\), gdzie przyjmujemy \(\displaystyle{ g_0=1}\) (odpowiadające liczbie podzbiorów zbioru pustego), ponieważ możemy wziąć największą liczbę ze zbioru liczb od 1 do (n+1), a reszta jest podzbiorem spełniającym warunki zadania liczb od 1 do (n-1) lub też nie brać (n+1) elementu, czyli wybrać podzbiór dobry zbioru od 1 do n. Biorąc pod uwagę \(\displaystyle{ g_{0}=1}\) i \(\displaystyle{ g_{1}=2}\) dostajemy, że ciąg \(\displaystyle{ g}\) jest ciągiem Fibonacciego przesuniętym o jeden wyraz. Korzystając ze wzorów na sumę ciągów \(\displaystyle{ F_n}\) i \(\displaystyle{ nF_{n}}\) zauważamy, że ta tożsamość nie ma prawa się zwijać do tego, czego chcemy (;p), więc szukamy kontrprzykładu i znajdujemy, np. \(\displaystyle{ n=4}\).

Awatar użytkownika
scyth
Gość Specjalny
Gość Specjalny
Posty: 6392
Rejestracja: 23 lip 2007, o 15:26
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 3 razy
Pomógł: 1087 razy

Problem Tygodnia #3

Post autor: scyth » 26 kwie 2011, o 11:58

Rzeczywiście coś jest nie tak z tym zadaniem i nie widzę sposobu, żeby go uratować.
i Damianito - jeśli się zgodzicie, dziś wieczór możemy dać zadanie zastępcze, a to uznamy za nieważne.

Liga
Gość Specjalny
Gość Specjalny
Posty: 168
Rejestracja: 29 wrz 2006, o 18:17
Płeć: Mężczyzna
Lokalizacja: Forum Matematyka.pl

Problem Tygodnia #3

Post autor: Liga » 28 kwie 2011, o 00:02

Nowe zadanie

Dany jest pewien czworościan c, na którym opisano sferę \(\displaystyle{ s}\). \(\displaystyle{ \alpha, \beta, \gamma, \delta}\) są płaszczyznami stycznymi do tejże \(\displaystyle{ s}\), w odpowiednich wierzchołkach c , tj punktach A, B, C, D, przy czym \(\displaystyle{ \alpha \cap \beta=p}\), i \(\displaystyle{ \gamma \cap \delta=q}\). Wykaż, że jeśli proste \(\displaystyle{ p}\) i CD nie są rozłączne, to \(\displaystyle{ q}\) i AB są współpłaszczyznowe.

Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

Problem Tygodnia #3

Post autor: Swistak » 28 kwie 2011, o 00:32

Jest to przestrzenny odpowiednik twierdzenia o wzajemności biegunowych.
Ja na to popatrzyłem pod takim kątem. Zdefiniujmy sobie dla sfery i punktu analogiczny odpowiednik biegunowej z płaszczyzny (będzie to oczywiście płaszczyzna) w taki sposób, że będzie to suma wszystkich biegunowych tego punktu względem okręgów będących przekrojem tej sfery, których przedłużenie średnicy zawiera ten punkt. Teraz to, że p i CD nie są rozłączne mówi, że istnieje taki punkt E, że A i B leżą na biegunowej E względem sfery s, oraz E, C, D są współliniowe. Zauważmy, że skoro E, C, D są współliniowe, to przecięcie płaszczyzn stycznych do s w punktach C i D będzie to prosta równoległa do biegunowej E względem s. Niech O oznacza środek sfery s i niech r to będzie okrąg będący przecięciem DEO ze sferą s. Niech teraz F i G będą to punkty r nalężące do biegunowej E względem s. Z twierdzenia o wzajemności biegunowych na płaszczyźnie DEO wynika, że FG (biegunowa E względem r) oraz proste poprowadzone z punktów C i D, styczne do r (w płaszczyźnie DEO) przetną się w 1 punkcie, a FG leży w biegunowej E względem S, zatem przecięcie płaszczyzn stycznych do s w C i D zawiera 1 punkt należący do biegunowej E względem s, zatem zawiera się ono całe w tej płaszczyźnie, czyli zarówno AB, jak i to przecięcie należą do tej płaszczyzny.
c.b.d.u.

ODPOWIEDZ