kms - fórum o príkladoch

9. príklad 1. letnej série 2008/2009

Zadanie:
Nech $n$ je prirodzené číslo, ktoré je aspoň 3. Nech $A_1, A_2, \dots , A_n$ sú navzájom rôzne podmnožiny množiny $\{1, 2, \dots , n\}$ . Dokážte, že vždy existuje $x \in \{1, 2, \dots. , n\}$ také, že keď z každej množiny $A_1, A_2, \dots , A_n$ odoberieme $x$ , tak novovzniknuté množiny sú tiež navzájom rôzne. (Ak sa $x$ v niektorej z množín nenachádza, tak táto množina ostane rovnaká.)

Naspäť na príklady | Napíš príspevok

bus - 09. 03. 2009 - 23:55:51 z dsl-static-251.213-160-168.telecom.sk

To nikto nedokazete ocenit eleganciu a zbytocnost s ktorou sa da aplikovat vysokoskolska matika na stredoskolsky problem? :D

cituj ma

katka - 09. 03. 2009 - 18:47:25 z 158.195.167.67

mne skor linearnu algebru :)

cituj ma

kamilama - 09. 03. 2009 - 16:58:15 z 158.196.244.87.in-addr.arpa

toto mi skor evokuje nejaku fyziku zmiesanu s informatikou :D:D

cituj ma

mišof - 04. 03. 2009 - 00:04:46 z adsl-dyn70.78-99-45.t-com.sk

Teda napadlo ma také jedno brutálne, až sa hanbím.

Každú podmnožinu $\{1,\dots,n\}$ môžeme reprezentovať ako vektor $n$ núl a jednotiek (zapíšeme, ktoré prvky v nej sú a ktoré nie). Nech $v_1,\dots,v_n$ sú vektory popisujúce $A_1,\dots,A_n$ .

Prvok $x$ je zlý, ak existujú $j,k$ také, že $v_k-v_j$ je $x$ -tý jednotkový vektor -- t.j. vektor, ktorý má všade $0$ , len na $x$ -tej pozícii $1$ .

Uvažujme $n-1$ vektorov: $v_2-v_1,v_3-v_1,\dots,v_n-v_1$ . Táto množina vektorov generuje nejaký najviac $n-1$ rozmerný vektorový priestor $E$ .

V priestore $E$ sú okrem iného aj všetky vektory tvaru $v_k-v_j$ , lebo $(v_k-v_1)-(v_j-v_1)=(v_k-v_j)$ .

Ak by každé $x$ bolo zlé, tak by v $E$ muselo byť všetkých $n$ jednotkových vektorov, a teda by $E$ bol $n$ -rozmerný. To ale nie je pravda.

(Hmm, fakt sa to nedá porovnateľne stručne povedať stredoškolskou matikou? Lama som...)

cituj ma

mišof - 03. 03. 2009 - 23:52:11 z adsl-dyn70.78-99-45.t-com.sk

No tak elegantné riešenie uniká aj mne. Umlátiť to indukciou sa dá, aj cez tie grafy sa dá, ale ono to vyzerá, že by to malo mať nejaké riešenie, že dve vety a hotovo, a také nevidim a nevidííím :P

cituj ma

Kubo - 27. 02. 2009 - 18:11:14 z adsl-dyn50.78-98-16.t-com.sk

Ako ste to robili? lebo mne sa moje riesenie cez grafy zda divne... ale zato spravne ale aj tak divne

cituj ma