Matematik Atölyesi – Garip Dünyalar #15

İnsan Düğümü Oyunu

Sınıftaki öğrenciler en az 5’erli gruplara ayrılır. Her grup ayakta çember şeklinde durur ve aşağıdaki talimatları izler:

  1. Gruptaki öğrencilerin sayısı çift ise:
    20190812_153400.jpg
    -Her öğrenci sağ eliyle komşusu olmayan birinin sağ elini tutar.
    20190812_153408.jpg
    -Öğrenci aynı şeyi sol elleri için yapar.
    20190812_153415.jpg
  2. Gruptaki öğrencilerin sayısı tek ise:
    20190812_153325.jpg
    -Biri hariç her öğrenci sağ eliyle komşusu olmayan (yani yanında olmayan) birinin sağ elini tutar.
    20190812_153338.jpg
    -Boşta kalan öğrenci sağ eliyle kendisine komşu olmayan birinin sol elini tutar.
    20190812_153345.jpg
    -Sol eli boşta kalan öğrenciler boşta kalan elleriyle birbirlerine komşu olmayanların sol elini tutar.
    20190812_153353.jpg

Talimatlar sonucunda öğrenciler düğümlenmiş olur.

The-Human-Knot-Game-e1447920419118-663x375

Öğrencilerin amacı ellerini bırakmadan düğümü çözmektir. Bunu yaparken öğrenciler Reidemeister hamlelerini kullanabilir.

Reidemeister Hamleleri

1926’da Kurt Reidemeister düğüm teorisi için harikulade bir şey keşfetmişti. Ona göre herhangi bir düğüm üzerinde Riedemeister hamleleri olarak adlandırdığımız üç hamle yapılabilirdi. Bu hamleler sayesinde bir düğümün farklı gösterimleri ve/veya herhangi düğümün birbiriyle aynı olup olmadığı bulunabilirdi.

Örneğin bir düğümün kesişimsiz düğüm (unknot) olup olmadığını, diğer bir deyişle bir düğümün çözülüp çözülemeyeceğini Reidemeister hamleleri kullanarak anlayabiliriz.

Peki bu hamleler nelerdir?

  1. Kıvırmak

    Reidemeister hamlelerinden biri kıvırma hareketidir. Bir düğüm üzerinde kıvırma hareketi yapmak serbesttir.

  2. Dürtmek

    İkinci hamle dürtmektir. Bir düğüm üzerinde dürtme hareketi yapmak serbesttir.
  3. Kaydırmak


    Son Reidemeister hamlesi kaydırma hareketidir.

Bi’ Göz Atmakta Fayda Var

İnsan düğümünü çözerken hangi hamlede hangi Reidemeister hamlesini kullandınız?

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Bulmaca #4

Haylaz Öğrenciler

Arkadaşlıklar arasında sıra arkadaşlığının diğerlerine kıyasla bambaşka bir yeri vardır. Sınıf içerisinde her öğrencinin öyle bir eşi vardır ki bu ikisi birbirine yakın oturduğunda (yan yana, önlü-arkalı veya diyagonal) rahat durmaları neredeyse imkansızdır. Bunun farkında olan öğretmenler sene içerisinde deneme yanılma yaparak en ideal oturma düzenini sağlamaya çalışır.

Steve Hocanın Problemi

Steve hoca ders verdiği sınıflardan birinde birbirlerine yakın olduğunda (birbirine yakın olmaya bundan sonra komşuluk diyeceğim) haylazlık yapmadan duramayan 8 öğrenciyi fark etmişti.

Koşullar

  • Komşu öğrenciler: Birbirleriyle yan yana, önlü-arkalı veya diyagonal olarak oturan iki öğrenciye denir.
  • Eğer iki öğrenci haylazlık yapıyorsa aralarında <–> bulunur.
  • Steve’in sınıfındaki 8 öğrencinin birbirleriyle ilişkileri şöyleydi:
  • Deniz <–> Ali <–> Kirk <–> Jane <–> Poseidon <–> Rebecca <–> Lucreita <–> Bran
  • Bu 8 öğrencinin oturma düzeni aşağıdaki gibidir:

sekiz.jpg

Sınıfın geri kalanının düzenini bozmak istemeyen Steve hocanın problemi şuydu:

“Bu 8 öğrenciyi çiftler birbirine komşu olmayacak şekilde nasıl oturtabilirim?”

İpucu: Öğrencilere sayı atayın.

Cevap bir sonraki yazıda.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Garip Dünyalar #14

Kulaklıklar Artık Düğüm Olmasın

12-13 yaşlarındayken kasetçalarım olmadan dışarı çıkmazdım. Kasetçalarımla ilgili iki büyük düğümlenme sorunum vardı. Bunlardan ilki kasetin bandının düğümlenmesiydi. Şanslıysam kalem yardımıyla bu düğümü kolayca çözebilirdim. Şansımın yaver gitmediği durumlarda ise kaset çöpe giderdi.

person holding black cassette tape

Diğer düğüm problemi kulaklığımla alakalıydı. Kimi zamanlar kulaklığım öyle düğümlenirdi ki düğümü çözene kadar muhakkak bir arkadaşıma denk gelirdim. Bu da karışık kasedimi bir sonraki güne kadar dinleyemeyeceğim demekti.

20190730_143315.jpg

İşin komik tarafı yaşadığım sinir harbi nedeniyle kulaklığı çantama rastgele fırlatarak aynı sorunu ertesi gün de yaşayacağımı garantiye alıyordum.

Çantada birbirine dolanan kulaklık olayının bir benzeri vücudumuzu oluşturan hücrelerde her an yaşanmaktadır.

