Simpatičan zadačić

Simpatičan zadačić 22.10.2005. u 12:58 · pre 255 meseci #1

Evo jednog simpatičnog zadačića koji je svojevremeno predlagan za zadatak na saveznom takmičenju:
U desetocifrenom broju $\quad \overline{a_{1}a_{2}a_{3}a_{4}a_{5}a_{6}a_{7}a_{8}a_{9}a_{10}} \quad$ , $a_{1}$ je broj nula u dekadnom zapisu tog broja, $a_{2}$ je jednak broju jedinica u zapisu, itd., $a_{10}$ je jednak broju devetki. Odrediti taj broj.

Potpis

"Verovatno da preko nje mnoge sile kontrolišu mnogo šta..." - GANDOR
"Kada bi ljudski mozak bio tako jednostavan da bismo mogli da ga shvatimo, onda bismo mi bili toliko glupi da ga ipak ne bismo mogli shvatiti."

Re: Simpatičan zadačić 23.10.2005. u 11:49 · pre 255 meseci #2

Upostenje:
Naci sve konacne nizove $(x_0, x_1, ..., x_n)$, tako da za svako $0 \leq i \leq n$, $x_i$ predstavlja koliko se puta broj $j$ javlja u nizu.

Resenja su:
(2, 0, 2, 0)
(1, 2, 1, 0)
(2, 1, 2, 0, 0)
(k, 2, 1, 0, 0, ..., 0, 1, 0, 0, 0), za $k \geq 3$.

Pozdravce

Potpis

Math is like love. A simple idea but it can get complicated.

Re: Simpatičan zadačić 23.10.2005. u 12:56 · pre 255 meseci #3

Radi jednostavnosti, koristiću ipak sledeće oznake:
$\overline {a_0 a_1\ldots a_9}$ , gde je $a_k$ broj pojavljivanja cifre $k$ u dekadnom zapisu traženog broja.
Jasno je da mora biti $\displaystyle\sum_{i=0}^9 a_i=10$ .

Primetimo zatim da ako je $a_n\ge 2$ imamo da postoje barem dve različite cifre koje se pojavljuju po $n$ puta, ali cifara u zapisu ima samo $10$ , pa mora biti $2\cdot n\le 10$ tj. $n\le 5$ .
Drugim rečima, za $n\ge 6$ je $a_n\le 1$ .

Ako bi bilo $a_9=1$ , onda bi postojalo $k<9$ takvo da je $a_k=9$ . Međutim, ovo poslednje bi značilo da imamo, $9$ cifara $k$ , pa lako sledi da mora biti $k=1$ (za preostalih $8$ ne možemo staviti cifru van skupa $\{1,9\}$ , jer nam treba $9$ istih cifara, pa zbog $k<9$ sledi da je $k=1$ ). Sada, je lako videti da smo dobili broj koji ne zadovoljava uslove zadatka (npr. dobijamo da je $a_0=1$ a u zapisu nema ni jedna $0$ ) pa je to kontradikcija.
Dakle, mora biti $a_9=0$

Ako bi bilo $a_8=1$ , onda bi postojalo $k<8$ takvo da je $a_k=8$ . Ovo poslednje implicira postojanje tačno $8$ pojavljivanja neke od cifara $\{0,1,\ldots ,7\}$ . Budući da je $a_9=0$ i po pretpostavci $a_8=1$ imamo da je $a_0\ge 1$ i $a_1\ge 1$ , sledi da moramo staviti da je nekih $7$ od cifara $a_0,a_1,\ldots ,a_7$ međusobno jednako, pa mora biti $k \in \{0,1\}$ , a otuda sledi (zbog $a_0\ge 1$ i $a_1 \ge 1$ ) da u zapisu ipak ne učestvuju samo cifre $0,1$ i $8$ , što je kontradikcija.
Dakle, mora biti $a_8=0$

Ako bi bilo $a_7=1$ , onda bi postojalo $k<7$ takvo da je $a_k=7$ . Na osnovu prethodnih zaključaka i na osnovu pretpostavke, važi $a_0\ge 2$ i $a_1\ge 1$ , slično kao i ranije zaključujemo da moramo uzeti da je $k\in \{0,1\}$ . Međutim, šta god uzeli za $k$ , dobićemo da su cifre $a_2,\ldots, a_6$ pozitivne, što znači da cifre $0,1$ i $7$ nisu jedine u zapisu, a to je kontradikcija.
Dakle, mora biti $a_7=0$

Neka je $a_6=1$ , onda postoji $k<6$ takvo da je $a_k=6$ . Iz prethodnih razmatranja sledi da je $a_0\ge 3$ i $a_1\ge 1$ . Kao i ranije, sledi da je $k\in \{0,1\}$ . Ali, ne može biti $k=1$ tj. $a_1=6$ , jer bi zbog $a_0\ge 3$ i $a_6=1$ morali da za preostale $4$ cifre $a_2,\ldots ,a_5$ stavimo $5$ jedinica, što je nemoguće. Dakle, mora biti $k=0$ tj. $a_0=6$ .
Ostaje nam da otkrijemo cifre $a_1,\ldots ,a_5$ . Iz $a_0=6$ i $a_7=a_8=a_9=0$ sledi da su među ciframa $a_1,\ldots ,a_5$ tačno tri jednake $0$ , tj. tačno dve cifre nisu nula. Kako je $\displaystyle\sum_{i=0}^9 a_i=10$ iz prethodnog sledi, da je $a_{k_1}+a_{k_2}=3$ za neke $1\le k_1,k_2\le 5$ . Sada imamo da je $a_k\le 2$ za $1\le k\le 5$ . Odatle, vidimo da mora biti $a_3=a_4=a_5=0$ , jer bi u protivnom dobili da se neka od cifara $a_1,\ldots ,a_5$ javlja $3,4$ ili $5$ puta (što je kontradikcija).
Sada, je lako proveriti da je $a_1=2$ i $a_2=1$ .

