Matematické Fórum

bradek · 11. 03. 2011 20:38

Chtěl bych poprosit ještě o radu s tímto příkladem.

Předem díky.

check_drummer · 12. 03. 2011 08:56

Zkusil bych vyjádřit rekurentně hledaný počet $p_n$ pro n ciferná čísla.

tomas.fejfar

No, jenže tam dělá problém to, že to neni $\{0000,...,9999\}$ ale $\{1000,...,9999\}$ . Takže bych řek, že to přes to nepůjde. Resp půjde ale bude to brutálně složité, ne? resp., že ta řada bude platná pro $N - \{1\}$ a tím pádem na dva její členy bys musel mít dvojciferné a trojciferné. A trojciferných je tolik, že se to IMO nedá spočíst brute-force. Takže nmáš z čeho odvozovat tu řadu :(

claudia

Ad a)

EDIT: nesprávné řešení, viz níže

Já bych to spočítala nejprve pro $\{0000,\ldots,9999\}$ a pro $\{000,\ldots,999\}$ a pak výsledky odečetla.

Pokud musí číslice tvořit rostoucí či klesající poslounpost, je zřejmé, že si žádné dvě číslice nejsou rovny. Tedy tvoří podmnožinu množiny číslic $\{0,\ldots,9\}$ velikosti 4 resp. 3. Takových podmnožin existuje $\binom{10}{4}$ , resp. $\binom{10}{3}$ a z každé takové množiny číslic lze jejich seřazením podle velikosti získat číslo (naopak každé číslo mající požadovanou vlastnost zjevně odpovídá takové podmnožině). Protože posloupnosti mohou být rostoucí/klesající, máme čísel dvakrát více než podmnožin. Výsledek je tedy $2\binom{10}{4}-2\binom{10}{3}$ .

Ad b)

Pokud mi nic zásadního neuniká, lze aplikovat podobnou myšlenku, jen s multimnožinami (resp. kombinacemi s opakováním).

tomas.fejfar · 12. 03. 2011 19:46

ad a) geniálně jednoduché :D Díky. Zcela zásadní úvaha je ta, že se jedná o kombinace (že se cifry nemohou opakovat)

ad b) tady myslím, že existuje snažší řešení. Celkový počet čísel je 9000 ( $0000 ... 9999 [n=10000]$ bez $0000....0999 [n=1000]$ ) z nichž N tvoří rostoucí nebo klesající posloupnost, pak je patrné, že neklesající nebo nestoupající posloupnost bude tvořit právě 9000-N čísel - tj. doplněk do celkového počtu. Ne?

claudia · 12. 03. 2011 20:04

To ale předpokládáš, že každé číslo je buď a) rostoucí nebo b) klesající nebo c) nerostoucí nebo d) neklesající (a žádná další možnost není). Kam bys pak zařadil třeba číslo 1324?

tomas.fejfar

Mám zmatek v pojmech (přesněj řečeno v definici toho, že je něco neklesající / nestoupající) :) Poradil jsem se s wiki a zjistil, jak jsem mimo ;) Sry x)

Myslel jsem, že naklesající je definováno jako posloupnost kde kde ai není < a i-1.

check_drummer

↑ tomas.fejfar:
Jak jsem psal, myslím n ciferné číslo, tj. ne číslo začínající 0 - např. tedy pro n=4 sem číslo 0589 nepatří.
Nakonec je nutné definovat p(n,k) - počet uvedených n ciferných čísel začínajících číslicí k, p(n) samotné nestačí,
získáme p(1,k)=1, p(2,k)=9-k, p(3,k)=(9-k).(8-k)/2, p(4,k)=(9-k)(8-k)(7-k)/6, p(5,k)=(9-k)(8-k)(7-k)(6-k)/24, což pro k=0 dává hledané řešení.

check_drummer · 12. 03. 2011 22:14

claudia napsal(a):
Ad a)

Já bych to spočítala nejprve pro $\{0000,\ldots,9999\}$ a pro $\{000,\ldots,999\}$ a pak výsledky odečetla.

Nestačí uvažovat jen cifry 1 až 9 a tedy kombinace $\binom{9}{4}$ ?

Stýv · 13. 03. 2011 00:05

a) napíšu si za sebe číslice 123...9, vyberu 4 z nich a mám čtyřciferný číslo, rostoucí cifry. tedy C(9,4) možností
napíšu si 987...0, vyberu čtyři číslice, mám klesající posloupost. C(10,4) možností

claudia

↑ check_drummer:

Ano, přinejmenším pro rostoucí posloupnosti máš pravdu (a já mám výše chybu). Pro rostoucí to má být

$\binom{10}{4}-\binom{9}{3}=\binom{9}{4}$

protože není žádoucí, aby některá z těch odečítaných trojciferných začínala nulou (takové by neodpovídala žádná čtyřciferná, protože by musela mít dvě nuly za sebou).

A pro neklesající tam to odečtení být vůbec nemá, protože mezi vygenerovanými žádné číslo < 1000 nedostaneme.

Matematické Fórum

#1 11. 03. 2011 20:38

posloupnosti2

#2 12. 03. 2011 08:56

Re: posloupnosti2

#3 12. 03. 2011 18:31 — Editoval tomas.fejfar (12. 03. 2011 18:33)

Re: posloupnosti2

#4 12. 03. 2011 18:45 — Editoval claudia (13. 03. 2011 00:09)

Re: posloupnosti2

#5 12. 03. 2011 19:46

Re: posloupnosti2

#6 12. 03. 2011 20:04

Re: posloupnosti2

#7 12. 03. 2011 21:20 — Editoval tomas.fejfar (12. 03. 2011 21:22)

Re: posloupnosti2

#8 12. 03. 2011 21:36 — Editoval check_drummer (12. 03. 2011 22:12)

Re: posloupnosti2

#9 12. 03. 2011 22:14

Re: posloupnosti2

claudia napsal(a):

#10 13. 03. 2011 00:05

Re: posloupnosti2

#11 13. 03. 2011 00:08 — Editoval claudia (13. 03. 2011 00:09)

Re: posloupnosti2

Zápatí