szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 21 lut 2015, o 14:20 
Użytkownik

Posty: 64
Lokalizacja: Polska
Ile jest liczb pięciocyfrowych o cyfrach ze zbioru \left\{ 0,1,2,3,4,5\right\} jeżeli w zapisie każdej takiej liczby występują dokładnie dwie takie same cyfry ?
Rozważył bym dwa przypadki.
1) w liczbie występują dwa zera
2) w liczbie występują dwie spośród cyfr \left\{ 1,2,3,4,5\right\}
Ad 1)
Losujemy dwa miejsca na cyfrę 0 czyli {4\choose 2} ,bo 0 nie może stać na początku Zostaje nam pięć cyfr, którymi uzupełniamy pozostałe miejsca na 5 \cdot 4 \cdot 3 sposoby.
Ad 2)
a) Jedna z powtarzających się cyfr na początku
Losujemy jeszcze jedno miejsce na powtarzającą się cyfrę \left\{ 1,2,3,4,5\right\}
5 \cdot {4\choose 1} i uzupełniamy pozostałymi na 5 \cdot 4 \cdot 3
b) Powtarzające się gdzieś w środku poza 1 miejscem
Losujemy 2 miejsca na powtarzającą się cyfrę 5 \cdot {4\choose 2}
Na pierwsze miejsce {4\choose 1} bo nie chcemy 0 Pozostałe uzupełniamy na 4 \cdot 3 sposoby.
Czy to rozwiązanie ma sens? Można zrobić to prościej?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Kobieta Offline
PostNapisane: 21 lut 2015, o 14:29 
Użytkownik
Avatar użytkownika

Posty: 2505
Rozwiązanie jest w porządku i już teraz jest całkiem proste. W tego typu problemach zero zawsze psuje nam życie i zmusza do rozważania przypadków.
Góra
Mężczyzna Offline
PostNapisane: 21 lut 2015, o 14:34 
Użytkownik

Posty: 64
Lokalizacja: Polska
Ok, dziękuję za sprawdzenie
Góra
Mężczyzna Offline
PostNapisane: 21 lut 2015, o 23:30 
Użytkownik

Posty: 454
Lokalizacja: Warszawa
artmat, sprawdziłem bardzo pobieżnie twoje rozwiązanie, wychodzi mi taka suma {4 \choose 2} \cdot 5 \cdot 4 \cdot 3 + 5 \cdot 4 \cdot 5 \cdot 4 \cdot 3 + 5 \cdot {4 \choose 2} \cdot 4 \cdot 4 \cdot 3 = 360+1200+1440=3000 a mi wychodzi 3516 przypadków. Sprawdź czy dobrze zinterpretowałem twoje zapisy.

A moje rozumowanie jest następujące:
  1. Każda liczba w naszym zadaniu jest wariacją z powtórzeniami pewnych cyfr. Jedna cyfra występuje 2 razy, pozostałe 3 cyfry — raz. Mamy więc rozłączne dwa zbiory: pierwszy zbiór jednoelementowy (w nim jest cyfra powtarzająca się) i drugi zbiór trzyelementowy (tu są niepowtarzające się).
  2. Na ile sposobów można wybrać 4 cyfry do tych zbiorów jw.? Na {6 \choose 1}  {5 \choose 3} = {5 \choose 3} + 5{5 \choose 3} — pierwszy składnik sumy reprezentuje przypadki, w których powtarza się cyfra zero, drugi resztę.
  3. Obliczyliśmy na razie, na ile sposobów możemy dokonać wyboru cyfr, które tworzą liczbę. Każdy taki wybór cyfr generuje \frac{5!}{2!} liczb. Przypominam, że liczby generujemy jako wariacje z powtórzeniami.
  4. Liczby jednakże nie mogą się zaczynać od zera, więc trzeba odrzucić odpowiednie wariacje. Wariacji, w których powtarza się cyfra zero odrzucimy inną ilość niż wariacji, w których zero się nie powtarza.
  5. Jeśli zero się powtarza, to chcemy odrzucić 4! wariacji — bo będą się one składać z początkowego zera i 4 liczb w dowolnej kolejności.
  6. Jeśli to nie zero się powtarza, to wariacje, które odrzucimy będą się składały z początkowego zera i trzech liczb, z których jedna występuje 2 razy. Takich wariacji będzie \frac{4!}{2!}.
  7. Podsumowując: {5 \choose 3} \frac{5!}{2!} - 4! + 