Dakle, dobili smo broj $6210001000$ .

Dokažimo da je nađeni broj jedinstven.

Za sada znamo da je $a_7=a_8=a_9=0$ . Pretpostavimo zato da je $a_6=0$ .
Očigledno je da je $a_5<3$ . Međutim, videćemo ubrzo da $a_5\not\in\{0,1,2\}$ , što će biti dovoljno za dokaz jedinstvenosti trženog broja.

Ako bi bilo $a_5=2$ , sledilo bi da postoje dva pojavljivanja cifre $5$ u zapisu, što znači da se neke dve različite cifre pojavljuju po $5$ puta u zapisu, što je kontradikcija, jer smo dobili da u zapisu učestvuju cifre $0,2$ i $5$ .

Ako bi bilo $a_5=1$ , sledilo bi da postoji $k<5$ takvo da je $a_k=5$ , kao i ranije, (zbog $a_0\ge 4$ i $a_1\ge 1$ ) mora biti $k=0$ . Sada, sledi da je $a_1+\ldots +a_4=4$ , a pošto je $a_0=5$ , među sabircima je tačno jedna $0$ , onda za neke $1\le k_1,k_2,k_3\le 4$ važi $a_{k_1}+a_{k_2}+a_{k_3}=4$ , pa je $a_k\le 2$ za $1\le k\le 4$ . Znači, mora biti $a_4=0$ (u protivnom bi se neka od cifara $a_1,\ldots ,a_4$ javljala $4$ puta, što je kontradikcija). E sad, jedina particija broja $4$ , koja zadovoljava tražene uslove je $1+1+2=4$ , međutim, kako god dodelili te brojeve ciframa $a_1,a_2$ i $a_3$ , dobijamo da u zapisu učestvuju ukupno $3$ jedinice, a $a_1\le 2$ , što je kontradikcija.

Ako bi bilo $a_5=0$ , sledilo bi $a_0\ge 5$ , što je u kontradikciji sa $a_5=\ldots=a_9=0$ .

Bez obzira što je rešenje ovako ružno, mislim da je zadatak fantastičan, jer pokazuje kakvi se perverzni skupovi kriju u $\omega$ .

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Simpatičan zadačić 24.10.2005. u 11:36 · pre 255 meseci #4

Citat:

cassey: Upostenje:
Naci sve konacne nizove $(x_0, x_1, ..., x_n)$, tako da za svako $0 \leq i \leq n$, $x_i$ predstavlja koliko se puta broj $j$ javlja u nizu.

Resenja su:
(2, 0, 2, 0)
(1, 2, 1, 0)
(2, 1, 2, 0, 0)
(k, 2, 1, 0, 0, ..., 0, 1, 0, 0, 0), za $k \geq 3$.

Pozdravce

Uh, ovo baš nije čitljivo! Mislim da si hteo da kažeš sledeće:

Naći sve konačne nizove $(x_0,...,x_n)$ , tako da za svako $0 \leq i \leq n$ , $x_i$ predstavlja koliko se puta broj $i$ javlja u nizu.

Rešenja su:
(2,0,2,0)
(1,2,1,0)
(2,1,2,0,0)
(k,2,1,0,0,...,0,1,0,0,0), za $k \geq 3$ .

Potpis

"Verovatno da preko nje mnoge sile kontrolišu mnogo šta..." - GANDOR
"Kada bi ljudski mozak bio tako jednostavan da bismo mogli da ga shvatimo, onda bismo mi bili toliko glupi da ga ipak ne bismo mogli shvatiti."

Re: Simpatičan zadačić 24.10.2005. u 20:24 · pre 255 meseci #5

Neka je $\overline{a_0a_1 \ldots a_9}$ trazeni broj. Ocigledno je $a_0 > 0$ . Oznacimo sa $k$ broj pozitivnih brojeva medju $a_1,a_2 \ldots ,a_9$ . Tada je

$a_1+a_2+ \ldots +a_9=k+1$ .

Kako je na levoj strani $k$ pozitivnih sabiraka ciji je zbir $k+1$ , jedan od njih jednak je 2, dok su preostalih $k-1$ jednaki 1. Iz toga sledi da jedino $a_0$ moze biti $>2$ . Takodje, ako je $a_i>0$ za neko $i>2$ , tada je $i=a_0$ . Takvih $i$ je samo jedno i pritom je $a_i=1$ .

Iz navedenog sledi da je $1\leq k \leq 3$ . Nije tesko ustanoviti da su slucajevi $k=1$ i $k=2$ nemoguci. Ostaje $k=3$ .

Neka je $a_0=s$ , $s>2$ . Tada je $a_s=1$ . Jedine preostale nenula cifre su $a_1$ i $a_2$ . Mogucnost $a_1=1$ otpada, jer je vec $a_s=1/tex]. Ostaje a_1=2$ i $a_2=1$ .
Trazeni broj ima oblik $\overline{s21\underbrace{0\ldots 0}_{s-3}1000}$ . S obzirom da je desetocifren, sledi $s=6$ i broj je 6210001000.

_{Bojan Bašić: popravljen [tex] tag}

_{[Ovu poruku je menjao Bojan Basic dana 29.10.2005. u 13:04 GMT+1]}

Srodne teme