DNA, tüm organizmalar ve bazı virüslerin canlılık işlevleri ve biyolojik gelişmeleri için gerekli olan genetik talimatları taşıyan bir nükleik asittir. DNA’nın başlıca rolü bilginin uzun süreli saklanmasıdır.

dna_main_001

DNA, “helix” adıyla bilinen bir sarmal eğri şeklindedir. Bir hücrenin içinde bulunan DNA sarmalının uzunluğu 2 metreyi bulur. Boyutlar arasındaki ilişkiyi tamamen anlamanız için bir örnek vereceğim: Eğer bir hücrenin çekirdeği basketbol topu büyüklüğünde olsaydı, o hücrede bulunan DNA 200 km uzunluğunda olurdu.

Bir metrelik kulaklığı kocaman bir çantaya atınca neler olduğunu biliyorsunuz. Bir basketbol topunun içine 200 km uzunluğunda sarmal eğri sığdırmaya çalışmak mı?! Tanrım; her yer düğüm!

Düğüm Teorisi

İşte bu keşmekeş matematikçilerin düğümlerle ilgilenmesine neden olmuştu. Fakat matematik ile düğümün ilişkisi DNA çalışmalarından çok daha eskiye dayanıyor. 19. yüzyılda İskoç bilim insanı William Thomson (nam-ı diğer Lord Kelvin) atomların farklı düğümler şeklinde olduğunu öne sürmüştü. Kısa süre içinde Lord Kelvin’in fikri matematikçileri düğümleri incelemeye itse de Lord Kelvin’in yanıldığının ortaya çıkması düğüm teoresini neredeyse 100 yıl boyunca kendi haline bırakmıştı. (20. yüzyılın başlarında Kurt Reidermeister’ın çalışmaları neredeyse 1980’lere dek tekti. Reidermeister’dan bir sonraki yazıda bahsedeceğim.)

Peki matematiksel düğümün diğer düğümlerden farkı var mı?

maxresdefault (4)

Örneğin ayakkabı bağcıklarını bağlarken atılan düğüm, matematikte düğüm olarak karşılık görmez. Çünkü bağcığın iki ucu açıktır. Halbuki matematikte bir düğümün iki ucu birbirine bağlı olmalıdır.

180px-Example_of_Knots.svg

Soldaki düğüm olsa da matematikte düğüm ifade etmez. Sağdaki ise matematiksel bir düğümdür.

Unknot* ve Trefoil*

Düğüm teorisinde düğümlere farklı isimler verilir. Bu yapılırken düğümün en sade halinin sahip olduğu kesişim sayısı dikkate alınır. Hiç kesişimi olmayan bir düğüm (unknot veya kesişimsiz düğüm) aslında bir çemberdir:

20190730_135245.jpg
Lastik bant bir kesişimsiz düğümü ifade eder. (unknot)

Aşağıdaki iki düğüme bir göz atın:

 

 

Bu düğümler birbirlerinden farklı görünüyor değil mi? Soldakinde 1, sağdakindeyse 2 kesişim vardır.

lanaa.jpg

Fakat bu düğümlerden birini kesip-biçmeden, yalnızca iple oynayarak (bir tarafa yatırmak ve/veya ters çevirmek gibi) diğerine benzetebiliriz!

Yani aslında bu iki düğüm birbirinin aynısıdır. Hatta bu iki düğüm, yukarıda gösterilmiş olan kesişimsiz düğümün ta kendisidir. Örneğin soldaki düğümün sol kısmı yukarı itilirse kesişimsiz düğüme dönülür:

 

 

1 kesişimi olan ama kesişimsiz düğüme döndürülemeyen bir düğüm var mıdır?

Hemen yanıtı veriyorum: 1, ve hatta 2, kesişimi olup da kesişimsiz düğüme döndürülemeyecek bir düğüm yoktur.

Peki ya 3 kesişim?

3 kesişimi olup, kesişimsiz düğüme çevrilemeyen düğüme trefoil denilir.

Blue_Trefoil_Knot.png
Trefoil düğüm.

Trefoil, ilk bakışta kesişimsiz düğüme çevrilebilecekmiş gibi görünse de düğüm teorisi kuralları çerçevesinde (yani kesip-biçmeden) bunu yapmak imkansızdır. Trefoil özel bir düğümdür, çünkü (unknot dışında) kesişim sayısı en düşük (3) olan düğümdür. Bu yüzden de trefoil düğüm teorisi için temel kabul edilir.

trefoilandmirror.jpg

Trefoil düğümün önemli özelliklerinden biri ayna simetrisiyle alakalıdır: Birbirinin simetrisi olan a ve b trefoilleri birbirinden farklıdır! Yani birinden diğerini elde etmek düğüm teorisi kuralları içinde mümkün değildir.

Möbius Şeridi ve Trefoil

Daha önce Möbius şeridi ve özelliklerinden bahsetmiştim. Kısaca hatırlatmak gerekirse bir kağıt şeridinin iki ucu birbirine bağlanırsa çember elde edilirken, uçlardan biri 180 derece çevrilip uçlar bağlanırsa karşınıza Möbius şeridi çıkar.

Gelin Möbius şeridini yaparken uçlardan birini üç defa 180 derece çevirelim:

 

 

Daha sonra oluşan şekli ortasından (boyuna paralel olarak) keselim:

20190730_131333.jpg

Karşımıza aşağıdaki gibi bir şekil çıkar:

20190730_134158-1.jpg

Şekli bir kurcaladığımızda aslında bir trefoil düğümü elde ettiğimizi görürüz:

 

 

Devam edecek…

Bi’ Göz Atmakta Fayda Var

  1. Kağıt şeridinden trefoil düğümü yaparken şeridin ucunu 3 defa 180 derece döndürüyoruz. Bu döndürmeyi içe veya dışa yapmanın bir farkı var mıdır? Neyle karşılaştınız?
  2. Şeridin ucunu 3 değil de 5 defa döndürürseniz ne olur? (Cevabı bir sonraki yazıda.)

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Algoritma #5

Doğru Pizza Dilimi

Üç arkadaş üç farklı pizza dilimini paylaşacaktır.

Pizzalar:

68591

Pizza 1: Dört peynirli.

20665-white-chicken-pizza-600X600

Pizza 2: Tavuklu.

pineapple pizza

Pizza 3: Ananaslı.

Üç arkadaş bu üç pizzayı altı şekilde paylaşabilir:

20190514_170727.jpg
P1:Pizza 1, P2:Pizza 2, P3:Pizza 3.

Ne Kadar Çok İstiyorsun?

Birer dilim pizza yemek çok basit bir işmiş gibi görünse de olayın arka planında tahmin edilemeyecek kadar çok detay vardır. Öncelikle bu üç dilimin maliyeti işin içindedir. Bir de tercih meselesi vardır; malum herkesin damak tadı aynı değil.

Diyelim ki bu üç dilim toplam 6 lira tuttu. Ali, Steve ve Jane için pizza tercihleri de aşağıdaki gibi olsun:

  1. Ali için ilk tercih dört peynirli. Eğer onu alamazsa tavuklu; son tercihi ise ananaslı.
  2. Steve için ilk tercih tavuklu, ikincisi ananaslı ve son olarak dört peynirli.
  3. Jane’in tercihleri sırasıyla tavuklu, dört peynirli ve ananaslı şeklindedir.

Bu durumda kimin hangi dilimi kaç liraya alacağına (adil bir şekilde) nasıl karar verilebilir?

Ev Arkadaşı Problemi (Kira Harmonisi Problemi)

İki (veya daha fazla) arkadaş kiraladıkları evde odaları ve kirayı adil olarak nasıl bölüşür sorusu uzun yıllar matematikçileri meşgul etmiştir. Ev arkadaşı problemi olarak bilinen bu soru adil paylaşmanın en bilindik problemlerinden biridir.

Ev arkadaşı probleminin adil ve kıskanç olmayan çözümlerinden biri 2004’te yayımlanan Atila Abdulkadiroğlu, Tayfun Sönmez ve Utku Ünver’in ortak çalışmasında yer alır. Bu üçlünün açık artırma algoritması adil paylaşımın en ünlü çözümlerinden biridir. (Hatta ev arkadaşı problemini çözmek için kurulmuş olan Spliddit isimli web sitesinde uzun yıllar 2004’teki algoritma kullanılmıştı.)

Algoritmanın İşleyişi

  • Kirayı bölüşecek kişiler kapalı her oda için kapalı zarfta teklif verir. Odalara yapılan teklifler toplam kirayı vermelidir. (Örneğin 3000 liralık bir evdeki iki odaya yapılacak tekliflerin toplamı tam olarak 3000 lira etmelidir.)
  • Zarflar herkesin gözü önünde açılır. Bir odanın kazananı o odaya en yüksek teklifi yapandır.
  • Bir oda için teklifi kazanan kişinin diğer teklifleri geçersizdir.
  • Kazanan tüm teklifler toplanınca tam olarak kiraya denk geliyorsa, herkesin vereceği miktar belirlenmiş demektir.
  • Eğer tekliflerin toplamı kiradan az veya fazla ise, basit orantı işlemleriyle herkes için verilmesi gereken kira belirlenir.

Pizza Dilimi Cevabı

Üç arkadaşın pizza dilimi seçimi açık artırma algoritmasıyla çözülebilir. Üçlünün kapalı zarf teklifleri aşağıdaki gibi olsun:

20190514_170542.jpg

Tek tek pizzalara bakıldığında ilk pizzayı Ali 4 liraya, ikinciyi Steve 4 liraya, üçüncüyü ise Jane 2 liraya kazanmış olur:

Tekliflerin toplamı

4 + 4 + 2 = 10

liradır. Teklif toplamları pizza dilimlerine verilecek 6 liradan fazla olduğu için tekliflerin oranları hesaplanır:

20190514_170507.jpg

Bu durumda Ali ve Steve 4 lira vermeye hazır oldukları pizza dilimlerine 2,4’er liraya, Jane ise 2 lira vermeye hazır olduğu pizza dilimine 1,2 liraya kavuşur. Algoritma sonucunda hem herkes istediği pizza dilimini düşündüklerinden daha ucuza almış olur.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Algoritma #4

Adil Pasta Kesimi

Adil bir şekilde pasta kesmenin bir yolu var mı?

Bunu resmen bir matematik problemi olarak gören ilk kişi Hugo Steinhaus isminde bir matematikçiydi. Steinhaus 1944 yılında bir pastayı iki kişinin nasıl paylaşabileceği üzerine kafa yormuştu.

Ona göre birbirlerinin seçimlerini kıskanmadan iki kişinin pastayı paylaşmasının yolu “biri keser, diğeri seçer” yöntemiydi:

İlk kişi pastayı ikiye böler, ikinciyse iki parçadan istediğini alır. Bu yöntemde ikinci kişi istediği parçayı alabildiği için tercihinden memnundur. İlk kişiyse pastayı eşit olarak iki parçaya ayırdığını düşündüğü için iki parçadan kendisine hangisi kalırsa kalsın memnun olacaktır. Steinhaus’un bu yöntemi bilinen ilk kıskanç olmayan yöntemdi.

