Cześć,
Ile jest liczb mniejszych od miliona, zakładając, że każda następna cyfra jest większa lub równa poprzedniej? Rozważamy liczby całkowite dodatnie.
Przy tłumaczeniu zadania, wyobraźcie sobie, że tłumaczycie je młodszemu kuzynowi, albo temu kumplowi, debilowi. W internecie nic ciekawego nie znalazłem. Dzięki.
Niemalejące liczby, mniejsze od miliona
-
Anon123Pl
- Użytkownik
- Posty: 6
- Rejestracja: 28 sty 2018, o 18:24
- Płeć: Mężczyzna
- Lokalizacja: WWA
- Podziękował: 1 raz
Re: Niemalejące liczby, mniejsze od miliona
Rozważmy przykładową liczbę, spełniającą warunek zadania: 234456788
Pierwszą cyfrą jest 2, więc następna to liczba z przedziału 2-9. Druga to 3, więc następna to liczba z przedziału 3-9...
Pierwszą cyfrą jest 2, więc następna to liczba z przedziału 2-9. Druga to 3, więc następna to liczba z przedziału 3-9...
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Niemalejące liczby, mniejsze od miliona
Zauważ, że łatwo obliczyć takie układy, najpierw od 1 do 9 jest ich 9.
Teraz od 11 do 99:
Dla liczb dwucyfrowych możliwe są układy:
\(\displaystyle{ xy,aa}\)
Najpierw liczmy te układy gdzie cyfry są różne, jest ich:
\(\displaystyle{ {9 \choose 2}}\)
teraz te gdzie cyfry są równe:
jest ich:
\(\displaystyle{ {9 \choose 1}=9}\)
Dla trzycyfrowych możliwe są takie układy:
\(\displaystyle{ xyz,aax,xaa,aaa}\)
1. Cyfry różne:
\(\displaystyle{ {9 \choose 3}}\)
2.Cyfry dwie równe, trzecia różna, i tu mogą być takie możliwości:
\(\displaystyle{ aax \vee xaa}\)
a jest ich:
\(\displaystyle{ 2 \cdot {9 \choose 2}}\)
Teraz liczmy te których wszystkie cyfry są równe, ich będzie:
\(\displaystyle{ {9 \choose 1}=9}\)
Teraz analogicznie dla czterocyfrowych powinny być układy:
\(\displaystyle{ xyzt,aaxy,xaay,xyaa,aaax,xaaa,aabb,aaaa}\)
Zliczając otrzymamy:
\(\displaystyle{ {9 \choose 4}+3 \cdot {9 \choose 3}+3 \cdot {9 \choose 2}+ {9 \choose 1}}\)
Analogicznie da się zrobić dla układów pięciocyfrowych i sześciocyfrowych,
Dla pięciocyfrowych:
\(\displaystyle{ xyztu,aaxyz,xaayz,xyaaz,xyzaa,aaaxy,xaaay,xyaaa,aaaax,xaaaa,aaabb,aabbb,aabbx,aaxbb,xaabb,aaaaa}\)
Na koniec to wszystko dodać...
I jeszcze w związku z tym ładny wzorek mi się nasunął:
\(\displaystyle{ \sum_{n=1}^{6} \sum_{i=0}^{n-1} {n-1 \choose n-1-i} {9 \choose n-i}=\sum_{n=1}^{6} \sum_{i=0}^{n-1} {n-1 \choose i} {9 \choose n-i}= \sum_{i=0}^{6} {6 \choose i} {9 \choose i}-1}\)
Przyjmujemy, że:
\(\displaystyle{ {0 \choose 0}=1}\)
Spróbować to ładnie teraz zwinąć...
Teraz od 11 do 99:
Dla liczb dwucyfrowych możliwe są układy:
\(\displaystyle{ xy,aa}\)
Najpierw liczmy te układy gdzie cyfry są różne, jest ich:
\(\displaystyle{ {9 \choose 2}}\)
teraz te gdzie cyfry są równe:
jest ich:
\(\displaystyle{ {9 \choose 1}=9}\)
Dla trzycyfrowych możliwe są takie układy:
\(\displaystyle{ xyz,aax,xaa,aaa}\)
1. Cyfry różne:
\(\displaystyle{ {9 \choose 3}}\)
2.Cyfry dwie równe, trzecia różna, i tu mogą być takie możliwości:
\(\displaystyle{ aax \vee xaa}\)
a jest ich:
\(\displaystyle{ 2 \cdot {9 \choose 2}}\)
Teraz liczmy te których wszystkie cyfry są równe, ich będzie:
\(\displaystyle{ {9 \choose 1}=9}\)
Teraz analogicznie dla czterocyfrowych powinny być układy:
\(\displaystyle{ xyzt,aaxy,xaay,xyaa,aaax,xaaa,aabb,aaaa}\)
Zliczając otrzymamy:
\(\displaystyle{ {9 \choose 4}+3 \cdot {9 \choose 3}+3 \cdot {9 \choose 2}+ {9 \choose 1}}\)
Analogicznie da się zrobić dla układów pięciocyfrowych i sześciocyfrowych,
Dla pięciocyfrowych:
\(\displaystyle{ xyztu,aaxyz,xaayz,xyaaz,xyzaa,aaaxy,xaaay,xyaaa,aaaax,xaaaa,aaabb,aabbb,aabbx,aaxbb,xaabb,aaaaa}\)
Na koniec to wszystko dodać...
I jeszcze w związku z tym ładny wzorek mi się nasunął:
\(\displaystyle{ \sum_{n=1}^{6} \sum_{i=0}^{n-1} {n-1 \choose n-1-i} {9 \choose n-i}=\sum_{n=1}^{6} \sum_{i=0}^{n-1} {n-1 \choose i} {9 \choose n-i}= \sum_{i=0}^{6} {6 \choose i} {9 \choose i}-1}\)
Przyjmujemy, że:
\(\displaystyle{ {0 \choose 0}=1}\)
Spróbować to ładnie teraz zwinąć...
-
Anon123Pl
- Użytkownik
- Posty: 6
- Rejestracja: 28 sty 2018, o 18:24
- Płeć: Mężczyzna
- Lokalizacja: WWA
- Podziękował: 1 raz
Re: Niemalejące liczby, mniejsze od miliona
Hmmm, trochę się doedukowałem jeśli chodzi o kombinatorykę i mam pytanie: Czy mój sposób rozumowania jest poprawny?
Zadanie rozbijam na 6 przypadków, zależnych od liczby cyfr: 6, 5, 4, 3, 2, 1.
Dla 6-cyfrowej liczby:
Skupmy się tylko i wyłącznie na wybraniu 6 cyfr ze zbioru 1-9 (0 nigdy się nie trafi), cyfry mogą się powtarzać. Nie obchodzi nas kolejność wylosowania tych liczb, bo i tak można je ustawić tylko w jednej konfiguracji. Więc dla 6 cyfr formuła wygląda następująco:
\(\displaystyle{ {9 + (6-1)\choose 6}}\)
Dla 5 cyfr:
\(\displaystyle{ {9 + (5-1)\choose 5}}\)
.
.
.
Dla 1 cyfry:
\(\displaystyle{ {9 + (1-1)\choose 1}}\)
Wynik to suma wszystkich poprzednich wyników.
Co myślicie o takim sposobie?
Zadanie rozbijam na 6 przypadków, zależnych od liczby cyfr: 6, 5, 4, 3, 2, 1.
Dla 6-cyfrowej liczby:
Skupmy się tylko i wyłącznie na wybraniu 6 cyfr ze zbioru 1-9 (0 nigdy się nie trafi), cyfry mogą się powtarzać. Nie obchodzi nas kolejność wylosowania tych liczb, bo i tak można je ustawić tylko w jednej konfiguracji. Więc dla 6 cyfr formuła wygląda następująco:
\(\displaystyle{ {9 + (6-1)\choose 6}}\)
Dla 5 cyfr:
\(\displaystyle{ {9 + (5-1)\choose 5}}\)
.
.
.
Dla 1 cyfry:
\(\displaystyle{ {9 + (1-1)\choose 1}}\)
Wynik to suma wszystkich poprzednich wyników.
Co myślicie o takim sposobie?