[es] - Simpatičan zadačić

darkon
Darko Novakovic
Istrazivac, IMP
Beograd

Član broj: 13647
Poruke: 166
*.226.17.bitsyu.net.

Jabber: darkon@elitesecurity.org

+1 Profil

Simpatičan zadačić

^{22.10.2005. u 12:58 - pre 236 meseci}

Evo jednog simpatičnog zadačića koji je svojevremeno predlagan za zadatak na saveznom takmičenju:
U desetocifrenom broju

je broj nula u dekadnom zapisu tog broja,

je jednak broju jedinica u zapisu, itd.,

je jednak broju devetki. Odrediti taj broj.

"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."

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*

+1 Profil

Re: Simpatičan zadačić

^{23.10.2005. u 11:49 - pre 236 meseci}

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

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

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.ptt.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Simpatičan zadačić

^{23.10.2005. u 12:56 - pre 236 meseci}

Radi jednostavnosti, koristiću ipak sledeće oznake:

, gde je

broj pojavljivanja cifre

u dekadnom zapisu traženog broja.
Jasno je da mora biti

.

Primetimo zatim da ako je

imamo da postoje barem dve različite cifre koje se pojavljuju po

puta, ali cifara u zapisu ima samo

, pa mora biti

tj.

.
Drugim rečima, za

.

Ako bi bilo

, onda bi postojalo

takvo da je

. Međutim, ovo poslednje bi značilo da imamo,

cifara

, pa lako sledi da mora biti

(za preostalih

ne možemo staviti cifru van skupa

, jer nam treba

istih cifara, pa zbog

sledi da je

). Sada, je lako videti da smo dobili broj koji ne zadovoljava uslove zadatka (npr. dobijamo da je

a u zapisu nema ni jedna

) pa je to kontradikcija.
Dakle, mora biti

Ako bi bilo

, onda bi postojalo

takvo da je

. Ovo poslednje implicira postojanje tačno

pojavljivanja neke od cifara

. Budući da je

i po pretpostavci

imamo da je

, sledi da moramo staviti da je nekih

od cifara

međusobno jednako, pa mora biti

, a otuda sledi (zbog

) da u zapisu ipak ne učestvuju samo cifre

, što je kontradikcija.
Dakle, mora biti

Ako bi bilo

, onda bi postojalo

takvo da je

. Na osnovu prethodnih zaključaka i na osnovu pretpostavke, važi

, slično kao i ranije zaključujemo da moramo uzeti da je

. Međutim, šta god uzeli za

, dobićemo da su cifre

pozitivne, što znači da cifre

nisu jedine u zapisu, a to je kontradikcija.
Dakle, mora biti

Neka je

, onda postoji

takvo da je

. Iz prethodnih razmatranja sledi da je

. Kao i ranije, sledi da je

. Ali, ne može biti

tj.

, jer bi zbog

morali da za preostale

cifre

stavimo

jedinica, što je nemoguće. Dakle, mora biti

tj.

.
Ostaje nam da otkrijemo cifre

. Iz

sledi da su među ciframa

tačno tri jednake

, tj. tačno dve cifre nisu nula. Kako je

iz prethodnog sledi, da je

za neke

. Sada imamo da je

. Odatle, vidimo da mora biti

, jer bi u protivnom dobili da se neka od cifara

javlja

ili

puta (što je kontradikcija).
Sada, je lako proveriti da je

.

Dakle, dobili smo broj

.

Dokažimo da je nađeni broj jedinstven.

Za sada znamo da je

. Pretpostavimo zato da je

.
Očigledno je da je

. Međutim, videćemo ubrzo da

, što će biti dovoljno za dokaz jedinstvenosti trženog broja.

Ako bi bilo

, sledilo bi da postoje dva pojavljivanja cifre

u zapisu, što znači da se neke dve različite cifre pojavljuju po

puta u zapisu, što je kontradikcija, jer smo dobili da u zapisu učestvuju cifre

.

Ako bi bilo

, sledilo bi da postoji

takvo da je

, kao i ranije, (zbog

) mora biti

. Sada, sledi da je

, a pošto je

, među sabircima je tačno jedna

, onda za neke

važi

, pa je

. Znači, mora biti

(u protivnom bi se neka od cifara

javljala

puta, što je kontradikcija). E sad, jedina particija broja

, koja zadovoljava tražene uslove je

, međutim, kako god dodelili te brojeve ciframa

, dobijamo da u zapisu učestvuju ukupno

jedinice, a

, što je kontradikcija.

Ako bi bilo

, sledilo bi

, što je u kontradikciji sa

.

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

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

Odgovor na temu

darkon
Darko Novakovic
Istrazivac, IMP
Beograd

Član broj: 13647
Poruke: 166
*.rcub.bg.ac.yu.

Jabber: darkon@elitesecurity.org

+1 Profil

Re: Simpatičan zadačić

^{24.10.2005. u 11:36 - pre 236 meseci}

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