Bu oyunun çözümü için biraz ikilik düzen ve xor işlemi kullanacağız. Yığınlardaki taş miktarlarını ikilik düzende yazalım.
$1 = 2^0 = 1_{2}$
$3 = 2^1 + 2^0 = 11_{2}$
$5 = 2^2 + 2^0 = 101_{2}$
$7 = 2^2 + 2^1 + 2^0 = 111_{2}$
Kimin kazanacağını bulmak için yapmamız gereken, bu dört yığını da birbirleriyle xor işlemine sokmak. Önce kısaca xor işlemini hatırlayalım.
| x | y | $x \oplus y$ |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
xor toplamı, eğer iki bit farklı ise 1, aynı ise 0'dır.
Şimdi $1_{2} \oplus 11_{2} \oplus 101_{2} \oplus 111_{2}$ işlemini yapalım. Bunun için basamakları alt alta yazıp aynı basamaklardaki birlerin adedine bakacağız. Eğer tek sayıda 1 varsa toplamda o basamağın değeri 1, çift sayıda 1 varsa 0 olacaktır.
| 1 = | 1 | ||
| 3 = | 1 | 1 | |
| 5 = | 1 | 0 | 1 |
| 7 = | 1 | 1 | 1 |
| $\oplus$ | 0 | 0 | 0 |
Bu bulduğumuz sayıya literatürde Nim toplamı denir. Eğer bu sayı 0'dan farklı ise ilk oynayan, 0 ise ikinci oynayan kazanır. Bu sonuç yığın sayısından ve her yığındaki taş adedinden bağımsızdır.
Bunu görmek için ispatları nispeten kolay olan iki özelliği kullanmak lazım.
Bunu görmek için ispatları nispeten kolay olan iki özelliği kullanmak lazım.
- Eğer Nim toplamı herhangi bir hamleden önce 0 ise yapılan kurallara uygun bir hamleden sonra Nim toplamı sıfırdan farklı olur.
- Eğer bir hamleden önce Nim toplamı sıfırdan farklı ise toplamı 0 yapacak bir hamle vardır.
Dolayısı ile ilk hamleden önce toplam sfırdan farklı ise ilk oyuncu bu toplamı sıfır yapar ve ikinci oyuncu ne yaparsa yapsın toplam sıfırdan farklı olacaktır. Bu yöntem hiç taş kalmayana kadar böyle gidecektir. Benzer şekilde sorudaki durumda ilk oynayan oyuncu mecburen toplamı sıfırdan farklı bir değere getirecektir ve ikinci oyuncu bu toplamı yine sıfırlayacaktır.
Sıfırdan farklı bir Nim toplamını sıfıra getirmek için kolay sayılabilir bir yöntem var.
Yöntemi görmek için bir örneğe bakalım. 3, 5 ve 8 yığınlarımız olsun.
Toplam görüldüğü gibi sıfır değil. Toplamda bir olan en soldaki basamağı buluyoruz. Yığınlardan o basamağı bir olan bir tanesini seçiyoruz. Bu özelikte en az bir tane yığın olmalı, yoksa toplamdaki bu basamak sıfır olurdu. Örneğimizde bu 8 taş içeren yığın oluyor. Şimdi Nim toplamı ile 8'i xor ile topluyoruz. $1000_{2} \oplus 1110_{2} = 0110_{2}$. Dikkat edilirse bu şekilde bir toplama her zaman o yığının değerinden küçük olacaktır. O basamağın solu hem yığında hem de yeni toplamda aynı olmalıdır çünkü Nim toplamında bu basamaklar sıfırdı. Eğer bu basamağa d basamağı dersek, bu toplama işi o yığının değerini $2^d$ kadar azaltacak ama sağdaki basamaklar ise bu değeri en fazla $2^d - 1$ artırabileceklerdir. Bu durumda o yığının değerinin yeni toplamdan her zaman daha büyük olduğunu göstermiş olduk. Yapılacak hamle de yığındaki miktardan yeni toplamın değeri kadar taş almak olacaktır. Örneğimize dönersek, yeni toplamı $0110_{2} = 6$ bulmuştuk. Yani 8'li yığından $8 - 6 = 2$ taş alabiliriz ve bu yığının değeri yeni toplama eşit olur. Şimdi bu durumdaki Nim toplamının sıfır olduğunu görelim.
Bu işlemlerin ispatları gerçekten de kolaydır. Yukarıda da linkini verdiğim wikipedia adresinde bu ispatlar bulunabilir. Ayrıca Matematik Dünyası dergisinin eski sayılarının birinde de bu oyun ve daha başka varyantları incelenmişti.
| 3 = | 0 | 0 | 1 | 1 |
| 5 = | 0 | 1 | 0 | 1 |
| 8 = | 1 | 0 | 0 | 0 |
| $\oplus$ | 1 | 1 | 1 | 0 |
Toplam görüldüğü gibi sıfır değil. Toplamda bir olan en soldaki basamağı buluyoruz. Yığınlardan o basamağı bir olan bir tanesini seçiyoruz. Bu özelikte en az bir tane yığın olmalı, yoksa toplamdaki bu basamak sıfır olurdu. Örneğimizde bu 8 taş içeren yığın oluyor. Şimdi Nim toplamı ile 8'i xor ile topluyoruz. $1000_{2} \oplus 1110_{2} = 0110_{2}$. Dikkat edilirse bu şekilde bir toplama her zaman o yığının değerinden küçük olacaktır. O basamağın solu hem yığında hem de yeni toplamda aynı olmalıdır çünkü Nim toplamında bu basamaklar sıfırdı. Eğer bu basamağa d basamağı dersek, bu toplama işi o yığının değerini $2^d$ kadar azaltacak ama sağdaki basamaklar ise bu değeri en fazla $2^d - 1$ artırabileceklerdir. Bu durumda o yığının değerinin yeni toplamdan her zaman daha büyük olduğunu göstermiş olduk. Yapılacak hamle de yığındaki miktardan yeni toplamın değeri kadar taş almak olacaktır. Örneğimize dönersek, yeni toplamı $0110_{2} = 6$ bulmuştuk. Yani 8'li yığından $8 - 6 = 2$ taş alabiliriz ve bu yığının değeri yeni toplama eşit olur. Şimdi bu durumdaki Nim toplamının sıfır olduğunu görelim.
| 3 = | 0 | 0 | 1 | 1 |
| 5 = | 0 | 1 | 0 | 1 |
| 6 = | 0 | 1 | 1 | 0 |
| $\oplus$ | 0 | 0 | 0 | 0 |
Bu işlemlerin ispatları gerçekten de kolaydır. Yukarıda da linkini verdiğim wikipedia adresinde bu ispatlar bulunabilir. Ayrıca Matematik Dünyası dergisinin eski sayılarının birinde de bu oyun ve daha başka varyantları incelenmişti.
Hiç yorum yok:
Yorum Gönder