5 \left( {5 \choose 3} \frac{5!}{2!} - \frac{4!}{2!} \right) = 3516
Góra
Kobieta Offline
PostNapisane: 22 lut 2015, o 10:11 
Użytkownik
Avatar użytkownika

Posty: 2505
Pierwotny wynik jest okej, czego "dowodem" może być poniższy kod (język Haskell, odpowiedź 3000):

Kod:
1
2
3
4
5
let liczby = [10000..55555]
let cyfry = nub . map (`mod` 10) . reverse . takeWhile (> 0) . iterate (`div` 10)
let test n = (4 == length k) && (maximum k <= 5) where k = cyfry n
length $ filter test liczby
Góra
Mężczyzna Offline
PostNapisane: 23 lut 2015, o 16:37 
Użytkownik

Posty: 454
Lokalizacja: Warszawa
OK, już wiem, co zrobiłem źle, nie policzyłem przypadków, w których zero nie występuje :D

Teraz też wychodzi mi 3000, ale wklejam rozwiązanie, bo jest ciekawe i pokazuje, że wszystko w kombinatoryce można liczyć na wiele sposobów.

Zbiór wszystkich interesujących nas liczb można podzielić na 3:
  1. gdzie zero występuje dwa razy, np. 00123,
  2. gdzie zero występuje raz, np. 01123,
  3. gdzie zero nie występuje, np. 11234.

Rozwiązaniem będzie więc suma A+B+C. Liczba to ciąg będący permutacją pewnych cyfr. Tak więc ilość liczb spełniających dane warunki to (a) ilość sposobów wyboru cyfr tworzących tę liczbę razy (b) ilość permutacji tych cyfr pomniejszona o (c) ilość liczb rozpoczynających się zerem (bo chcemy mieć pięciocyfrowe): a(b-c).

Składnik (a)

W grupie A wiemy, że zero występuje 2 razy, więc pozostaje nam wybranie 3 cyfr z 5.

W grupie B zero występuje raz, zatem musimy ustalić, która z 5 cyfr występuje dwa razy (5 sposobów) i dobrać resztę cyfr: {4 \choose 2}.

W grupie C nie ma zera, zatem wybieramy powtarzającą się cyfrę na 5 sposobów oraz resztę cyfr {4 \choose 3}.

Składnik (b)

Jest we wszystkich grupach identyczny, wszak we wszystkich grupach mamy 5 elementów, z których 2 się powtarzają, a takich wariacji z powtórzeniami jest \frac{5!}{2!}.

Składnik (c) — liczby zaczynające się od zera

W grupie A jeśli ustawimy zero na początku, to będziemy mogli ustawić pozostałe cyfry na 4! sposobów.

W grupie B — na \frac{4!}{2!}, bo jedna cyfra różna od początkowego zera się powtarza.

W grupie C nie ma zera, więc nie ma żadnych permutacji do odjęcia.

Ostateczne rozwiązanie to zatem: {5 \choose 3} \left( \frac{5!}{2!} - 4!\right) +  
{5 \choose 1}  {4 \choose 2} \left( \frac{5!}{2!} - \frac{4!}{2!}\right) +  
{5 \choose 1}  {4 \choose 2}\left( \frac{5!}{2!}\right) = 3000 \ \blacksquare.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 ilość sposobów usadzenia przy okrągłym stole.  piorko_92  8
 Ilość kombinacji na płaszczyźnie, w przestrzeni...  Bierut  33
 Ilość możliwości w szachach.  Leeq3  16
 Ilość możliwości wylosowania odpowiednich sztuk towaru  trissmerigold  2
 Ile jest liczb 4 cyfrowych  Piczet  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl