Matematik Atölyesi – Oyun #12

Üçgen İstilası

İki kişilik bir oyun olan üçgen istilasını oynamak için öncelikle bir üçgen çizin ve bu üçgenin köşelerine farklı isimler verin (1-2-3 gibi):

20190530_145646.jpg

Daha sonra büyük üçgenin içine aşağıdaki gibi küçük üçgenler çizin:

20190531_125538.jpg

(Küçük üçgen sayısı istenildiği kadar artırılabilir.)

Üçgende köşeleri aşağıdaki kurallara uyarak adlandırın:

a. 1-2 kenarında bulunan köşeler 1 veya 2 olabilir.

b. 1-3 kenarında bulunan köşeler 1 veya 3 olabilir.

c. 2-3 kenarında bulunan köşeler 2 veya 3 olabilir.

d. Büyük üçgenin içerisinde kalan köşeler 1, 2 veya 3’ten herhangi biri olabilir.

Oyunun İşleyişi

  • Yukarı kuralları izleyerek sırayla köşeler adlandırılır.
  • Oyuncular son köşesini adlandırdıkları üçgenleri istila etmiş sayılır.
  • Amaç 1-2-3 üçgeni yapmamaktır. En az 1-2-3 üçgeni istila etmiş olan kişi oyunu kazanır.

Sperner’in Üçgeni

Üçgen istilası oyunu aslen Sperner üçgeninden gelir. Emanuel Sperner’in bulduğu Sperner üçgeni, çok basit kuralları olmasına rağmen şaşırtıcı bir sonucu içerisinde barındırır. Sperner üçgeni aynı üçgen istilasında olduğu gibi büyük bir üçgenin içine küçüklerinin çizilmesi ve bunların köşelerinin adlandırılmasıyla elde edilir.

Kurallara göre köşeler etiketlendiğinde muhakkak köşeleri 1-2-3 olan bir üçgen bulunur:

20190531_125917.jpg
Örnekte üç tane 1-2-3 üçgeni vardır.

Hatta Sperner bu kurallar çerçevesinde her zaman tek sayıda 1-2-3 üçgenleri olacağını söyler.

Bu yüzden de üçgen istilası hiçbir zaman beraber bitmez.

Çıkmaz Sokak

Sperner üçgeninde 1 ve 2 arasında kalan kenarlar kapı, kalan tüm kenarlar ise duvar olsun. Bir 1-2 kapısından başlanan yürüyüşte karşılaşılan tüm kapılar kullanılmak zorundadır:

Bu durumda üçgenin dışından başlayan bir yürüyüş iki şekilde bitebilir:

  1. Büyük üçgenin içinde bulunan bir 1-2-3 üçgeninde:

    Sol kenarda üç tane 1-2 kapısından başlanan yürüyüşlerin hepsi 1-2-3 üçgenlerinde bitmiştir.

  2. Büyük üçgenin dışında:

    Sol üstteki kapıdan başlayan yürüyüş üçgenin dışında bitmiştir.

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

Matematik Atölyesi – Şans #6

Ne kadar şans?

Matematiğin işe yaramazlığından bahseden insanların (tamamı olmasa da) önemli bir kısmı olasılık konusunda kötü oldukları için sürekli zarara uğradıklarından bihaberdir. Halbuki hangi insana sorsanız olasılık konusunda kendinden emin konuşur.

Buna en güzel örneklerden biri kumarhane tecrübesi olanların hemen anlayacağı rulet oyunudur. 0’dan 36’ya kadar sayıların bulunduğu rulet masasında her turda top rulet çarkına bırakılır. Rulet oyununda topun çarkın üzerinde hangi sayıda duracağını tahmin etmek dışında da seçenekleriniz var. Mesela sayının renginin kırmızı ya da siyahtan hangisi olacağını veya hangi satır/sütundaki sayının gelebileceğini de tahmin etmeye çalışabilirsiniz.

Burada ben kırmızı-siyah olasılığı üzerinde duracağım. Toplam 37 sayının 18’i kırmızı, 18’i siyahtır. (Tek eksik olan sıfırın rengi bunların ikisi de değildir.) O halde ruletin bir turunda kırmızı veya siyah renkli bir sayının gelme olasılığı eşit ve 18/37’dir.

images55

Soru: Diyelim ki bir rulet masasında oturuyorsunuz ve art arda sekiz tane kırmızı renkli sayı geldi. Bir sonraki turda hangi renge oynardınız: Kırmızı mı? Siyah mı?

Bunun için ufak bir anket düzenledim. Sorduğum on arkadaşımın içinden sadece ikisi kırmızıyı seçeceğini söylerken altısı siyahı, kalan ikisiyse herhangi biri cevabını verdi. İşin garibi hemen herkesin daha ben sormadan şansların eşit olduğunu belirtmesiydi. Yani burada seçim yaparken matematik değil duygular ön plana çıkıyor.

Doğru cevapsa “fark etmez” olmalıdır. Her turda siyah ve kırmızının 18/37’şer, sıfırın ise 1/37 ihtimali vardır. Önceki turlarda ne geldiği hiçbir şeyi değiştirmez. Psikolojiniz hariç…