Peki üç kişi bir pastayı birbirlerinin seçimlerini kıskanmadan nasıl paylaşabilir?

İnanılmaz ama bu soru ancak 1962’de cevaplanmıştı. Soruyu birbirinden bağımsız olarak çözen J. H. Conway ve J. Selfridge’e göre yöntem şu şekilde ilerler:

Ali, Steve ve Jane

  1. Ali pastayı üç (kendince) eşit parçaya böler.
  2. Steve bu parçaları kontrol eder. Eğer Steve kontrol sonrası bir şey yapmazsa sıra Jane’e geçer.
  3. İlk seçimi Jane, ikinci seçimi Steve, son seçimiyse Ali yapar.

Gelin yöntemi ayrıntılarıyla açıklayalım:

Adım #1: Ali ne yapmalı?

Ali göz kararı bir şekilde pastayı üç eşit (ya da en azından denk) parçaya böler:

Adım #2: Steve ne yapmalı?

Steve bu parçaları kontrol eder. Burada ihtimaller Ali’nin kesiminin değerlendirilmesiyle şekillenir:

  1. Eğer Steve parçalardan en az ikisinin en iyi (yani en büyük) parçalar olduğuna kanaat getirirse bir şey yapmaz ve sıra Jane’e geçer. Steve’e göre böyle bir durumda iki ihtimal vardır:
    a. Parçaların hepsi birbirine eşitse Jane hangisi seçerse seçsin kalan parçaların hepsi Steve’i memnun eder:

    20190502_152944.jpg
    Üç parça da eşitse ikinci seçimi yapacak olan Steve mutlu olacaktır.

    b. Eğer iki parça birbirine eşit ve üçüncü parçadan büyükse, Jane büyük parçalardan birini alsa dahi diğer büyük parça Steve’e kalır ki bu da onu memnun eder.

  2. Parçalardan biri diğer ikisinden büyükse Steve bir şey yapmak zorundadır. Aksi takdirde Jane tek büyük parçayı alır:
    20190502_153002.jpg
    Steve ortadaki parçanın diğer ikisinden daha büyük olduğunu fark eder. Eğer bir şey yapmazsa bu parça Jane’e gidecektir.

    Bu durumda Steve büyük parçayı traşlayarak düzenler ve fazla parçayı bir kenara ayırır. Böylece Steve Jane’e seçmesi için en kötü ihtimalle birbirine eşit iki büyük parça bırakmış olur:

    Steve ortadaki parçayı traşlar ve fazlalığı başka yere koyar. Örnekte orta ve sağ en iyi parçalardır. Jane bu ikisinden birini aldığı takdirde diğeri Steve’e kalacaktır.

Adım #3: Jane ne yapmalı?

Steve memnun olduğuna kanaat getirdikten sonra sıra Jane’e gelir:

  1. Eğer Steve hiçbir şey yapmamışsa üç parça birbirine eşit demektir. Bu durumda ilk Jane seçimini yapar, sonra da Steve. Son parça ise Ali’nindir. Böylece kıskanç olmayan kek kesimi gerçekleşmiş olur.
  2. Eğer Steve’e göre Ali’nin kestiği üç parçadan biri diğer ikisinden büyükse Steve bu büyük parçayı yukarıdaki adımda anlatıldığı gibi düzeltir ve sıra Jane’e öyle gelir. Böyle bir durumda Jane istediği parçayı seçer. Fakat Jane’in seçtiği parça yöntemin geri kalanını etkiler:
    a. Eğer düzenlenmiş kek parçasını Jane seçerse kalan iki parçayı sırasıyla Steve ve Ali alır. Bu durumda ayrılmış olan dördüncü parçayı Steve eşit üç parçaya böler. Bu üç parçayı sırasıyla Jane, Ali ve Steve seçer ve adil paylaştırma sona erer:

    b. Eğer Jane düzenlenmiş kek parçasını almazsa bu parçayı Steve almak zorundadır. Bu durumda ayrılmış olan dördüncü parçayı Jane eşit üç parçaya böler. Bu üç parça sırasıyla Steve, Ali ve Jane tarafından seçilir ve adil paylaştırma sona erer.

Bi’ Göz Atmakta Fayda Var

Buraya kadar olan senaryo kıskançlıktan uzak mıdır?

(Okumadan önce cevap üzerine bir süre kendiniz düşünün.)

*

*

*

Cevaplar

Ali İçin: Evet. Çünkü orijinal keki üç eşit parçaya ayırdığını düşündüğü için hangi parça gelirse gelsin memnun olacaktır. Artan kısım olursa Ali için zaten eşit olduğunu düşündüğü parçaya biraz daha fazla pay gelmiş olacaktır.

Steve İçin: Evet. Çünkü kek parçalarından en az ikisinin en iyi (yani en büyük) olmasını garantilemeden Jane’e sırayı vermez. Eğer parçalardan birinde düzeltme yaptıysa ve bu parçayı Jane aldıysa, artan parçayı üç eşit parçaya bölen Steve olur ki bu da Steve’in herhangi bir artan parça ile memnun olacağı anlamına gelir.

Jane İçin: Evet. Çünkü orijinal parçalardan ilk seçimi yapan o olur: Bu sayede kendinden en iyi parçayı seçebilir. Ayrıca Steve’in üçe böldüğü artan kısımda da ilk seçimi yapacağı için paylaşımdan memnun olacaktır.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Oyun #11

Lahana

