Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Maradona126
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 7 gru 2020, o 14:34
Płeć: Mężczyzna
wiek: 21
Podziękował: 29 razy

Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: Maradona126 » 14 kwie 2021, o 15:55

Cześć,

Potrzebuje odpowiedzi a najlepiej rozwiązania jeśli mój wynik 1246 jest nieprawidłowy.

Zadanie:
Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30.

Za pomoc BARDZO DZIĘKUJĘ :)
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 3303
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 75 razy
Pomógł: 1139 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: Janusz Tracz » 14 kwie 2021, o 16:45

A jak to robiłeś? Moim zdaniem nie ma takich liczb zbyt dużo (tak na oko). Skoro mają to być liczby naturalne mniejsze niż \(\displaystyle{ 10000}\) to są to po prostu liczby cztero cyfrowe. Oczywiście jakby jakaś cyfr była zerem to już nie ma seans aby cyfry sumowały się do \(\displaystyle{ 30}\), a nawet jeśli jakaś cyfra jest jedynką lub dwójką to już odpada. Więc mamy tylko liczby cztero cyfrowe w których cyframi są elementy \(\displaystyle{ \left\{ 3,...,9\right\} }\). Można więc zliczyć ile jest rozwiązań równania \(\displaystyle{ a_1+a_2+a_3+a_4=30}\) w liczbach \(\displaystyle{ \left\{ 3,...,9\right\} }\). A to bez funkcji tworzących wydaje się raczej żmudne. Z funkcjami tworzącymi sprawdzamy czym jest \(\displaystyle{ \left[ x^{30}\right]\left( x^3+x^4+...+x^9\right)^4=84 }\).

Maradona126
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 7 gru 2020, o 14:34
Płeć: Mężczyzna
wiek: 21
Podziękował: 29 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: Maradona126 » 14 kwie 2021, o 17:00

Janusz Tracz pisze:
14 kwie 2021, o 16:45
A jak to robiłeś? Moim zdaniem nie ma takich liczb zbyt dużo (tak na oko). Skoro mają to być liczby naturalne mniejsze niż \(\displaystyle{ 10000}\) to są to po prostu liczby cztero cyfrowe. Oczywiście jakby jakaś cyfr była zerem to już nie ma seans aby cyfry sumowały się do \(\displaystyle{ 30}\), a nawet jeśli jakaś cyfra jest jedynką lub dwójką to już odpada. Więc mamy tylko liczby cztero cyfrowe w których cyframi są elementy \(\displaystyle{ \left\{ 3,...,9\right\} }\). Można więc zliczyć ile jest rozwiązań równania \(\displaystyle{ a_1+a_2+a_3+a_4=30}\) w liczbach \(\displaystyle{ \left\{ 3,...,9\right\} }\). A to bez funkcji tworzących wydaje się raczej żmudne. Z funkcjami tworzącymi sprawdzamy czym jest \(\displaystyle{ \left[ x^{30}\right]\left( x^3+x^4+...+x^9\right)^4=84 }\).
Rozwiązywałem to analogicznie z rozwiązaniem zadania gdzie liczby są mniejsze 1000 i ich suma cyfr jest równa 20, ale te rozwiązanie było trochę zawiłe i nie zrozumiałe dla mnie, więc mogłem się trochę pogubić.

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 3303
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 75 razy
Pomógł: 1139 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: Janusz Tracz » 14 kwie 2021, o 17:04

aha... ale jak rozwiązałeś to zadanie?

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7974
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 262 razy
Pomógł: 3124 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: kerajs » 14 kwie 2021, o 17:18

Gdyby wypisać możliwe zestawy cyfr: \(\displaystyle{ (9,9,9,3), (9,9,8,4), (9,9,7,5), (9,9,6,6), (9,8,8,5), (9,8,7,6), (9,7,7,7), (8,8,8,6),(8,8,7,7) }\) to sumując ich permutacje dostaje się ten sam wynik \(\displaystyle{ 4+12+12+6+12+24+4+4+6=84}\).

Maradona126
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 7 gru 2020, o 14:34
Płeć: Mężczyzna
wiek: 21
Podziękował: 29 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: Maradona126 » 14 kwie 2021, o 17:20

Janusz Tracz pisze:
14 kwie 2021, o 17:04
aha... ale jak rozwiązałeś to zadanie?
No właśnie podobnie jak napisałeś na początku \(\displaystyle{ x _{1}+x _{2}+x _{3}+x_{4}=30 }\)
Potem coś takiego: \(\displaystyle{ (x _{1}-3) (x _{2}-3) (x _{3}-3) (x _{4}-3)=30-12=18 }\)

Wkładamy po 3 przedmioty do każdego pudełka i odpowiadamy na pytanie.
Na ile sposobów można rozłożyć 18 przedmiotów w czterech rozróżnialnych pudełkach, tak aby w żadnym nie znajdywało się więcej niż 6 przedmiotów.

Wszystkich rozmieszczeń jest \(\displaystyle{ {18+4-1 \choose 4-1}=1330}\)

