XIV. UMO(2006) ardışık sayı içermeyen kümeler

[ERhan ERdoğan]

{1,2,.......,2006} kümesi, boş olmayan ve hiçbiri ardışık herhangi iki sayı içermeyen
üç kümeye kaç değişik biçimde ayrılabilir?

A) 3²⁰⁰⁶-3.2²⁰⁰⁶+1   B) 2²⁰⁰⁵-2    C) 3²⁰⁰⁴   D) 3²⁰⁰⁵-1    E) Hiçbiri

[Lokman Gökçe]

Kümeler A, B, C olsun. 1 in eleman olarak A kümesinde olduğunu varsayabiliriz. Bundan sonra

2, ya B de veya C dedir. 2 durum var.
3, ya A da, ya da 2 yi bulundurmayan kümededir. 2 durum var.

... Bu şekilde devam edersek herbir eleman için 2 durum olacaktır. çarpma prensibinden 2²⁰⁰⁵ elde ederiz. Tek sayılar A kümesinde, çift sayılar B ya da C den birinde birikirse diğer küme boş olacağındna 1 çıkarmalıyız. 2²⁰⁰⁵ - 1 Cevap E.

[ERhan ERdoğan]

{1,2,......,30} kümesinden 5 elemanlı fakat ardışık eleman içermeyen
kaç küme seçilir?  yanıt: C(26,5)

[Lokman Gökçe]

Öncelikle ilk sorumun cevabını 2²⁰⁰⁴ - 1 olarak değiştireyim. 3 tane doğru çözüm vereceğim.
Ayırtedilemezlik kavramının yerleşmesi bakımından, bu problemlerde sorun yaşayanlar için, her bir çözümün dikkatle okunmasını tavsiye ederim.

1. yol: A, B, C birbirinden ayırtedilemeyen kümeler olduğu için 1 in A da olduğunu varsaymak genelliği bozmaz demiştik. 2 nin de B de olduğunu varsaymak genelliği bozmaz. Bu kabuller altında A, B, C ayırtedilebilir kümelerdir. Şimdi 3'ü B ye yazamayız. A veya C ye yazılacağından 2 durum var. Benzer şekilde 4'ü yazabileceğimiz iki küme vardır. Bunlar 3'ü içermeyen kümeler olabilir....vs. 2006 için de 2 durum vardır. Çarpma prensibinden 2²⁰⁰⁴ elde edilir. Fakat A, B, C nin boş olmaması isteniyordu. A ile B nin içinde sırasıyla 1, 2 elemanları olduğundan zaten boş küme değiller. C nin boş olduğu bir durum var. O da A = {1, 3, 5, ..., 2005} , B = {2, 4, 6, ..., 2006}, C = { }  yazılışıdır. Dolayısıyla doğru yanıt 2²⁰⁰⁴ - 1 olmalıdır.

2. yol: Üstteki hatalı çözümümde 1 in A da olduğunu varsaymak genelliği bozmaz diyerek başlamıştık. Bu yoldan ilerleyelim. yapılan hatayı da açıklarsak problem daha iyi anlaşılacaktır. 2 ya B de ya da C dedir demişiz, doğru. Ama böyle başlayınca B ile C ayırtedilemez kümeler olmaktadır. Bunu aklımızda tutarsak hiçbir sorun çıkmayacaktır. Bu halde 2²⁰⁰⁵ elde ederiz. Fakat A = {1, 3, 5, ..., 2005} , B = {2, 4, 6, ..., 2006}, C = { } ya da A = {1, 3, 5, ..., 2005} , C = {2, 4, 6, ..., 2006}, B = { } istenmeyen durumlar olduğundan bu iki durumu çıkarmalıyız. 2²⁰⁰⁵ - 2 elde edilir. Seçenekler çeldirici olarak hazırlanmış, bu cevap seçeneklerde var. B ile C ayırtedilemez olduğundan 2²⁰⁰⁵ - 2  sayısını 2! ile bölelim.  2²⁰⁰⁴ - 1 elde edilir.

3. yol: 1 sayısı A, B, C den herhangi birindedir. 3 durum var. Bundan sonra 2 sayısı (1 i bulundurmayan) diğer iki kümeden birindedir, 2 durum var. 3 sayısı (2 yi bulundurmayan) diğer iki kümeden birindedir, yine 2 durum var ... vs. 2006 sayısı  (2005 i bulundurmayan) diğer iki kümeden birindedir, 2 durum var. çarparsak 3.2²⁰⁰⁵ olur. Şimdi de boş küme durumlarını çıkaralım. A = {1, 3, 5, ..., 2005} , B = {2, 4, 6, ..., 2006}, C = { } ve permütasyonlarından 6 tane istenmeyen durum elde edilir. 3.2²⁰⁰⁵ - 6 sonucuna ulaşırız. A, B, C ayırtedilemez kümeler olduğundan bunların kendi aralarında yer değiştirmesi aynı kümeleri verir. Dolayısıyla 3.2²⁰⁰⁵ - 6 sayısını 3! ile bölmeliyiz. Buradan 2²⁰⁰⁴ - 1 elde edilir.

[Lokman Gökçe]

{1,2,......,30} kümesinden 5 elemanlı fakat ardışık eleman içermeyen
kaç küme seçilir?  yanıt: C(26,5)