1967’de M. S. Paterson ile J. H. Conway’ın yarattığı iki kişilik bir oyun olan lahanayı oynamak için kağıt ve kalemden başka bir şeye ihtiyacınız yoktur.

  • Oyuna başlarken kağıt üzerine rastgele üç adet nokta koyulur:20190429_140440.jpg
  • Oyuncular sırayla bir noktadan diğerine (veya bir noktadan yine kendisine) giden bir eğri çizer. Çizilen eğrinin üzerine bir de nokta konur:
  • Çizilen eğriler birbirini kesemez.

    20190429_140912.jpg
    Çizgilerin kesişmesi yasaktır.
  • Bir noktaya bağlı üç tane eğri varsa, o nokta artık ölüdür: Yani o noktaya başka bir eğri bağlanamaz:
    Soldaki resim ihlal içerirken sağdaki resimde A, B ve E noktaları “ölü”dür. Çünkü bu noktaların her biri üç çizgiye sahiptir.
  • Son eğriyi çizen oyunu kazanır.

Brüksel Lahanası

Lahananın bir başka versiyonu olan Brüksel Lahanası’nda başlangıçta konulan noktaların ufak çizgileri vardır. Bu noktalar ve üzerinde bulunan çizgiler istenilen sayıda seçilebilir. Örneğin birinde 3, diğerinde 4 çizgi olan iki noktayla oyuna başlayalım:

20190429_141609.jpg

Brüksel Lahanası’nda da oyuncular sırayla birer eğri çizer (her çizilen eğrinin üzerine yeni bir nokta ve iki küçük çizgi konur). Bu sefer eğriler noktalarda bulunan ufak çizgiler arasındadır:

20190429_141659.jpg

Yine bir önceki oyunda olduğu gibi çizilen eğriler birbirini kesemez ve yine en son eğriyi çizen oyunu kazanır:

En sağdakinde çizgiler kesiştiği için ihlal vardır.

Euler ve Lahana

Euler ile bu basit görünümlü oyunların ne alakası var diyebilirsiniz. Euler karakteristiğinden daha önceki yazılarımda bahsetmiştim.

Euler der ki:

Bir düzlemde (kağıt üzerinde) V tane nokta ve bu noktalar arasında birbirini kesmeyen E tane çizgi olsun. Bu nokta ve çizgilerin çerçevelediği yüzlerin sayısı da F olsun (tüm kağıdın da bir yüz olduğunu unutmayın). O halde:

V – E + F = 2 olur.

Yani nokta sayısıyla yüz sayısını toplayıp bundan çizgi sayısını çıkarırsan cevap her zaman 2 olur.

Bitmiş bir Brüksel Lahanası oyununu ele alın. Nokta, çizgi ve yüz sayılarını belirleyin:

Euler’in formülüne sayıları yerleştirin:

Euler her defasında haklı çıkacak!

Dört Renk

Yine bitmiş bir Brüksel Lahanası’nı ele alın. Bu sefer dört farklı renkte kaleme ihtiyacınız olacak:

Bitmiş oyun üzerindeki alanları komşu olanlar farklı renkte olacak şekilde boyarsanız dört rengin yeterli olacağını göreceksiniz.

Bi’ Göz Atmakta Fayda Var

  1. Lahana oyununu 3 nokta ile en fazla kaç el oynayabilirsiniz?
  2. Lahanayı kazanmak için bir strateji bulabilir misiniz?
  3. Brüksel lahanasında üçer dikeni olan iki nokta ile en fazla kaç el oyun sürdürülebilir?

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Hayat-Matematik İlişkisi #7

H&G Oyunu

Bu ismi çoğunuzun küçükken öğrendiği Hansel ve Gretel’in hikayesinden esinlenerek koydum. (Eğer hikayeyi bilmiyorsanız lütfen okuyun.)

H&G’de amaç iki yer arasındaki en kısa yolu bulmaktır. Fakat oyun oturulan yerden değil, bizzat deneyimlenerek ilerler. Sonuca yaşanılan deneyimlerden çıkarım yaparak ulaşılır.

Şimdiden belirtmem gerekiyor: Bu oyunu böceklerden, özellikle karıncalardan öğrendik. Yazının devamında buna değineceğim.

Peki H&G nasıl oynanır?

  • Oyuncular belirtilen iki yer arasında yürüyüş yapar.
  • Her oyuncunun başlangıç ve bitiş yerleri aynıdır.
  • Yürüyüş için birden fazla yol vardır.
  • Amaç bu iki yoldan hangisinin daha kısa olduğunu bulmaktır.
  • Oyun sırasında kalem dışında hiçbir aletin kullanımına izin verilmez. (Saat, telefon vs. dahil.)
  • Oyuncular başlangıç ve bitişe vardığı her sefer için kalemle bir çizgi çizer.
  • Oyuncuların hızlarının aynı (ya da en azından benzer) olması için koşmaları yasaktır.

Oyun #1

H&G için hazırlanan iki yol aşağıdaki gibi olsun:

20190425_134042.jpg

Bu iki yol üzerindeki ilk yürüyüş başlarken hem A hem de B’de oyuncular bir süre aynı yolu gider, fakat yürüyüş devam ettikçe A’dekiler B yolundaki oyunculardan çok daha önce bitişe varır:

20190425_134109.jpg

B’de yürüyen oyuncular bitişe ulaştığında diğer yoldakilerin ilk çizgiyi koyduğunu görür. Bu da A yolunun B’den daha kısa olduğunu belirtir. Oyuncuların bir kısmı B’ye hala inanıp geri dönüşü yaptığında, bitişe ulaştıklarında A’dakilerin ikinci çizgiyi çektiğini görür.

