ZADATAK :
Od 200 brojeva: 1, 2, 3,...,199, 200, proizvoljno je izabran 101 broj. Dokazati da se među njima nalaze dva takva da je jedan od njih djeljiv drugim.(Zadatak je preuzet iz knjižice 'Najteži zadaci' iz serije 'Matematika u džepu', a u izdanju 'Tehničke knjige', Beograd)
Kako postaviti ovaj zadatak?
Formulacija zadatka navodi nas da bismo trebali promatrati nekakve skupine (skupove) brojeva koji ne bi trebali ići zajedno, dakle koji bi bili "zavisni" jedni od drugih. Na pamet su mi pale ove: prva skupina: svi brojevi od 1 do 200 djeljivi sa 2, druga skupina: brojevi od 1 do 200 djeljivi sa 3,..., četrnaesta skupina: brojevi od 1 do 200 djeljivi sa 14. Problem je ovih skupova što u svakom od njih postoje dva broja koja mogu ići zajedno( koji nisu "zavisni"): npr: iz skupa 2 brojevi 6 i 14, iz skupa 5 brojevi 15 i 70 itd.
Prije gornjega probao sam sa konkretnom skupinom - uzeo sam brojeve 101-200 kojih ima stotinu i sigurno nisu djeljivi jedni sa drugima. Zatim sam od preostalih stotinu(1-100) pokušao ubaciti jednog "nezavisnog" među njih, ali takav se ne može naći. Dakle, ovaj pristup također nije dobar.
Opet se vraćam na prvi algoritam rješavanja - pronaći skupove međusobno "zavisnih"(djeljivih) brojeva, ovog puta radim novu strukturu skupova:
1. grupa: 1, 2, 4, 8, 16, 32, 64, 128
2. grupa: 3, 6, 12, 24, 48, 96, 192
3. grupa: 5, 10, 20, 40, 80, 160
4. grupa: 7, 14, 28, 56, 112
5. grupa: 9, 18, 36, 72, 144
6. grupa: 11, 22, 44, 88, 176
7. grupa: 13, 26, 52, 104
8. grupa: 15, 30, 60, 120
9. grupa: 17, 34, 68, 136
10. grupa: 19, 38, 76, 152
11. grupa: 21, 42, 84, 168
12. grupa: 23, 46, 92, 184
13. grupa: 25, 50, 100, 200
14. grupa: 27, 54, 108
15. grupa: 29, 58, 116
.
.
.
25. grupa: 50, 100, 200
26. grupa: 51, 102
27. grupa: 53, 106
28.grupa: 55, 110
.
.
50. grupa: 99, 198
51. grupa: 101
52. grupa: 103
.
.
.
99. grupa: 197
100. grupa: 199
Vidimo da ovakvih grupa ima točno sto. Jasno je da ako izaberemo proizvoljnih 101 broj, dva moraju pasti u istu grupu, a time će biti i djeljivi.
Ovime smo riješili zadatak, no postoji li jednostavnije rješenje?
Posežem za rješenjem autora - on polazi od zanimljivog teorema: svaki paran broj može se prikazati kao m × 2**k , gdje je k prirodan broj, a m neparan prirodni broj.
Da li smo mogli ovo sami postaviti svojom intuicijom, ili smo to morali već negdje pročitati? Može li se intuicija steći ili se čovjek s njom rodi? Vjerujem da svatko od nas može naći odgovor na to pitanje.
Dakle, da nastavimo:
Neka je S101 skup od 101 proizvoljnog broja od 1 do 200. Rekli smo da se svaki parni broj može napisati kao m x 2 **k. Označimo sad sa E101 skup koji čine brojevi mj i svi neparni brojevi iz skupa S101. Taj skup ima točno 101 element i svi elementi tog skupa su neparni brojevi manji od 200. Kako među prvih 200 brojeva imamo točno sto neparnih, slijedi da u skupu E101 imamo bar dva jednaka broja. Sad opet imamo tri mogućnosti:
1. U skupu S101 imamo dva parna broja oblika m x 2**r i m x 2**s , njihov količnik biti će 2**(r-s) ili 2**(s-r), u oba slučaja prirodan broj.
2. U skupu S101 imamo neparan broj m i paran broj oblika m x 2**r , količnik je u ovom slučaju m.
3. U skupu S101 imamo dva ista neparna broja, oni su djeljivi jedan sa drugim.
Post je objavljen 23.06.2015. u 21:39 sati.