Uyarı: Kumar tüm kötülüklerin anasıdır. Uzak durun.

“Kumarbaz mısın?”

İki ve daha fazla kişinin oynayabileceği bir oyun olan “Kumarbaz mısın?” için gereken tek şey standart bir zardır.

indir (12)

Kurallar:

  • Oyuncular sırayla zar atar.
  • Gelen sayıları toplar. Amaç 50’yi ilk geçen olmaktır.
  • Eğer oyunculardan biri kendi turunda 6 atarsa, o turda kazandığı puanları kaybeder ve sıra diğer oyuncuya geçer.
  • Oyuncular kendi turlarında 6 gelmediği sürece zar atmaya devam edebilir ve istedikleri yerde turu bitirebilir.

Örneğin bir oyuncunun ilk zarı 4 gelsin. Zar 6 gelmediği için oyuncunun iki şansı vardır: Zarı ikinci defa at veya turu bitir ve 4 puanı toplam puanına ekle. Diyelim ki oyuncu devam etmeye karar verdi ve zar bu sefer 5 geldi. Oyuncu için yine aynı iki şans vardır: Ya puanlarını al (4+5=9 puan) ve turu bitir veya üçüncü defa zar at.

Ne öğrenilir?

Oyunda kaçınılması gereken tek zar 6’dır. Bu da toplam altı sayıdan sadece biridir. Yani ilk zar atıldığında 5/6 = 0,833… (diğer bir deyişle %83)  ihtimalle istediğiniz zarı elde edersiniz. Bunu iki defa üst üst yapma ihtimaliniz ise (5/6)*(5/6) = 0,694… olur. İkinci denemenizde %70’in altına düşülür.

O halde 10 defa üst üste zar attığınızda 6 gelme ihtimalini artırmış olursunuz. (%60 ihtimalle 6 gelir.)

Fakat her zar atılışına tek tek baktığımızda her zaman 5/6 ihtimali olduğunu görürüz. Bunu düşününce 6 gelme olasılığının zamanla daha yüksek olması gözden kaçmış olur.

Başta düşük olan ihtimal zamanla yüksek ihtimale dönüşür. Örneğin 100 defa zar attığınızda 6 gelmesi neredeyse kesindir:

screenshot_20190326-155011_calculator.jpg
%99,99999879 ihtimalle 6 gelir.

Sonuç: Bir zar 100 defa atıldığında 6 gelmesi neredeyse kesinken, her atış tek tek incelendiğinde bu ihtimal hep 1/6’dır. İşte düşük ihtimalin zamanla yüksek ihtimale dönüşmesi buradan kaynaklanır.

O halde kendinize şu soruyu sormanız gerekir: “Kumarbaz mısın?” oynarken ne zaman durmanız gerekir?

Bi’ Göz Atmakta Fayda Var

“Kumarbaz mısın?” oyununu biraz değiştirelim. Diyelim ki turun bitmesini gelen zar etkilemesin. İlk oyundan en büyük farklar şunlardır:

  • Atılan tüm zarlar geçerli olsun.
  • Bir oyuncunun toplam sayısı 5, 10, 15, 20, 25, 30, 35, 40 veya 45’ten biri olduğunda oyuncu topladığı tüm puanları kaybetsin ve zar atma sırası diğer oyuncuya geçsin.

Bu oyunda nasıl bir strateji izlerdiniz? Bir önceki oyuna göre ne gibi farklılıklar görüyorsunuz?

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Graf #4

2014 yılının Kasım ayında Rusya’nın St. Petersburg şehrinde bulunan dünyaca ünlü Hermitage müzesini ziyaret etmiştim. İçinde 1057 tane oda olan Hermitage’ı baştan sona yürüyen biri 22 km mesafe kat etmiş olur. Müzede bulunan eserlerin tamamına bakmak istiyorsanız, her esere sadece 1 dakika ayırsanız bile bu işi 11 yıldan önce bitirmenin mümkün olmadığını bilmeniz gerekir.

hermitage-map-st-petersburg
Hermitage’ın planı.

Bu yüzden Hermitage’ı sadece birkaç saatliğine ziyaret etmeye çalıştığımda nerede ne kadar süre geçirmem gerektiğini iyi ayarlamalıydım. Çünkü devasa müzeyi kısa sürede gezmem, ama bunu yaparken ilgimi çeken eserleri görmem gerekiyordu.

Aslında bu, çok orijinal bir problem değil. Hemen herkes günlük yaşamında bu tür problemlerle karşılaşır: “Ev-iş arasında hangi saatte hangi yolu kullanmalı?” gibi.

Postacının Yolu

St. Petersburg’da bu problemle karşılaşmam çok hoş bir tesadüftü. Çünkü Petersburg 18. yüzyılda ünlü matematikçi Leonhard Euler’e ev sahipliği yapmıştı. İlk graf yazısından hatırlayacağınız üzere Euler Königsberg’in yedi köprüsü problemiyle birlikte çizge teorisinin ortaya çıkmasına önayak olmuştu.

Königsberg probleminden 230 yıl sonra 1960’da Çinli bir matematikçi olan Mei-Ko Kwan soruyu biraz daha farklı şekilde ele almıştı:

Bir postacı rotasındaki evlere elindeki mektupları dağıtmak üzere posta ofisinden ayrılır. Postacının en kısa sürede tüm evlere uğrayıp tekrar posta ofisine dönmesi için nasıl bir rota izlemesi gerekir?

indir
Mei-Ko Kwan

Kwan’a ithafen Çinli Postacı Problemi olarak bilinen bu problemde önemli olan detaylar şunlardır:

  • Postacı rotası üzerindeki tüm sokakları kullanmalıdır. Fakat her sokak sadece ama sadece bir defa kullanılmalıdır.
  • Postacının rotasında başlangıç ve bitiş posta ofisinde olmalıdır.
  • Postacının amacı en kısa sürede yukarıdaki iki şartı yerine getirmektir.

Çizge Teorisinin Gücü

Mei-Ko Kwan Çinli Postacı Probleminin çözümünde Euler’in Königsberg’in yedi köprüsü için ortaya keşfettiklerinden yararlanmıştı. Kwan’a göre problem Euler’in yaptığı gibi graf haline getirebilirdi. Postacının gitmesi gereken mahalleler noktalarla, mahalleler arasındaki mesafeler (yani sokaklar) ise çizgilerle gösterilebilir.

Örnek Graf:

20190324_210039
A, B, C, D ve E harfleri mahalleri, aralarındaki çizgiler yolları gösteriyor. Çizgilerin üzerindeki sayılarsa postacının bir mahalleden diğerine ne kadar sürede gittiğini ifade ediyor.

Hatırlatma

Euler döngüsü nedir?

Eğer bir grafta Euler döngüsü varsa o grafta bulunan tüm çizgiler bir ama sadece bir defa kullanılarak tam bir tur atılabilir demektir. Ayrıca Euler döngüsünde başlangıç ve bitiş aynı noktadadır.

Euler döngüsü ne zaman vardır?

Bir graftaki bir noktanın sahip olduğu çizgi sayısı, o noktanın derecesini verir. Eğer bir grafta Euler döngüsü varsa, o graftaki tüm noktalar çift derecelidir.

Çözüm

Anlaşıldığı üzere Çinli Postacı Probleminin çözümü için postacının rotasında Euler döngüsü olmalıdır. Örneğin postacının güzergahı aşağıdaki gibi olsun:

20190325_123338.jpg
Çizgilerin üzerindeki sayılar harfler mesafeleri (km cinsinden olsun) gösteriyor.

İlk yapılması gereken şey tüm noktaların (harflerin) sahip olduğu çizgi sayısını bulmak:

20190325_123326.jpg

Yukarı görüldüğü üzere graftaki tüm noktalar çift derecelidir. Bu sayede hiç denememize bile gerek kalmadan bu rotada Euler döngüsü olduğunu söyleyebiliriz. O halde postacının en kısa sürede görevini tamamlaması için graftaki yolları kullanması yeterlidir:

20190325_123311.jpg
En kısa güzergah 11 km sürer.

Tek dereceli noktalar varsa grafa yeni çizgiler eklenerek (yani postacı yeni yollar üretmek zorundadır) tüm noktalar çift dereceye çevrilmelidir. Peki bu nasıl yapılır?

  1. Tek dereceli noktaları bul.
  2. Bu noktaları ikili gruplara ayır.
  3. İkili gruplar arası mesafeleri bul. En düşük mesafeliler eklenmesi gereken çizgileri belirtir.
  4. Çizgileri grafa ekle.

Yukarıda verdiğim mahalle örneği üzerinden giderek açıklamaya çalışalım. Sorun postacının A mahallesinden başlayıp yine A’da bitecek gününü en kısa sürede tamamlamak istemesidir.

Önce her mahallenin (yani noktanın) sahip olduğu yol sayısına (yani çizgi sayısına) bakalım:

20190324_210039
A ve D’nin 3’er, B, C ve E’nin 2’şer çizgisi vardır.

Her nokta çift sayıda çizgiye sahip olsaydı burada bir Euler yolu olurdu ve postacının en kısa turu direk mesafelerin toplanmasıyla bulunabilirdi. Fakat A ve D noktalarının tek sayıda çizgiye sahip olması bunu engelliyor:

20190324_210102

Bu durumda yapılması gereken şey, tek çizgiye sahip noktalar arasında yeni yol veya yollar yapmaktır. A ve D mahalleri arasında üç farklı yol vardır. Bunlardan en kısasını bulup grafa eklersek sorumuz çözülmüş olur:

20190324_210157

A-D mahalleri arasındaki yollar yukarıdaki gibidir. Görüldüğü üzere en kısa süre direk A-D arasındaki yoldadır. O halde A-D arasına yeni bir yol eklersek postacının sorunu çözülmüş olur:

Bi’ Göz Atmakta Fayda Var

Aşağıdaki rotada A’dan başlayıp A’ya dönmesi gereken postacının en kısa yolu ne kadar süre alır? Bunu yapabilmek için kullanması gereken rota nedir?

20190324_210225

M. Serkan Kalaycıoğlu