Geomania.Org Forumları
Fantezi Cebir => Kombinatorik => Konuyu başlatan: geo - Mart 12, 2013, 05:50:23 ös
-
S1, S2, ..., S20; S={1,2,...,20} kümesinin alt kümeleri olsun.
s(S1)+ s(S2)+ ... + s(S20) > 369 ise S1, S2, ..., S20 kümelerinin 10 tanesi tarafından da içerilen en az 10 sayının bulunduğunu gösteriniz.
-
Genellemeyi bozmadan
20 ≥ s(S1) ≥ s(S2) ≥ ... ≥ s(S20) ≥ 0 olsun.
0 ≤ s(S'1) ≤ s(S'2) ≤ ... ≤ s(S'20)≤ 20 olacaktır.
Soruda verilen eşitsizliği
0 ≤ s(S'1) + s(S'2) + ... + s(S'20) ≤ 30 şekline dönüştürebiliriz.
s(S'10) > 2 ise s(S'11) + s(S'12) + ... + s(S'20) ≥ 33 olacağı için, s(S'10) ≤ 2 dir.
s(S'10) = 2 için s(S'11) + s(S'12) + ... + s(S'20) ≥ 20 olacağı için
s(S'1) + s(S'2) + ... + s(S'9) ≤ 8 ve
s(S'1) + s(S'2) + ... + s(S'9) + s(S'10) ≤ 10 elde edilir.
s(S'10) < 2 için
s(S'1) + s(S'2) + ... + s(S'10) ≤ 10 dur.
Her durumda s(S'1) + s(S'2) + ... + s(S'10) ≤ 10 elde etmiş olduk.
T = S'1∪S'2∪...∪S'10 kümesi en fazla 10 elemanlıdır. Bu durumda, S={1,2,...,20} kümesinden en az 10 eleman T kümesinde yer almaz.
Bu elemanlardan biri a alsun.
i=1,2,...,10 için a ∉ S'i olduğu için a ∈ Si dir.
Demek ki, T kümesinde yer almayan 10 elemandan her biri S1, S2, ..., S10 kümelerinin ortak elemanıdır.
Not: Bu soru, UMO 2. Aşama 2000/3 sorusunun çözüm adımlarından birinin soruya dökülmüş halidir.