Böylece B’nin daha uzun olduğunu (gerçekten inatçı olanlar hariç) herkes görmüş olur. Oyun devam ettiği sürece A’dakiler B’dekilere fark atacağı anlaşılmıştır.

Oyun #2

İlk oyunda herkes A yoluna geçmişken A üzerine aşağıdaki gibi bir engel koyalım:

20190425_134136.jpg

Oyunculardan en az biri B’yi denemeye karar verir. Bir kaç tur sonra çizgi sayılarında B’nin A’ya yaklaştığını fark eden oyuncular B yoluna geçmeye başlar:

20190425_134159.jpg
Yavaş da olsa B’deki oyuncular A ile farkı kapatır.

Zamanla oyuncuların hepsi B’nin daha kısa yol olduğunu kabul eder.

Oyun #3

İkinci oyun devam ederken C ismi verilmiş olan üçüncü bir yol açılsın:

20190425_134223.jpg

Yine oyunculardan en az biri C’yi denemeye karar verir. Aynı bir önceki oyun gibi oyunculardan dikkatli olanlar çizgi sayılarına bakarak hangi yolun daha kısa olduğuna karar verir.

En İyi H&G Oyuncuları: Karıncalar

Yazının başında karıncaların bize en kısa yolu bulmayı öğrettiğini söylemiştim. 1992’de Marco Dorigo ismindeki bir bilim insanı karıncaların yemek arayışlarıyla ilgili bir araştırma yapmıştı. Dorigo araştırması sonucunda karıncaların yuvalarıyla besin kaynakları arasındaki yolu nasıl gittiklerini açıklamıştı.

Karınca yuvası ve besin kaynağı aşağıdaki gibi olsun:

20190425_134508.jpg

Karınca besin kaynağını yuvasına aşağıdaki gibi bir yol izleyerek taşısın:

20190425_134535.jpg

Feromon: Aynı türün üyeleri arasındaki sosyal ilişkileri düzenleyen kimyasal madde.

Karıncalar yürürken arkalarında feromon, yani bir tür kimyasal madde bırakır:

20190425_134548.jpg

İşte karıncaların en kısa yolu bulmalarını sağlayan şey de bu maddedir. Bir yoldan ne kadar çok karınca geçerse o yolda o kadar çok feromon vardır. Aynı bizim kalemle çizgi çizmemiz gibi.

Gelin karıncaların yoluna bir engel koyalım:

20190425_134602.jpg

Karıncaların bir kısmı engelin aşağısından, diğer kısmıysa yukarısından yoluna devam eder:

20190425_134620.jpg

I numaralı yol daha kısa olduğu için karıncalar bu yolun üzerinde daha çok tur atarlar. Yani daha çok feronom bırakırlar:

20190425_134631.jpg

Zamanla diğer yoldaki karıncalar daha çok feronom olan yolu tercih eder.

Karınca Kolonileri Algoritması (KKA)

Gündelik hayatta her işimizi en hızlı ve en kısa yoldan halletmeye çalışıyoruz. İşte bunu yaparken bize yardımı olan algoritmalardan birinin adı Karınca Kolonileri Algoritması’dır. Bu algoritmanın mantığı karıncaların en kısa yolu bulma yönteminden gelir.

Quicktron-Alibaba-warehouse
Alibaba’nın içinde sadece robot çalışan deposu.

Örneğin KKA robotların hareketlerini belirlemesinde büyük önem teşkil eder. Bir alanda birden çok robotun birbirine çarpmadan hareket edebilmesi için KKA kullanılır.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Graf #6

Miras Problemi

Kral Serkan I ölüm döşeğindeyken sahip olduğu arsaları çocuklarına dağıtmaya karar verir. Doğal olarak Serkan I’in bazı koşulları vardır:

  • Her çocuk en az bir arsa alacak.
  • Birbirine komşu arsalar aynı çocuğun olmayacak.
  • Yukarıdaki koşullar sağlanmadığı takdirde mirasın tamamı “Fener Ol” kampanyası vasıtasıyla Frey’in bonservisine harcanacak.

Problem: Serkan I’in en az kaç çocuğu olmalı ki herhangi bir arsa paylaşımında sorun yaşanmasın?

Harita #1

Basit bir haritadan başlayalım:

20190423_000256.jpg

Bu durumda Serkan I’in iki çocuğunun olması yeterlidir:

20190423_000310.jpg

Bir önceki yazıdan hatırlayacağınız üzere harita ile graf birbirlerine dönüşebilir. Eğer arsalar noktaları ve iki arsanın komşu olması bu iki noktanın arasında çizgi olduğunu ifade ederse, haritamız aşağıdaki gibi graf olarak gösterilebilir:

20190423_000334.jpg

Bu haritaya bir arsa daha ekleyelim:

20190423_000402.jpg

Eklenen arsa graf için yeni nokta ve çizgi(ler) anlamına gelir:

20190423_000507.jpg

Harita #2

Yeni haritada üç arsa bulunsun:

20190423_000523.jpg

Bu haritayı graf haline getirelim:

20190423_000537.jpg

Grafta da görüldüğü üzere mirasın dağıtılabilmesi için Serkan I’in üç çocuğu olmalıdır:

20190423_000553.jpg

Harita #3

Üçüncü harita aşağıdaki gibidir:

20190423_000627.jpg

Bu dört arsanın kurallara uygun dağıtılması için miras dört çocuğa dağıtılmalıdır:

20190423_000642.jpg

Harita #3’teki durum graf olarak aşağıdaki gibidir:

20190423_000728.jpg

Harita #4

Serkan I’in bıraktığı arsaların aslında ABD haritasıyla aynı olduğunu varsayalım:

