Točno
23. srpnja 2014. 02:49 (9 godine, 12 mjeseci)
Sakrij rješenje
Neka je skup
![S](/media/m/c/6/3/c63593c3ec0773fa38c2659e08119a75.png)
takav da sadrži
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
cijelih brojeva, i niti jedan element
![S](/media/m/c/6/3/c63593c3ec0773fa38c2659e08119a75.png)
nije djeljiv s
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
. Dokaži da je moguće naći podskup od
![S](/media/m/c/6/3/c63593c3ec0773fa38c2659e08119a75.png)
takav da je suma svih elemenata podskupa djeljiva s
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
.
%V0
Neka je skup $S$ takav da sadrži $n$ cijelih brojeva, i niti jedan element $S$ nije djeljiv s $n$. Dokaži da je moguće naći podskup od $S$ takav da je suma svih elemenata podskupa djeljiva s $n$.
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Neka je
![S_1](/media/m/7/7/e/77ed808eaa71be903a10ce754f90a904.png)
prvi broj.
![S_2](/media/m/c/1/1/c11855875777bfedb764b27ccc108413.png)
suma prva dva broja
![S_3](/media/m/b/5/a/b5a32762b99c5b833ab182d93fc941b4.png)
suma prva tri broja.
....
![S_n](/media/m/c/2/e/c2e97c6b8d807599d8398c14e4ac95fc.png)
suma svih brojeva.
Ako neka dva
![S_i](/media/m/9/f/d/9fd19263a5663142484a86f39fb49833.png)
i
![S_j](/media/m/d/5/b/d5b84faba9d7d2f91f28a9b0432e7262.png)
daju isti ostatak pri djeljenju s
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
, tada je skup elemenata od
![i+1](/media/m/8/f/3/8f35f9624c94458dd9bff544fa1e6129.png)
-og do
![j](/media/m/7/9/e/79ebb10f98eb80d16b0c785d9d682a72.png)
-tog u sumi djeljiv s
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
.
Ako niti jedna dva nedaju isti ostatak, onda neki od
![S_i](/media/m/9/f/d/9fd19263a5663142484a86f39fb49833.png)
daje ostatak
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
, pa je on trazeni podskup.
%V0
Neka je $S_1$ prvi broj.
$S_2$ suma prva dva broja
$S_3$ suma prva tri broja.
....
$S_n$ suma svih brojeva.
Ako neka dva $S_i$ i $S_j$ daju isti ostatak pri djeljenju s $n$, tada je skup elemenata od $i+1$-og do $j$-tog u sumi djeljiv s $n$.
Ako niti jedna dva nedaju isti ostatak, onda neki od $S_i$ daje ostatak $0$, pa je on trazeni podskup.
28. srpnja 2014. 12:55 | ikicic | Točno |