Güvercinler ve kaplamalar

Geçtiğimiz hafta ortaya atılan üç "güvercin" problemi, nispeten basit olmalarına rağmen, çok sayıda ve ilginç yoruma yol açtı.

Birincisi en basit olanı: Bir zarı 12 kez atarsak, altı sayıdan her birinin iki kez gelmesi olasıdır (ne kadar olası değil ki?), ancak bu olası değildir. Dolayısıyla, bir sayının en az üç kez geleceğinden kesinlikle emin olmak için zarı 13 kez atmamız gerekir.

İkincisine farklı şekillerde yaklaşılabilir. Luis Ortiz'in bunu nasıl yaptığına bir bakalım:

"12 basamaklı problem bir tablo kullanılarak açıkça gösterilmiştir. 100 olası iki basamaklı sayıyı, her biri 00'dan başlayarak 11 ardışık sayıdan oluşan satırlara şu şekilde yerleştiriyoruz:

00 01 02 03 04 05 06 07 08 09 10

11 12 13 14 15 16 17 18 19 20 21

22 23 24 25 26 27 28 29 30 31 32

· · ·

88 89 90 91 92 93 94 95 96 97 98

99

Bu tabloda, aynı sütundaki herhangi iki sayı arasındaki fark 11'in katıdır veya başka bir deyişle, her iki rakam da eşittir. Tabloda herhangi 12 sayı seçersek, en az ikisi aynı sütunda olmalıdır, yani farkları her iki rakamı da eşit olacaktır. Gerçekten de: sonuçta, 11 kutu ve 12 güvercini olan bir güvercinliktir.

Önceki yazının sonunda, güvercin deliği ilkesinin, graf teorisiyle birleştirildiğinde bazı problemleri etkili bir şekilde çözmemize olanak sağladığını söylemiştim ve Manuel Amorós'un geçen haftaki problemlerden üçüncüsü için sunduğu çözüm bunun güzel bir örneğidir:

“Dostluk problemi, noktaların insanları ve kenarların ilişkileri ifade ettiği renkli bir grafikte açıkça görülür: birbirlerini tanıyorlarsa mavi bir kenar, aksi takdirde kırmızı bir kenar. Amaç, tek renkli bir grafiğin varlığını göstermektir. Herhangi bir P köşesinden, mavi veya kırmızı olmak üzere 5 kenar çıkar. Zorunlu olarak, aynı renkten 3 tane olacaktır, diyelim ki mavi. Karşılık gelen 3 köşe de birbirine bağlanacaktır ve iki durum olabilir: ya söz konusu üçgenin 3 kenarı da kırmızıdır (tek renkli bir üçgenimiz olurdu) ya da bir tane mavi kenar vardır. Bu kenar, uçlarından P'ye doğru çıkan 2 kenarla birlikte mavi bir üçgen oluşturur.”

Benzer figürlere sahip kaplamalar

Kavramsal güvercinliğimizden ayrılmadan (ilişki çok açık olmasa da), Salva Fuster aşağıdaki örtme problemini önerdi:

"Bir eşkenar üçgen verildiğinde, onu kaplamak için en az kaç tane daha küçük eşkenar üçgene ihtiyaç vardır?"

Bu küçük üçgenlerin eşit olması gerekmez ve üst üste gelebilirler (aksi takdirde cevap açıkça 4 olurdu).

Sorun ilginç varyasyonlara ve genellemelere izin veriyor: Bir kare verildiğinde, onu kaplamak için en azından kaç tane daha küçük kareye ihtiyaç vardır? Kriter diğer düzenli çokgenlere genelleştirilebilir mi? Ve düzensiz çokgenlere? Ve daireye?

Ve son olarak, eşkenar üçgen ile güvercin yuvası ilkesinin birleştiği bir başka problem (SF ile ince bir bağlantısı olan):

Kenar uzunlukları 1 metre olan eşkenar üçgende verilen 5 noktanın birbirinden uzaklığı 50 cm'den fazla olabilir mi?