480271690e1e0485f71988e273730559

Bu haritayı paylaştırmak için Serkan I’in sadece dört çocuğunun olması yeterlidir:

amarikaaa

Ne Oluyor?

Dikkat ederseniz harita #2’nin grafından harita #3’ün grafına tek bir hareketle (yeni bir nokta koyarak) geçmek mümkündür. Hatta harita #1’den harita #2’ye geçiş de graf üzerine yeni bir nokta eklenip (3 numaralı olan) diğer iki noktaya bağlanarak gerçekleşmiştir:

O halde bir haritaya yeni bir mirasçı eklemek demek grafa yeni bir nokta eklemek demektir.

Peki en az beş çocuğun gerektiği bir harita yaratılabilir mi?

Bu soru aslında grafa (hiçbir çizgiyle kesişmeden) tüm noktalarla bağlantısı olan beşinci bir nokta eklenip eklenemeyeceği anlamına da gelir.

Yani tek yapmamız gereken dört noktalı grafa beşincisini ekleyip bu yeni noktayı diğerleriyle birleştirmektir. Fakat deneyince bunun mümkün olmadığı görülür. Örneğin beşinci noktayı en dışarı koyarsak:

1 ile 5’in arasında diğerleriyle kesişmeyen bir çizgi çizmek mümkün değildir. Ne yaparsak yapalım aynı sonuçta karşılaşırız:

Dört Renk Teoremi

Yaklaşık 160 yıl önce Francis Guthrie harita boyamak üzerine düşünüyordu:

“Düzlemde çizilmiş olan herhangi bir haritayı komşu ülkeler farklı renkte olacak şekilde boyamak için kaç renk yeterlidir?”

İnanılmaz bir şekilde cevap sadece dörttür.

Matematikle ilgili olan/olmayan hemen herkesin anlayabileceği basitlikteki bu soru ilk defa 1852’de Francis Guthrie tarafından ortaya atılmıştı. Ancak 120 yıl sonra (1976’da) dört rengin yeterli olduğu bilgisayarda 1936 farklı senaryo incelenerek ispatlanmıştı. Bu ispat çok önemlidir çünkü tarihte ilk kez bir matematik teoremi bilgisayar kullanılarak ispat edilmişti.

Bi’ Göz Atmakta Fayda Var

20190423_003916.jpg

Yukarıdaki grafa dördüncü noktayı ekleyin ve diğerlerine çizgilerle bağlayın. (Bunu yaparken dördüncü noktayı istediğiniz yere koymakta serbestsiniz.)

Şimdi elinizdeki grafa bakın: Dört noktadan herhangi biri çizgilerin içinde kalmış değil mi?

Bunu engellemenin yolu var mı?

Neden var/yok?

M. Serkan Kalaycıoğlu

 

Matematik Atölyesi – Graf #5

Zalim Trafik Işığı

Hemen her gün aynı dört yol ağzından geçiyorum. Tabii olarak en uzun süre kırmızı yanan ışığın bulunduğu tarafı kullanmak zorundayım. Bir bakıma beklemek iyi geliyor: Hayatla ilgili bazı şeyleri düşünmeme olanak sağlıyor. Fakat düşüncelere matematik eğitiminin girmesi çok fazla zaman almıyor.

Bu kısa düşünce seanslarında aklıma takılanlardan biri matematiğin trafik ışıklarıyla ne tür bir ilgisi olabileceğiydi. Kısa bir araştırmadan sonra karşıma matematiğin en sevdiğim kısımlarından biri olan çizge teorisi çıktı.

Işık #1

Tek yön araç akışı olan ve yayaların karşıdan karşıya geçebildiği bir yol düşünün.Araçlar için olan ışığa A, yaya için olanaysa B diyelim:

20190419_014641.jpg

Bu durumda kaza olmaması için A’da yeşil renk yanarken B’de kırmızı, B’de yeşil yanarken ise A’da kırmızı yanmalı. Her iki ışığın da kırmızı yanması kaza yok demekse de anlamsızdır; çünkü öyle bir durumda kimse yerinden kıpırdayamamış olur:

20190419_014707.jpg

Bu durumu çizge teorisinde nokta ve çizgi olarak da gösterebiliriz. A ve B noktalar olurken, aralarında çizgi bulunması noktaların farklı renklerde olduğunu gösterir:

20190419_014721.jpg

Aynı şeyi alan boyama ile de göstermek mümkündür: A ile B komşu iki ülke gibi düşünülebilir. Komşu ülkeler birbirleriyle karışmasın diye farklı renklerde boyanır:

20190419_014817.jpg

Işık #2

İkinci örnekte gidiş-geliş bir yol ve yayalar için konan trafik ışıkları olsun. Araçlar için olan trafik ışıkları A ve B, yayalar için olansa C harfiyle gösterilsin:

20190419_014838.jpg

Bu yolda C kırmızıyken A ile B’nin her ikisi veya herhangi biri yeşil yanabilir. C yeşilken ise A ile B’nin her ikisi de kırmızı olmalıdır:

20190419_014858.jpg

Hepsinin kırmızı olduğunda kaza olmayacaksa da kimse bir yere gidemediği için bu durumu es geçeriz.

İkinci trafik ışığını çizge teorisinde ve harita boyamayla aşağıdaki gibi ifade edebiliriz:

20190419_014930.jpg

Kurallar belirlendikten sonra çizge teorisinin trafik ışıklarının yanış şeklini ne kadar daha sade açıkladığını görebiliyoruz.

Işık #3

İki yönlü bir yolda sağa dönüş ve yayalar için iki ışık koyulmuş bir durumu ele alalım:

20190419_014947.jpg

Bu sefer öncekilere kıyasla görünürde çok daha karmaşık bir durumla karşı karşıyayız:

20190419_015005.jpg

Fakat çizge teorisi ve harita boyamayla karmaşa çözülür:

Kaç Renk Yeter

İki nokta arasında bir çizgi varsa bu noktaların farklı renkte olması gerektiğini düşünerek aşağıdaki grafleri boyayalım.

Kromatik Sayı: Herhangi bir grafte renklendirme/boyama yaparken amaç en az sayıda renk kullanmaktır. İşte bu sayıya bir grafin kromatik sayısı denir.

Burada en az 3 renk gerekir. Yani grafin kromatik sayısı 3’tür. Grafe bir nokta ve çizgi daha ekleyelim:

Nokta ve çizgi sayısı artmasına rağmen kromatik sayı 2’ye düşer. Bir nokta ve çizgi daha eklersek:

Kromatik sayı yine 3 olur. Son bir defa daha nokta ve çizgi ekleyelim:

Kromatik sayı tekrar 2’ye düştü.

Devam edecek…

Bi’ Göz Atmakta Fayda Var

Burada gerçekleşen şey ne? Ne fark ettiniz? Neden öyle oluyor?

Kromatik sayıyı nasıl artırabilirsiniz?

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Geometri #18

Pastayı Koru

Bugün okula kutsal pasta geliyor. Pasta okuldaki odalardan birinde ziyaret edilebilecek. Siz kutsal pastanın korunması için organizasyonu sağlamakla görevlisiniz. Amacınız en az sayıda koruma ile pastanın sürekli göz altında tutulabilmesi.

Korumalarla ilgili bir bilgi: Bir müze koruması belli bir noktada durur ve bulunduğu odayı o noktadan inceler. Tabii ki koruma kendi etrafında 360 derece dönebilir.

Kutsal pastanın sergileneceği odanın krokisi aşağıdaki gibidir:

20190328_130114.jpg

Bu odaya en az kaç koruma gerekir?

Çokgen Şeklinde Odalar

Bu sorunun çözümüne en basit çokgen olan üçgenden başlayarak ulaşmaya çalışacağız.

Örnek 1: Üçgen oda.

İlk örnekte oda üçgen şeklinde olsun. Böyle bir odada kutsal pasta nereye konulursa konsun tek bir koruma onu her an gözleyebilir:

Örnek 2: Dörtgen oda.

Burada da yine tek bir koruma yeterli gelir:

Soru: Tüm çokgen şeklinde odalarda bir koruma yeterli gelir mi?

İçbükey-Dışbükey Farkı: Bir çokgende iç açıların tamamı 180 derecenin altındaysa o çokgen dışbükeydir. Açılardan herhangi biri dahi 180 derecenin üzerindeyse çokgen içbükey olur.

Dışbükey çokgenlerin tamamı tek bir korumayla korunabilir. Aynı şey her içbükey çokgen için söylenemez.

Kutsal pastanın bulunduğu oda içbükey bir çokgendir. Önce basit bir içbükey çokgen inceleyelim:

20190328_123117.jpg

İçbükey çokgenliğe yol açan noktada duran bir koruma, odanın her yerine hakim olur:

20190328_123216.jpg

Peki çokgen aşağıdaki gibiyse:

20190328_123606.jpg

Bu tür bir odada tek koruma yeterli gelmez:

20190328_123732.jpg
Koruma taralı alanı göremez.

Sanat Galerisi Problemi

Daha karmaşık oda krokilerine geçmeden önce, koruma sayısıyla ilgili bir algoritma olup olmadığına bakmamız gerekir. İlk kez 1973 yılında Victor Klee ismindeki bir matematikçi tarafından ortaya atılan sanat galerisi problemini çözmek için üçgenleme olarak bilinen bir yöntem kullanılır.

Üçgenleme: Bir çokgeni üçgenlere bölme işlemidir.

Önce verilen planı üçgenlere ayıralım:

Daha sonra üçgenlerdeki köşelere renkler verelim. Aynı üçgendeki köşeler birbirinden farklı renkte olmak zorundadır:

20190328_124639.jpg

En az sayıda kullanılan renk, en az koruma sayısını verir. Korumalar bu renklerin bulunduğu köşelerde durduğu sürece odada görünmeyen bir yer kalmaz:

20190328_124931.jpg
Burada iki çözüm vardır: Korumalar 2 veya 3 numaraları köşelerde durarak odayı koruyabilir.

Çözüm

O halde kutsal pastanın bulunduğu odaya en az kaç koruma gerektiğini ve bu korumaların nerede durmak zorunda olduğunu bulabiliriz. Önce pastanın bulunduğu odanın krokisini üçgenlere ayıralım:

20190328_130612.jpg

Daha sonra üçgenlerin köşelerini boyayalım:

20190328_130833.jpg

Sonuçta üç renk aşağıdaki kadar kullanılmıştır:

20190328_131241.jpg

En az kullanılan renkler 1 ve 3’tür. Bu da bize odayı korumak için gereken sayıyı verir: 6. Bu noktalarda konuşlandırılan korumalar kutsal pastayı sürekli göz önünde bulundurur.

Bi’ Göz Atmakta Fayda Var

  1. Kutsal pastanın bulunduğu odada aşağıdaki gibi sütunlar bulunsaydı çözüm nasıl olurdu?
    20190328_131619.jpg
  2. Çokgenlerin köşe koruma sayısı arasında nasıl bir ilişki var?

M. Serkan Kalaycıoğlu