Problemin çözümü dağılım prensibi ile ilgilidir. A = {a, b, c, d, e} ardışık eleman içermeyen bir küme olsun. Bu durumda a dan küçük x₁ tane sayı, a ile b arasında x₂ tane sayı, b ile c arasında x₃ tane sayı, c ile d arasında x₄ tane sayı, d ile e arasında x₅ tane sayı, e den büyük x₆ tane sayı olduğunu düşünebiliriz. A kümesinde ardışık eleman bulunmaması için x₁ > 0, x₆ > 0, x₂ > 1, x₃ > 1, x₄ > 1, x₅ > 1 olması gereklidir ve tabii ki yeterlidir. {1,2,......,30} kümesinin elemanlarından 5 tanesi {a, b, c, d, e} olduğundan geriye 25 tane sayı kalıyor.

x₁ + x₂ + x₃ + x₄ + x₅ + x₆ = 25

denkleminin çözüm sayısını bulmalıyız. Bu ise dağılım prensibinden dolayı C(26, 5) elde edilir.

[proble_m]

{1,2,......,30} kümesinden 5 elemanlı fakat ardışık eleman içermeyen
kaç küme seçilir?  yanıt: C(26,5)

Problemin çözümü dağılım prensibi ile ilgilidir. A = {a, b, c, d, e} ardışık eleman içermeyen bir küme olsun. Bu durumda a dan küçük x₁ tane sayı, a ile b arasında x₂ tane sayı, b ile c arasında x₃ tane sayı, c ile d arasında x₄ tane sayı, d ile e arasında x₅ tane sayı, e den büyük x₆ tane sayı olduğunu düşünebiliriz. A kümesinde ardışık eleman bulunmaması için x₁ > 0, x₆ > 0, x₂ > 1, x₃ > 1, x₄ > 1, x₅ > 1 olması gereklidir ve tabii ki yeterlidir. {1,2,......,30} kümesinin elemanlarından 5 tanesi {a, b, c, d, e} olduğundan geriye 25 tane sayı kalıyor.

x₁ + x₂ + x₃ + x₄ + x₅ + x₆ = 25

denkleminin çözüm sayısını bulmalıyız. Bu ise dağılım prensibinden dolayı C(26, 5) elde edilir.

Çok güzel bir çözüm olmuş. Zihnine sağlık hocam..

[proble_m]

Öncelikle ilk sorumun cevabını 2²⁰⁰⁴ - 1 olarak değiştireyim. 3 tane doğru çözüm vereceğim.
Ayırtedilemezlik kavramının yerleşmesi bakımından, bu problemlerde sorun yaşayanlar için, her bir çözümün dikkatle okunmasını tavsiye ederim.

1. yol: A, B, C birbirinden ayırtedilemeyen kümeler olduğu için 1 in A da olduğunu varsaymak genelliği bozmaz demiştik. 2 nin de B de olduğunu varsaymak genelliği bozmaz. Bu kabuller altında A, B, C ayırtedilebilir kümelerdir. Şimdi 3'ü B ye yazamayız. A veya C ye yazılacağından 2 durum var. Benzer şekilde 4'ü yazabileceğimiz iki küme vardır. Bunlar 3'ü içermeyen kümeler olabilir....vs. 2006 için de 2 durum vardır. Çarpma prensibinden 2²⁰⁰⁴ elde edilir. Fakat A, B, C nin boş olmaması isteniyordu. A ile B nin içinde sırasıyla 1, 2 elemanları olduğundan zaten boş küme değiller. C nin boş olduğu bir durum var. O da A = {1, 3, 5, ..., 2005} , B = {2, 4, 6, ..., 2006}, C = { }  yazılışıdır. Dolayısıyla doğru yanıt 2²⁰⁰⁴ - 1 olmalıdır.

2. yol: Üstteki hatalı çözümümde 1 in A da olduğunu varsaymak genelliği bozmaz diyerek başlamıştık. Bu yoldan ilerleyelim. yapılan hatayı da açıklarsak problem daha iyi anlaşılacaktır. 2 ya B de ya da C dedir demişiz, doğru. Ama böyle başlayınca B ile C ayırtedilemez kümeler olmaktadır. Bunu aklımızda tutarsak hiçbir sorun çıkmayacaktır. Bu halde 2²⁰⁰⁵ elde ederiz. Fakat A = {1, 3, 5, ..., 2005} , B = {2, 4, 6, ..., 2006}, C = { } ya da A = {1, 3, 5, ..., 2005} , C = {2, 4, 6, ..., 2006}, B = { } istenmeyen durumlar olduğundan bu iki durumu çıkarmalıyız. 2²⁰⁰⁵ - 2 elde edilir. Seçenekler çeldirici olarak hazırlanmış, bu cevap seçeneklerde var. B ile C ayırtedilemez olduğundan 2²⁰⁰⁵ - 2  sayısını 2! ile bölelim.  2²⁰⁰⁴ - 1 elde edilir.

3. yol: 1 sayısı A, B, C den herhangi birindedir. 3 durum var. Bundan sonra 2 sayısı (1 i bulundurmayan) diğer iki kümeden birindedir, 2 durum var. 3 sayısı (2 yi bulundurmayan) diğer iki kümeden birindedir, yine 2 durum var ... vs. 2006 sayısı  (2005 i bulundurmayan) diğer iki kümeden birindedir, 2 durum var. çarparsak 3.2²⁰⁰⁵ olur. Şimdi de boş küme durumlarını çıkaralım. A = {1, 3, 5, ..., 2005} , B = {2, 4, 6, ..., 2006}, C = { } ve permütasyonlarından 6 tane istenmeyen durum elde edilir. 3.2²⁰⁰⁵ - 6 sonucuna ulaşırız. A, B, C ayırtedilemez kümeler olduğundan bunların kendi aralarında yer değiştirmesi aynı kümeleri verir. Dolayısıyla 3.2²⁰⁰⁵ - 6 sayısını 3! ile bölmeliyiz. Buradan 2²⁰⁰⁴ - 1 elde edilir.

Mükemmel..