cztery zadania

[sbs]

Witam. Czy mógłbym prosić o rozwiązanie tych zadań:

1)
Jeżeli namalujemy na płaszczyźnie n prostych, z których \(\displaystyle{ x_{1}}\) jest równoległych w jednym kierunku, \(\displaystyle{ x_{2}}\) równoległych w innym kierunku ... i \(\displaystyle{ x_{k}}\) równoległych w jeszcze innym kierunku oraz żadne trzy proste nie przecinają się w tym samym punkcie, to pokazać, że liczba punktów przecięcia wynosi
\(\displaystyle{ \frac{1}{2} \left( n^{2} - \left( x^{2}_{1}+x^{2}_{2} + ... +x^{2}_{k}\right) \right)}\)


2)
W grupie złożonej z 2n uczniów każdy ma co najmniej n przyjaciół. Będące na wycieczce, nauczyciel nakazał im parami za ręce. Pokazać, że można to uczynić tak, że każda osoba trzyma rękę przyjaciela, a w przypadku gdy n>1, wybór przyjaciela może być dokonany na co najmniej dwa różne sposoby.


3)
Na ile sposobów można wybrać trzy liczby spośród 1,2,3,...,30 w ten sposób że ich suma jest parzysta?


4)
Pokazać, że liczba podziałów liczby całkowitej n na składniki całkowite takich, że żadna liczba całkowita nie pojawia się więcej niż dwa razy, jest równa liczbie podziałów n na składniki niepodzielne przez 3.


wskazówki do 1)
\(\displaystyle{ x_{i}}\) prostych przecina się z pozostałymi \(\displaystyle{ n - x_{i}}\) prostymi, wiec ogólna liczna przecięć wynosi \(\displaystyle{ \frac{1}{2} x_{i} ft( n - x_{i} \right)}\). Wiadomo również, że \(\displaystyle{ \sum_{}^{} x_{i} = n}\)

wskazówka do 4)
Wskazać odpowiednią bijekcję.

[Sir George]

Moim zdaniem jest tak:
ad.1) \(\displaystyle{ x_k}\) prostych równoległych przecina się z \(\displaystyle{ x_j}\) prostymi równoległymi (o innym kierunku!) w \(\displaystyle{ x_k\!\cdot\!x_j}\) punktach. Zatem wszystkich przecięć jest \(\displaystyle{ \frac12\sum\limits_{j\neq k}x_k\!\cdot\!x_j}\)
Z drugiej strony jak napisałeś \(\displaystyle{ \sum x_i\,=\,n}\), czyli \(\displaystyle{ n^2\,=\,\sum {x_i}^2+\sum\limits_{j\neq k}x_k\!\cdot\!x_j}\) skąd już otrzymujesz wynik...

ad.3) Liczbę parzystą otrzymamy sumując trzy liczby parzyste, czyli na \(\displaystyle{ {15\choose3}}\) sposobów, albo sumując dwie liczby nieparzyste i jedną parzystą, a to na \(\displaystyle{ {15\choose2}{15\choose1}}\) sposobów. W sumie mamy zatem 2030 różnych możliwości.

[ Dodano: 4 Stycznia 2008, 15:37 ]
ad.2) Jeśli relacja "bycia przyjacielem" jest zwrotna, to możemy wykorzystać teorię grafów nieskierowanych (uczniowie są wierzchołkami,a krawędzie łączą przyjaciół). Z wynika, że tak skonstruowany graf jest hamiltonowski, a co za tym idzie również dwudzielny (co jest równoznaczne z podziałem na pary!). Jeśli n>1, to ścieżka Hamiltona ma długość większą niż 1, czyli można krawiędzie łączyć w pary na dwa sposoby (przynajmniej) - raz po parzystych krawędziach ścieżki Hamiltona, a raz po nieparzystych...

[Qń]

Pierwsze można zrobić też wprost ze wskazówki (chyba prościej), tylko tam przy \(\displaystyle{ x_i}\) nie powinno być kwadratu.

