szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 1 gru 2014, o 14:58 
Użytkownik

Posty: 25
Lokalizacja: Kraków
1. Na każdym z pól szachownicy o wymiarach n × n położono lub nie jedno ziarenko. Jaka jest minimalna łączna liczba kolumn, wierszy i przekątnych na których znajduje się po tyle samo ziarenek?

2. Na ile różnych sposobów można spośród 20 rycerzy wybrać 13 i obsadzić nimi dokładnie 3 z 4 baszt zamku (nazwanych wg stron świata).

3. Ile jest różnych permutacji ciągó 1,2,...,n w których każda liczba i znajduje się na miejscu i lub sąsiednim z i (dla i = 1,2,...,n)? Znajdź zależność rekurencyjną.

4. Ile jest roznych wynikow meczow hokejowych w ktorych strzelono 13 bramek jesli wynik meczu podaje sie wraz z wynikami trzech tercji?

5. Ile jest ciągów binarnych o długości n, w których jest dokładnie k par 01?

Pomógłby ktoś z rozwiązaniami takich zadań?
1. Wydaje mi się, że zasady szufladkowej dirichleta, tylko nie wiem czy jeśli chodzi o przekątne to tylko te 2 o n miejscach czy wszystkie?
2/3. Z liczb Stirlinga, ale nie wiem jak zacząć.
4/5. W ogóle teog nie widzę.

Z góry dziękuje za pomoc. To nie tak, że oczekuję odrazu rozwiązań, tylko zbliża się kolokwium i chciałbym to zrozumieć.
Góra
Mężczyzna Offline
PostNapisane: 1 gru 2014, o 17:53 
Użytkownik

Posty: 166
Lokalizacja: Bytom
1. Rozwiązanie szłoby mniej więcej tak samo niezależnie od tego, czy bierzesz jedynie te dwie przekątne czy wszystkie "przesunięte" 2n (przesunięte w sensie że przechodzisz przez ścianę i kontynuujesz dopóki każda przekątna ma n pól). Zrobiłoby się trudniej gdybyś musiał rozważać te przekątne jako "obcięte" (czyli niektóre miałyby mniej pól), ale nie wydaje mi się żeby to zadanie miało być aż tak skomplikowane.

W każdym razie masz n kolumn, wierszy i 2n przekątnych, natomiast ziarenek w każdym zbiorze jest od 0 do n. Mamy więc 4n obiektów w n+1 szufladkach, więc z zasady szufladkowej musi istnieć szufladka z \ceil{\frac{4n}{n+1}}=3 (lub 2 dla n=1) obiektami, zatem Twoja minimalna liczba to 2 lub 3 zależnie od n.

2. Liczbami Stirlinga? A czemu nie:
- wybieramy 13 spośród 20;
- wybieramy 3 spośród 4 wież;
- liczymy na ile sposobów możemy rozmieścić w tych trzech, odejmując sposoby które obsadzają mniej niż trzy wieże.

Finalnie:

{20 \choose 13}{4 \choose 3}(3^{13}-{3\choose 2}2^{13}-3).

3. Oczywiście I_1=1, I_2=2. Dla n\ge 3 (zakładam że traktujemy 1 i n jako nie sąsiadujące ze sobą) albo n zostaje na swoim miejscu i resztę permutujemy zgodnie z warunkami zadania na I_{n-1} sposobów, albo zamieniamy miejscami n i n-1, resztę permutując na I_{n-2} sposobów. Zatem
I_n=I_{n-1}+I_{n-2}.
Góra
Mężczyzna Offline
PostNapisane: 1 gru 2014, o 21:21 
Użytkownik

Posty: 25
Lokalizacja: Kraków
3. Chodziło mi, że pierwszą część zadania chyba z liczb Sterlinga.

1. Czemu n+1 szufladek?
Góra
Mężczyzna Offline
PostNapisane: 2 gru 2014, o 17:21 
Użytkownik
Avatar użytkownika

Posty: 3302
Lokalizacja: blisko
zad 4.
Nie znam się na hokeju ale z tego co pisze w zadaniu wyobrażam to sobie tak:

I tura: a:b

II tura: c:d

III tura: e:f

Z warunków zadania:

a+b+c+d+e+f=13,0 \le a,b,c,d,e,f \le 13

co daje:

{6+13-1 \choose 13} ={18 \choose 13}

A pytanie powinno raczej brzmieć:

Ile jest możliwych wyników meczu hokejowego w którym strzelono - 13 bramek

...............................................................................................................

Co do 5 tego zadania pojęciem kluczowym są serie w ciągach zer i jedynek.

Może napiszę kilka przykładów:

I . Np takie ciągi zaczynające i kończące się zerami:

0001......0111000

Zauważmy że w tego typu ciągach występuje:

k - serii jedynek

k+1 - serii zer

k - par 01

R=k+k+1=2k+1 - wszystkich serii


II. Ciągi zaczynające się jedynkami i kończące się zerami:

111 0001......0111000

Zauważmy że w tego typu ciągach występuje:

k+1 - serii jedynek

k+1 - serii zer

k - par 01

R=k+1+k+1=2k+2 - wszystkich serii


III. Ciągi zaczynające się zerami i kończące się jedynkami:

0001......0111000111

Zauważmy że w tego typu ciągach występuje:

k - serii jedynek

k - serii zer

k - par 01

R=k+k=2k - wszystkich serii


IV. Ciągi zaczynające się jedynkami i kończące się jedynkami:

1110001......0111000111

Zauważmy że w tego typu ciągach występuje:

k+1 - serii jedynek

k - serii zer

k - par 01

R=k+1+k=2k+1 - wszystkich serii

Innych możliwości już niema.

Niech teraz:

n - długość ciągu

x - ilość występujących jedynek

y - ilość występujących zer

n=x+y

Teraz stosuję wzór do ilości serii R
bo zauważmy tyle będzie par 01 - ile będzie wynosiło k

w każdym z tych przypadków.

I teraz wracając do przypadków i korzystając ze wzoru na serie mamy:

ad. (I) - R=2k+1,

a(n,k)= {x-1 \choose k} {y-1 \choose k-1}+ {x-1 \choose k-1} {y-1 \choose k}


ad. (II) - R=2k+2,

a(n,k)= {x-1 \choose k} {y-1 \choose k}


ad. (III) - R=2k,

a(n,k)= {x-1 \choose k-1} {y-1 \choose k-1}


ad. (IV) - R=2k+1,

a(n,k)= {x-1 \choose k} {y-1 \choose k-1}+ {x-1 \choose k-1} {y-1 \choose k}


gdzie: a(n,k) - to ilość ciągów w których występuje k - par 01

Wyszedłem tu z obserwacji, że ilość serii i ilość par 01 - jest związana ze sobą.
Potem zastosowałem wzór na ilość serii w ciągu zerojedynkowym!
Góra
Mężczyzna Offline
PostNapisane: 3 gru 2014, o 12:36 
Użytkownik

Posty: 166
Lokalizacja: Bytom
Szufladki są ponumerowane od 0 do n, więc jest ich n+1.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania kombinatoryczne  marysia_marysia  2
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 3 zadania...  Ciapanek  2
 Zadania z kombinatoryki  neworder  1
 Dwa SKOMPLIKOWANE zadania :)))  domel666  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl