Tübitak Lise 2. Aşama 2017 Soru 1

[Eray]

$25$ çeşit yemeğiyle ünlü bir $A$ köyünde yapılacak bir düğün için $2017$ kişinin yaşadığı komşu $B$ köyünden düğüne bazı kişiler davet edilecektir. $B$ köyündeki her bir kişi bu $25$ çeşit yemekten en az birini sevmektedir ve her yemek için $B$ köyünde o yemeği seven en az bir kişi bulunmaktadır. $B$ köyünden düğüne davet edilen kişilerin kümesine, her bir yemek davet edilen en az bir kişi tarafından seviliyorsa, uygun davetli listesi diyelim. Her uygun davetli listesinden en az bir eleman içeren bir kümeye ise kamber grubu diyelim. Kendisi dışında hiçbir altkümesi kamber grubu olmayan herhangi bir kamber grubundaki herkesin sevdiği bir yemek bulunduğunu gösteriniz.

(Selim Bahadır)

[nk6]

Söz konusu grup $\{ A_1, A_2, \ldots , A_k \}$ olsun.

İddia 1: Buradan sadece $A_1$ i içeren bir uygun davetli listesi vardır.

Aksini varsayalım. O zaman $A_1$ i içeren her uygun davetli listesinde bu kamber grubundan başka bir eleman daha bulunur. Öyleyse $\{ A_2, \ldots, A_k\}$ de bir kamber grubudur, çelişki.

Bu davetli listesi $\{ A_1, B_1, \ldots , B_l\}$ olsun.

İddia 2: Bu davetli listesinden sadece $A_1$ in sevdiği en az bir yemek vardır.

Aksini varsayalım. O zaman $A_1$ in sevdiği her yemek için bu yemeği seven bir $B_i$ bulunur. Bu durumda $\{B_1, \ldots , B_l\}$ uygun davetli listesidir, ama kamber grubunda bu listeden eleman yok, çelişki.

Bu yemekler $Y_1, Y_2, \ldots, Y_m$ olsun.

İddia 3: Bu yemeklerden öyle biri vardır ki, verilen kamber grubu dışındakilerden o yemeği seven yoktur.

Aksini varsayalım. Her $Y_i$ yemeği için bu yemeği seven bir $C_i$ vardır (bunlar aynı kişi olabilir), o zaman $C_i$ lerin birleşimi ile $B_j$ leri içeren davetli listesi uygundur, ama kamber grubunda bu listeden eleman yok, çelişki.

Bu yemeklerden biri $Y$ olsun.

İddia 4: $A_i$ lerin tümü $Y$ yi sever.

Aksini varsayalım, $A_i$ $Y$ yi sevmiyor olsun. Kamber grubundan sadece $A_i$ yi içeren uygun davetli listesi $\{ A_i, D_1, \ldots , D_n\}$ ye bakalım. $D_i$ lerden hiçbiri $Y$ yi sevmez, $A_i$ de $Y$ yi sevmediğinden bu davetli listesi uygun değildir, çelişki.

İddianın soruyu bitirdiği açıktır.