W czwartym natomiast odpowiedniość między podziałami konstruujemy tak:
Niech \(\displaystyle{ n= \sum_{i=1}^{n} a_i}\) będzie podziałem liczby \(\displaystyle{ n}\) na liczby całkowite dodatnie, takim w którym żadna liczby całkowita nie występuje więcej niż dwa razy. Zastąpmy w nim każdy składnik postaci \(\displaystyle{ 3^kl}\) (gdzie \(\displaystyle{ l}\) nie jest podzielne przez \(\displaystyle{ 3}\)) przez \(\displaystyle{ 3^k}\) składników równych \(\displaystyle{ l}\). Otrzymamy w ten sposób nowy podział, taki, w którym nie będą występowały składniki podzielne przez \(\displaystyle{ 3}\). Przykładowo podziałowi:
\(\displaystyle{ 25 = 9 + 6 + 6 + 4}\)
odpowiada podział:
\(\displaystyle{ 25 = (1+1+1+1+1+1+1+1+1) + (2+2+2)+(2+2+2) +4}\)
Łatwo zauważyć, że tę procedurę da się też odwrócić, skąd (być może po chwili zastanowienia ) płynie wniosek, że jest to bijekcja.

Pozdrawiam.
Qń.

[sbs]

Zadania wróciły do poprawienia

Czy mógłby ktoś rozwiązać całe zadanie 1).

2) " ... graf jest hamiltonowski, a co za tym idzie również dwudzielny (co jest równoznaczne z podziałem na pary!). ... " zastrzeżenia były odnośnie tego co jest podkreślone

4) "procedurę da się też odwrócić" Trzeba wyjaśnić w jaki sposób dokonuje się operacji odwrócenia

Bardzo proszę o pomoc, sam sobie z tym nie poradzę.
Jak dal mnie odp. może być na kartce i zeskanowane, albo zrobione zdjęcia z aparatu/komórki.

[Qń]

Tak z ciekawości spytam - oddałeś prowadzącemu zajęcia rozwiązania zadań przepisane słowo w słowo z forum?

Q.

[sbs]

Pierwsze robiłem ze wskazówki, że się na tym nie znam było źle. //brak wyjaśnienia
Trzecie było na tyle proste, że sam już wcześniej je zrobiłem.
A z resztą było przykładowo tak:
"Można zauważyć, że tę procedurę da się też odwrócić, skąd płynie wniosek, że jest to bijekcja."

[Sir George]

2) " ... graf jest hamiltonowski, a co za tym idzie również dwudzielny (co jest równoznaczne z podziałem na pary!). ... "

Graf jest Hamiltonowski, istnieje zatem ścieżka Hamiltona (tj. ścieżka przechodząca przez każdy wierzchołek grafu dokładnie jeden raz). Biorąc wierzchołki o numerach parzystych w ścieżce Hamiltona i te o numerach nieparzystych dostajemy podział wierzchołków na dwa rozłączne zbiory, które są połączone ze sobą. Przyznaję, że poprawna definicja grafu dwudzielnego zakłada dodatkowo, że wierzchołki wewnątrz owych zbiorów nie są połączone żadną krawędzią - czego oczywiście w ogólnym przypadku nie otrzymamy. Do rozwiązania zadania wystarczy jednak wiedza, że istnieje ścieżka Hamiltona, która da już podział na pary...

Pozdrawiam, sG

[sbs]

Wielkie dziki za to, że tyle już zrobiliście, tylko że potrzebuje mieć rozwiązane wszystkie 4 zadania.
To jak, wie ktoś jak zrobić poprawnie zad 1??
ad 4) Trzeba wyjaśnić w jaki sposób dokonuje się operacji odwrócenia i dlaczego obie te operacje są rzeczywiście względem siebie odwrotne

[Qń]

Trochę inaczej rozumiem rolę niniejszego forum - dla mnie nie jest ono miejscem, gdzie otrzymuje się gotowce, a raczej miejscem gdzie można otrzymać wskazówkę lub naprowadzenie na właściwy pomysł. I w związku powyższym nachalne proszenie o rozwiązania, które będziesz mógł bez większego zrozumienia przepisać słowo w słowo - wydaje mi się mało stosowne.

Q.

[sbs]

Wiadomo w jakim celu umieszcza się tu zadania i na innych tego typu forach.
Ja pomagam na forum z programowania i nie mam nic przeciwko jak ktoś oddaje mój program.
Czasem zrozumienie jakiegoś problemu nie jest komuś do niczego potrzebne.

[Qń]

Wiadomo w jakim celu umieszcza się tu zadania i na innych tego typu forach.

Widać jestem naiwny i staroświecki, bo mi wiadomo było co innego niż Tobie.

Czasem zrozumienie jakiegoś problemu nie jest komuś do niczego potrzebne.

Wyjaśnij więc prowadzącemu zajęcia, że nie potrzebujesz wiedzy, której się od Ciebie wymaga.

Q.