Takich rozmieszczeń, że w jednym pudełku jest co najmniej 7 przedmiotów.

\(\displaystyle{ 4[{6 \choose 1}+{5 \choose 1}+{4 \choose 1}+{3 \choose 1}+{2\choose 1}+{1 \choose 1}]=4 \cdot 21=84 }\)

\(\displaystyle{ 1330-84=1246}\)

Zapis mocno skrócony.

Ale to na pewno jest błędne rozwiązanie i sam nie wiem co z czego tutaj.

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 3303
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 75 razy
Pomógł: 1139 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: Janusz Tracz » 14 kwie 2021, o 17:28

Maradona126 pisze:
14 kwie 2021, o 17:20
\(\displaystyle{ (x _{1}-3) (x _{2}-3) (x _{3}-3) (x _{4}-3)=30-12=18 }\)
Tam raczej powinny być \(\displaystyle{ +}\). Poza tym tu masz ograniczenie górne na \(\displaystyle{ x_i}\) bo to są cyfry. Więc nie interesuje Cię liczba rozwiązań w liczbach naturalnych tylko w cyfrach. Z tego powodu wzór na takie rozmieszczenia tu nie działa bezpośrednio. W sensie widzę, że to zapisałeś ale nie wiem skąd wziąłeś te wzory.
Ostatnio zmieniony 14 kwie 2021, o 17:30 przez Janusz Tracz, łącznie zmieniany 1 raz.

Maradona126
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 7 gru 2020, o 14:34
Płeć: Mężczyzna
wiek: 21
Podziękował: 29 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: Maradona126 » 14 kwie 2021, o 17:30

Janusz Tracz pisze:
14 kwie 2021, o 17:28
Maradona126 pisze:
14 kwie 2021, o 17:20
\(\displaystyle{ (x _{1}-3) (x _{2}-3) (x _{3}-3) (x _{4}-3)=30-12=18 }\)
Tam raczej powinny być \(\displaystyle{ +}\). Poza tym tu masz ograniczenie górne na \(\displaystyle{ x_i}\) bo to są cyfry. Więc nie interesuje Cię liczba rozwiązań w liczbach naturalnych tylko w cyfrach. Z tego powodu wzór na takie rozmieszczenia tu nie działa bezpośrednio.
Więc jak to zrobić lepiej?

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 3303
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 75 razy
Pomógł: 1139 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: Janusz Tracz » 14 kwie 2021, o 17:31

Maradona126 pisze:
14 kwie 2021, o 17:30
Więc jak to zrobić lepiej?
No tak jak ja albo kerajs który pokazał elementarne rozwiązania.

Maradona126
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 7 gru 2020, o 14:34
Płeć: Mężczyzna
wiek: 21
Podziękował: 29 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: Maradona126 » 14 kwie 2021, o 17:32

Janusz Tracz pisze:
14 kwie 2021, o 17:31
Maradona126 pisze:
14 kwie 2021, o 17:30
Więc jak to zrobić lepiej?
No tak jak ja albo kerajs który pokazał elementarne rozwiązania.
Ok, Dzięki :)

vpprof
Użytkownik
Użytkownik
Posty: 471
Rejestracja: 11 paź 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 23 razy
Pomógł: 63 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: vpprof » 3 maja 2021, o 21:38

Janusz Tracz pisze:
14 kwie 2021, o 16:45
A to bez funkcji tworzących wydaje się raczej żmudne. Z funkcjami tworzącymi sprawdzamy czym jest \(\displaystyle{ \left[ x^{30}\right]\left( x^3+x^4+...+x^9\right)^4=84 }\).
Mam pytanie: czy ten sposób z funkcjami tworzącymi jest do policzenia jakoś szybko na papierze czy tylko w programie do wyliczeń symbolicznych? Krótko mówiąc, czy bez sprzętu jest jakaś lepsza metoda niż wymnażanie tych czterech nawiasów?

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 3303
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 75 razy
Pomógł: 1139 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: Janusz Tracz » 3 maja 2021, o 21:57

Raczej trzeba liczyć programem jak szybko chcemy odpowiedź ale są pewne sztuczki: Multinomial theorem

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9517
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 38 razy
Pomógł: 2116 razy

Re: Ile jest liczb naturalnych mniejszych od 10000, których suma cyfr jest równa 30

Post autor: Dasio11 » 8 maja 2021, o 18:48

Liczby czterocyfrowe o sumie cyfr równej \(\displaystyle{ 30}\) to dokładnie liczby postaci \(\displaystyle{ 9999-x}\), gdzie \(\displaystyle{ x}\) jest liczbą czterocyfrową o sumie cyfr równej \(\displaystyle{ 6}\). Tych drugich zaś jest tyle co rozwiązań równania \(\displaystyle{ x_1+x_2+x_3+x_4 = 6}\) w liczbach całkowitych nieujemnych, czyli oczywiście \(\displaystyle{ \binom{9}{3} = 84}\).

ODPOWIEDZ