Matematické Fórum

Alan122 · 29. 03. 2010 16:20

Dokážte,že spomedzi n čísel možno vždy vybrat niekolko tak,že ich sučet je delitelný číslom n .
Kto by mi s tým pomohol? díík :)

lukaszh · 29. 03. 2010 17:08

↑ Alan122:

$x_1,x_2,\cdots,x_n\in\mathbb{N}$

Každé číslo z tohto súboru možno zapísať v tvare

$x_j=q_jn+r_j$

kde r_j reprezentuje zvyšok po delení n. Ak sú všetky zvyšky rovnaké r, tak triviálne n delí súčet

$\sum_{j=1}^{n}x_j=n\sum_{j=1}^{n}q_j+nr$

Ak sú zvyšky zastúpené rovnomerne od 0 až po n-1, tak opäť triviálne n delí súčet toho, ktoré dáva zvyšok 1 a toho čo dáva zvyšok n-1. Ak však nemáme zastúpené zvyšky rovnomerne a nie sú rovnaké, tak sa niektoré musia opakovať. Nepotrebujeme pracovať s celým súborom, ale len so zvyškami modulo n.

$r_1,r_2,\cdots,r_n\in\mathbb{Z}/n\mathbb{Z}$

Skonštruujeme n súčtov
$x_1\nlx_1+x_2\nlx_1+x_2+x_3\nl\;\vdots\nlx_1+x_2+x_3+\cdots+x_n$

Po delení číslom n dávajú dva z nich rovnaký zvyšok (pretože zvyškov môže byť najviac n-1). Rozdielom väčšieho a menšieho z nich dostávame hľadaný súčet.

Olin · 29. 03. 2010 17:08

Pokud je některé z čísel dělitelné n, je to triviální. Pokud ne, pak lze řešení nalézt třeba zde (2. úloha).

Matematické Fórum

#1 29. 03. 2010 16:20

Dokaz

#2 29. 03. 2010 17:08

Re: Dokaz

#3 29. 03. 2010 17:08

Re: Dokaz

Zápatí