Dört adet 4

Bu bilmecede ilkokul ve ortaokul matematik bilgileri yetecektir. Amaç dört adet 4 rakamını kullanarak 1'den 100'e kadar bütün tamsayıları bulmak. Bu sırada kullanılabilecek işlemler şunlardır:

1. Toplama
2. Çarpma
3. Çıkarma
4. Bölme
5. Parantez
6. Rakamları birbirlerine ekleme: Sadece 4'ler için geçerlidir, örneğin 44, 444, 4444 şeklinde kullanımlar olabilir.
7. Ondalık nokta: .4 = 0.4 Yani bu tür sayıları sıfır kullanmak zorunda olmadan gösterebilirsiniz.
8. Faktöryel: n! = n(n-1)(n-2)...1
9. Karekök: kök(4) = 2
10. Kuvvet: 4^4 = 256

Çözümlerin hepsinde dört adet rakam da kullanılmalıdır.

Örnek: 1 = 4/4 yanlış (sadece iki rakam kullanılmış)

            1 = 44 / 44 doğru

Bir Nim varyantı (Çözüm)

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.

1. Eğer Nim toplamı herhangi bir hamleden önce 0 ise yapılan kurallara uygun bir hamleden sonra Nim toplamı sıfırdan farklı olur.
2. 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.

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.

Bir Nim varyantı

İki kişi arasında oynanan bu oyunda 1, 3, 5 ve 7 taştan oluşan dört adet yığın var. Oyuncular sırayla istedikleri bir yığından en az bir taş alıyorlar. Sırası geldiğinde hamle yapamayan oyuncu kaybediyor. Kim kazanır ve nasıl?

Örnek:

Hamle sırası	1. yığın	2. yığın	3. yığın	4. yığın	Açıklama
A	1	3	5	7	Başlangıç pozisyonu, ilk hamleyi A oyuncusu yapacak
B	0	3	5	7	A oyuncusu birinci yığından bir taş aldı
A	0	1	5	7	B oyuncusu ikinci yığından iki taş aldı
B	0	1	3	7	A oyuncusu üçüncü yığından iki taş aldı
A	0	1	2	7	B oyuncusu üçüncü yığından 1 taş aldı
B	0	1	2	0	A oyuncusu dördüncü yığındaki bütün taşları aldı
A	0	1	1	0	B oyuncusu üçüncü yığından bir taş
B	0	1	0	0	A oyuncusu üçüncü yığından bir taş
A	0	0	0	0	B oyuncusu ikinci yığından bir taş aldı. A oyuncusu için yapacak hamle kalmadı, dolayısıyla B oyuncusu kazandı.

Kuruş tasarımı (Çözüm)

18 adet madeni para ile kolay bir çözüm var: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90. Tabii ki çözüm bu kadar kolay olsaydı Gardner bu soruya kitabında yer vermezdi. 

Öncelikle 1 kuruş değerinde bir madeni paraya ihtiyacımız var, yoksa 1 kuruş ödeyemeyiz. Şimdi soruyu çözmeye tersten devam edelim. 50 kuruşumuz varsa, iki tane kullanarak 100 kuruş da elde edebiliriz. Hedeflediğimiz bütün kuruşları aşağıdaki tabloda gösterelim. Elimizdeki kuruşları mavi ile, bu kuruşları kullanarak elde edebileceğimiz diğer değerleri de yeşil renkle gösterelim. Bu şekilde bir elek yapmaya çalışalım.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Şimdi 1 kuruşu tabloda işaretleyelim

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1)

50 kuruştan büyük değerler kullanırsak 100'den büyük değerler de elde edeceğiz ve bu soruda buna gerek olmadığından eleğimizi idareli kullanalım ve 50 kuruşu eleğimize ekleyelim

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 50)

99'u elde etmek için 50 ile 49 kuruşu toplamak gerekecek.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 49, 50)

97 kuruş için iki ihtimal var: $50 + 47 = 97$ ya da $49 + 48 = 97$. 47 kuruş 48 kuruştan daha iyi bir seçim olacaktır çünkü bu şekilde 94, 96 ve 97 kuruş elde edebiliyoruz ama 48 kuruş ile sadece 96 ve 97, yani bu durumda eleğimiz bir fazla hedef değeri daha yakalayabiliyor.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 47, 49, 50)

95 kuruş elde etmek için de iki yol var: $45 + 50 = 95$ ya da $46 + 49 = 95$.

45 kuruşun doğru olduğunu varsayarsak

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 45, 47, 49, 50)

46 kuruş doğru ise

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 46, 47, 49, 50)

Son iki tablo arasında ikinciyi seçelim, çünkü 93'ü de elde edebiliyoruz. Karşılığında 45 feda edilmiş oluyor ama buna karşı bir sonraki eleman seçimi için daha çok alan kazanacağız.

91 değerini elde etmek için 41 yeterli olacaktır ($41 + 50 = 91$).

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 41, 46, 47, 49, 50)

89 için de $39 + 50 = 89$ eşitliğine göre 39 değerini alalım.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 39, 41, 46, 47, 49, 50)

Aynı yönteme devam ederek $34 + 50 = 84$ ile 34 değerini tanımlayalım.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 34, 39, 41, 46, 47, 49, 50)

Şimdi yöntemimizden biraz sapıyor gibi gözüksek de aslında mantıklı bir hareket yapacağız. Şu anda eleğimizin sonundaki boşluklara bakarsak 79, 77 ve 76 sayılarını görüyoruz. Elimizdeki değerlerden bu şekle uygun bir grubu bulacağız. Eğer şimdiye kadar yaptığımız gibi $29 + 50 = 79$ diye düşünürsek o zaman elimizdeki sayılardan 50, 49 ve 47'yi kullanmış oluruz ve bu durumda sadece 76 ve 79 değerlerini elde edebiliriz. Fakat bunun yerine aradığımız deliklerle aynı yapıdaki 46, 47 ve 49 değerlerini alırsak $30 + 49 = 79$ ile yüksek değerli delikleri daha çabuk kapatırız. 30 için tabloya bakalım.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 30, 34, 39, 41, 46, 47, 49, 50)

Bu durumda 24'ü alırsak eleğimize sadece 74'ü ekleyebiliriz, bunun yerine 25'i alırsak (bir önceki adımdaki mantıkla) hem 74 hem de 72'yi elde ederiz. O zaman yola 25 ile devam edelim.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 25, 30, 34, 39, 41, 46, 47, 49, 50)

Şimdi eleğimize 20 kuruşu ekleyelim.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50)

62, 63 ve 65 desenini daha önceki adımlardan biliyoruz. Bu durumda 15 yerine 16 kuruş kullanmak daha iyi.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50)

Bir önceki adımdaki gibi, 8 yerine 9 kuruşu alalım.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 9, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50)

52 ve 53 için de 3 kuruşu ekleyelim eleğimize.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 3, 9, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50)

Eleğimizdeki sonraki boşluklar 45 ve 38. 45'ten küçük eleğimizdeki kuruşlardan 41'i kullanarak ($41 + 4 = 45$) bu iki boşluğu da kapatabiliriz. Diğer hiçbir değerin bu iki boşluğu aynı anda kapatamadığına dikkat edelim.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 3, 4, 9, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50)

Son olarak da en küçük boşluğu eleğimize ekleyelim: 11. Buna daha küçük değerlerle ulaşamıyoruz.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

(1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50)

Böylece 16 değişik değer ile 1'den 100'e kadar her değeri elde edebildik.

Peter Wegner'a ait çözümde ise 16 adet madeni para ile 1'den 104'e kadar her değer elde edilebiliyor: 1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52.

Kuruş tasarımı

Büyük bir para reformu yapılacaktır. Bu sefer paradan sıfır atılmayacak fakat kuruşlar yeniden tasarlanacak. 

1 kuruştan 100 kuruşa kadar herhangi bir değeri en fazla iki adet madeni para ile elde edebileceğimiz (iki madeni paranın değeri de aynı olabilir) en az sayıda farklı madeni para değerleri nelerdir? 

Eşzamanlı şapkalar (Çözüm)

Eğer bir kişi başındaki şapkayı rastgele bilmeye çalışırsa doğru tahmin yapma şansı yüzde elli olacaktır. Demek hiçbir strateji bulamazsak en kötü ihtimalle yüzde elli kurtulma şansları var. 

Şimdi problemin çözümünde kullanacağımız bazı tanımlamaları yapalım.

Gösterim kolaylığı açısından kırmızı şapkayı 1, ve mavı şapkayı da 0 ile göstereceğiz. Böylece herhangi bir şapka dağılımı ikili düzendeki bir rakam dizisiyle eşdeğer olacak. Bu ikili düzendeki şapka dağılımlarını da $D_{i}$ ile göstereceğiz. Buradaki $i$ indeksi ikili düzendeki sayının onluk düzendeki karşılığı olacak.

$i$ birden $N$'e kadar (ilk soruda $N = 3$) olmak üzere mahkumları sıra numaraları ile $m_{i}$ şeklinde göstereceğiz. Sıralamaya sağ basamaktan başlayacağız.

Hamming uzaklığı: İki şapka dağılımı arasındaki mesafeyi $d(D_{i}, D_{j})$ ile göstereceğiz ve bu da kısaca aynı uzunluktaki iki ikili düzendeki sayının farklı rakamlara sahip pozisyonlarının adedi olacak. Örnek olarak $d(000, 111) = 3$ ve $d(011, 110) = 2$ (Yani pozisyonları numaralandırmaya sağdan başlarsak, birinci pozisyondaki rakamlar farklı, ikinci pozisyondaki rakamlar aynı, üçüncü pozisyondaki rakamlar da farklı).

Şimdi Hamming uzaklığı ile biraz oynayalım.

$N$ şapka ile belli bir $D_{i}$ dağılımı için Hamming uzaklığı 1 olan $N$ farklı pozisyon vardır. Bunu görmek için tanım üzerinde düşünmek gerek. Hamming uzaklığı 1 demek sadece bir pozisyondaki rakamlar farklı demek olduğundan ve bu sayılarda $N$ farklı pozisyon olduğundan toplam $N$ farklı sayı yazabiliriz.

Örnek: 5 şapka ile 00000 dağılımına uzaklığı bir olan dağılımlar 00001, 00010, 00100, 01000 ve 10000 saylarıdır.

Bu noktada problemle ilgili bir takım gözlemler yapmaya çalışalım.

G1: Bir mahkum kendi başındaki şapkanın rengini göremediği için onun açısından olası iki dağılım vardır ve bu dağılımlar arasındaki Hamming uzaklığı birdir, çünkü diğer pozisyonlardaki rakamlar eşit olduğundan sadece kendi pozisyonundaki rakamlar farklı olacaktır.

Örnek: 5 şapka için 3. sradaki mahkum sadece beyaz şapkalar görüyorsa olası dağılımlar 00000 veya 00100 olacaktır. Bu durumda da $d(00000, 00100) = 1$ olacaktır.

G2: Belli bir D dağılımı için buna uzaklığı 1 olan dağılımlarda en fazla bir mahkum o anki dağılımın bu D dağılımına olan uzaklığının en fazla 1 olduğunu bilebilir. Her mahkum için şöyle bir yol izleyebiliriz. $i$ numaralı mahkum D dağılımından kendi pozisyonundaki rakamı çıkararak $N-1$ basamaklı bir sayı üretir. Sonra da diğer mahkumların şapkalarına göre kalan dağılımı ikilik düzende yazar. Eğer bu iki dağılım arasındaki mesafe 0 ise sadece kendi şapkası farklı olabileceğinden uzaklık da en fazla 1 olacaktır. Diğer mahkumlar aynı işlemi yaptığında kendi şapkaları hariç uzaklık zaten 1 olduğundan bu mahkumlar açısından uzaklık 1 veya 2 olacağından emin olamayacaklardır.

Örnek: 5 şapka için kararlaştırılmış dağılım 01001 olsun. O anki şapka dağılımı da 11001 olsun. Tabii ki $d(01001, 11001) = 1$. Birinci mahkum problemden kendisini çıkarırsa kararlaştırılmış dağılım 0100 ve o anki dağılım da 1100 olacaktır. $d(0100, 1100) = 1$ olduğundan bu mahkum kendi kafasında kırmızı (1) şapka varsa uzaklığın bir kalacağını ama mavi (0) şapka varsa uzaklığın ikiye çıkacağını bildiğinden emin olamayacaktır. Sadece 5. sıradaki mahkum bu uzaklığın en fazla 1 olduğundan emindir.

Burada şöyle bir notasyon tanımlayalım. $D_{i}/j$, $N$ şapka için verilen bir şapka dağılımı için j pozisyonundaki şapka çıkarıldığında kalan $N-1$ şapkalı dağılım olsun. O zaman $d(D_{i}, D_{k}) <= d(D_{i}/j, D_{k}/j) + 1$

Verilen bir $D_{i}$ şapka dağılımına olan Hamming uzaklıkları 1 olan dağılımlar kümesine $K_{1}{i}$ (1-komşuluğunda olan dağılımlar) kümesi diyelim.

G3: İki şapka dağılımı $D_{i}$ ve $D_{j}$ verilsin. Eğer $d(D_{i}, D_{j}) \ge 3 \implies K^{1}_{i} \cap K^{1}_{j} = \emptyset$. Yani iki dağılım arasındaki mesafe 3 veya daha büyükse bunların direkt komşuluğunda (yani 1-komşuluğunda) ortak dağılım yoktur. Eğer ortak bir dağılım olsaydı bu dağılım verilen iki dağılıma da 1 mesafesinde olduğundan iki dağılımın birbirine uzaklığı da en fazla 2 olacaktı (Haming uzaklığı bir metriktir ve üçgen eşitsizliğinden bu sonuç çıkar).

G4: İki şapka dağılımı $D_{i}$ ve $D_{j}$ verilsin. Eğer $d(D_{i}, D_{j}) = 2 \implies \left\vert K^{1}_{i} \cap K^{1}_{j} \right\vert = 2$. İki dağılım arasında iki pozisyondaki rakamlar farklı olduğundan kesişim kümesinde de 2 eleman vardır.

Örnek: 1010 ve 1111 verilmiş olsun. 1-komşuluğundaki ortak elemanlar $N-2$ adet ortak şapkalara sahip olacak ve bir durumda bir şapkayı birinci durumda ve diğerini ikinci durumdan, ikinci durumda da tam tersi şekilde. Yani 1110 ve 1011.

G5: Bir önceki gözlemdeki durumda en fazla iki mahkum o anki durumun kararlaştırılan durumlara uzaklığının en fazla 1 olduğunu bilecektir. İki mahkum da sadece bir kararlaştırılmış durumu bulabilecektir, diğer durum için kendisi açısından uzaklık en fazla iki olacaktır.

Örnek: 1010 ve 1111 verilmiş olsun. 1-komşuluğundaki ortak elemanlardan 1110 durumuna bakalım. Birinci mahkum ikinci durum için 1-komşuluğunda olduğunu anlayacaktır ama üçüncü mahkum bunu destekleyemeyecektir, fakat üçüncü mahkum da birinci durum için 1-komşuluğunda olduklarını bilecektir. Diğer ortak eleman 1011'de ise birinci mahkum birinci durum için 1-komşuluğunu bilecek, üçüncü mahkum ise ikinci durum için 1-komşuluğunu bilecek.

Şimdi kabaca bir strateji tanımlayalım. Bu aşamada bazı kısımlar hala çözülmemiş kalacak ama problemi başka bir probleme dönüştürmüş olacağız.

Mahkumlar $M$ adet birbirine uzaklıkları 3 (ya da mümkün değilse 2) olan dağılımlar kararlaştırsınlar. Bu dağılımları $Kod_{i}$ şeklinde gösterelim ($1 <= i <= M$). Tahmin zamanı geldiğinde mahkumlar o an gördükleri durumun bu kararlaştırılmış   kodlara uzaklıklarını hesaplasın. Eğer bu uzaklıklar her kod için birden büyük olabiliyorsa o mahkum pas geçsin. Eğer bu uzaklık bir kod için en fazla 1 oluyorsa o zaman mahkum sonuç o kod olmayacak şekilde tahminde bulunsun. Bu şekilde o kodda tanımlanmış dağılımda hepsi yanlış cevap verecek fakat buna karşın o kodun 1-komşuluğundaki her dağılım doğru tahmin edilmiş olacak. Bu da toplam olasılığı çok daha fazla artıracaktır. $M$ adet kod dışındaki her dağılım doğru tahmin edildiğinde de olasılık $\frac {2^N - M}{2^N}$ olacaktır.

Bu strateji için çözülmesi gereken sorular:

1. M = ?
2. Kodlar nasıl seçilmeli?
3. Kodlar arası uzaklık 2 olunca 1-komşuluğunda ortakkk dağılımlar olacak. Bu dağılımlarda birden fazla kişi tahminde bulunacak. Bu tahminler birbirleriyle uyumlu olacak mı?
4. Bu stratejiden daha iyi bir strateji var mıdır?

Şimdi bu sorulara cevap aramaya çalışayım.

1. $N$ mahkumla oynanan oyunda $2^N$ değişik dağılım olacağından ve seçilecek her kod için 1-komşuluğunda $N$ dağılım olacağından $M \ge \frac {2^N} {N+1}$ olacaktır.

2. Kodlar seçilirken her ikili kombinasyon arasındaki Hamming uzaklığının 3 (en kötü ihtimalle 2) olmasına dikkat edilmelidir.

3. Evet. İki kod arasındaki uzaklık 2 ve ortak dağılımlar da iki koda eşit uzaklıkta. İki mahkum da tahminlerinde seçilmiş kodlardan uzaklaşacağına göre iki kodun orta noktasında (ortak dağılımda) buluşacaklardır.

4. Bunu bilmiyorum. Literatüre bakmak lazım. $k$ pozitif bir tamsayı olmak üzere $N=2^k - 1$ şartını sağlayan mahkum sayısı için daha iyi bir çözüm yok sanırım (Ebert's version). Bu durumda da kazanma olasılığı $\frac {2^k - 1}{2^k}$ oluyor.

Son olarak üç mahkum için $Kod_{1} = 000$ ve $Kod_{2} = 111$ tanımlarsak, $d(Kod_{1}, Kod_{2}) = 3$ olduğundan $M=2$ olacak şekilde bütün dağılımları sınıflandırabiliyoruz. Sınıfları aşağıdaki tabloda görebiliriz.

$Kod_{1}$ (000)	$Kod_{2}$ (111)
001	110
010	101
100	011

Şimdi de oyuncuların yukarıdaki stratejiye göre her dağılımda verecekleri cevapları tablo halinde görelim.

Dağılım	1. mahkum	2. mahkum	3. mahkum	Sonuç
000	1	1	1	Yanlış
001	1	Pas	Pas	Doğru
010	Pas	1	Pas	Doğru
011	0	Pas	Pas	Doğru
100	1	Pas	Pas	Doğru
101	Pas	0	Pas	Doğru
110	Pas	Pas	0	Doğru
111	0	0	0	Yanlış

Dolayısı ile kazanma şansı $\frac{6}{8} = 0.75$. Yukarıda bulduğumuz formüle de bu sayıları ($M=2, N=3$) yerleştirirsek $\frac {2^N - M}{2^N} = \frac {2^3 - 2}{2^3} = \frac {6}{8} = 0.75$

Çözümde unuttuğum ve yapamadığım, dolayısıyla eksik kalan ve yanlış yerler vardır mutlaka. Bunları tamamlamak ve düzeltmek isteyenler kağıt kalem alıp çalışmaya başlayabilirler..

  

Eşzamanlı şapkalar

Padişah üç idam mahkumuna son bir şans vermek ister. Mahkumlara bir oyun oynanacağını bildirir ve kurallar açıklanır. Üç mahkum bir odaya alınacak ve her birinin başına rastgele kırmızı ya da mavi birer şapka konulacak. Her mahkum diğer mahkumların şapkalarını görebilecek ama kendi şapkasını göremeyecek ve odada başka herhangi bir iletişim yasak. Birbirlerinin şapkalarını gördükten sonra aynı anda kendi başlarındaki şapkaların renklerini ya tahmin edecekler (yani kırmızı ya da mavi diyecekler) ya da pas geçecekler. Eğer en az birisi kendi başındaki şapkanın rengini doğru tahmin eder ve hiç yanlış tahminde bulunulmazsa hepsi özgür bırakılacak. Pas geçmek yanlış tahmin olmuyor. Oyun oynanmadan önce üç mahkum da bir araya gelip bir strateji belirleyebilecekler.

Mahkumlara en yüksek kurtulma şansını verecek strateji nedir? Çözümü herhangi bir mahkum sayısı için genelleyin.

Kilitli Kutu - Sith'in intikamı (Çözüm)

Paralel posta yapılanması tabii ki Bilal'in babasına gönderdiği kutuyu posta dağıtım merkezinde tespit etti. Bu kutuyu babaya göndermek yerine üzerine kendi kilitlerini takarak Bilal'e geri gönderdiler. Bilal de kutunun babasından geldiğini düşünerek kendi kilidini açtı ve kutuyu yeniden babasına gönderdi. Bu gönderi de posta dağıtım merkezinde yakalandı ve paralel yapı kendi kilidini açarak gizli belgeye ulaştı. Gizli belge kopyalandıktan sonra tekrar kutuya konuldu ve yine kendi kilitleriyle bu sefer babaya gönderildi. Baba da planlandığı gibi kutuya kendi kilidini takarak oğluna geri gönderdi. Kutu yine dağıtım merkezinde yakalandı ve paralel kilit açılarak babaya tekrar geri gönderildi. Böylece hem baba hem de paralel yapı gizli belgeye erişmiş oldu. Bu saldırıya literatürde Man-in-the-middle attack (Aradaki adam saldırısı) denir. İki taraf da birbirleriyle haberleştiğini sanırken aslında sadece aradaki saldırganla haberleşiyorlarmış.

Bu senaryodaki saldırıyı önlemenin en kolay yolu babasının kutu kendisine ulaştığında Bilal'i telefonla arayıp haber vermesi olabilir. Bu aramadan önce alınan her kutu şüpheli olacaktır. Bu arama paketin gerçekten babadan geldiğini göstermek şeklinde saldırıyı önlemeye yönelik bir önlemdir.

Bu hikaye burada biter mi? NSA'in de dediği gibi: "Attacks always get better; they never get worse."

O zaman bir başka macerada buluşmak üzere ...

Kilitli kutu - Sith'in intikamı

Bilal'in gönderdiği kutuyu açıp gizli belgeleri okuyan baba sonunda oğlunun bir işi becerdiğini düşünerek rahat bir nefes almıştı ki telefonu acı acı çalmaya başladı. Arayan danışmanıydı ve bir felaket olduğundan bahsedip hemen internete girmesini söylüyordu. İnternete giren baba dehşetle elindeki gizli belgelerin o an herkes tarafından paylaşıldığını görüp deliye döndü. Hemen bütün danışmanlarını arayarak ertesi gün yapacağı konuşmayı belirlemek için bir kriz toplantısı düzenledi. 

Rakipleri bu belgelere nasıl ulaşabildi ve  kilitli kutu ile haberleşme nasıl daha güvenli bir hale getirilebilir?

Kilitli kutu (Çözüm)

Bilal kilidin anahtarını başka bir kutuyla göndermeye kalksa, bu kutuyu da elindeki kilitlerden biriyle kilitlemeli, yoksa anahtar rakiplerin eline geçer. Fakat babası bu yeni kilidi de açamayacağından anahtara ulaşamayacaktır. Babası Bilal'in kilidini açamadığına göre ne yapabilir? Evet, kutunun kendi açabileceği bir kilit ile kilitlenmesini sağlayabilir. 

Baba gider kendine anahtarı sadece kendinde olan bir kilit alır. Bilal kutuyu kilitleyerek babasına gönderir. Babası kutuyu alınca bir de kendi kilidiyle kilitler ve kutuyu Bilal'e geri göderir. Bilal kutuyu geri alınca kendi kilidini açar ve kutuyu üzerinde sadece babasının kilidiyle geri göderir. Böylece hayati önem taşıyan belgeler güvenli bir şekilde babaya ulaştırılmış olur.

Dayanıklılık testi: Üç küre için çözüm

İki küre için kullanılan mantıkla yola devam edelim. Yani ilk olarak $n_{1}$ numaralı kattan küreyi bırakalım. Kırılırsa kalan iki küre ile $1$'den $n_{1} - 1$'e kadar olan katları daha önceki yazıda bulduğumuz gibi $\frac {n \cdot (n+1)}{2} \ge n_{1} - 1$ eşitsizliğini çözerek $n$ adımda deneyebiliriz. Eğer ilk küre ilk denemede kırılmazsa ikinci deneme için ilk deneme katını öyle artırmalıyız ki kırılırsa kalan iki küreyle bu artış miktarını $n-1$ adımda çözebilelim. Bu yöntemi diğer adımlar için de genelleyerek bir tablo halinde gösterelim:

Adım	Artış miktarı
1	$\frac{n \cdot (n+1)}{2} + 1$
2	$\frac{(n-1) \cdot (n+2)}{2} + 1$
3	$\frac{(n-2) \cdot (n+3)}{2} + 1$
...	...

Her adımda son iki küre artışı tam deneyebildiğinden artış miktarına ilk küre için ekstra bir deneme katı daha ekleyebildik. Bu şekilde ilk küre herhangi bir adımda kırıldığında maksimum deneme sayısı adım sayısı artı iki küre durumunda artış için çözüm adım sayısı, o da eşittir $n+1$ olacaktır ($n + 1 = (n-1)+2 = (n-2) + 3 = ...$).

Yukarıdaki tabloyu kullanarak birinci küre için deneme yüksekliklerini yazalım.

Adım	Deneme yüksekliği
1	$\frac{n \cdot (n+1)}{2} + 1$
2	$\frac{n \cdot (n+1)}{2} + \frac{(n-1) \cdot (n)}{2} + 2$
3	$\frac{n \cdot (n+1)}{2} + \frac{(n-1) \cdot (n)}{2} + \frac{(n-2) \cdot (n-1)}{2} +3$
...	...

Artış miktarlarını topladığımız zaman $n+1$ adım sonunda eksiksiz taranabilecek yükseklik bulunur. Basit bir değişken dönüşümüyle bu tabloyu üç küre için $n$ adımda çözümü verecek şekilde yazabiliriz.

Adım	Deneme yüksekliği
1	$\frac{n \cdot (n-1)}{2} + 1$
2	$\frac{n \cdot (n-1)}{2} + \frac{(n-1) \cdot (n-2)}{2} + 2$
3	$\frac{n \cdot (n-1)}{2} + \frac{(n-1) \cdot (n-2)}{2} + \frac{(n-2) \cdot (n-3)}{2} +3$
...	...

Toplam yükseklik = $\sum\limits_{i=1}^n {\frac{i \cdot (i-1)}{2} + 1} = \frac{1}{2} \sum\limits_{i=1}^n {i^2} - \frac{1}{2} \sum\limits_{i=1}^n {i} + \sum\limits_{i=1}^n {1} = \frac {1}{12} n \cdot (n+1) \cdot (2\cdot n + 1) - \frac {1}{4} n \cdot (n+1) + n$

$\sum\limits_{i=1}^n {i^2}$ toplamı için bir formül bulmaya çalışalım. Bunun için önce formülün üçüncü derece bir polinom şeklinde yazılabileceğini var sayalım. Yani
$\sum\limits_{i=1}^n {i^2} = a \cdot n^3 + b \cdot n^2 + c \cdot n + d$

$a, b, c, d$ değerlerini bulmak için kare toplamların ilk dört değeri için denklemler yazalım ve bu dört bilinmeyenli dört denklemi çözelim.

$a + b + c + d = 1$            (1)
$8 \cdot a + 4 \cdot b + 2 \cdot c + d = 1 + 4 = 5$            (2)
$27 \cdot a + 9 \cdot b + 3 \cdot c + d = 1 + 4  + 9= 14$            (3)
$64 \cdot a + 16 \cdot b + 4 \cdot c + d = 1 + 4 + 9 + 16 = 30$            (4)

İlk önce $d$ değişkenlerinden kurtulmak için (2) - (1), (3) - (2) ve (4) - (3) denklemlerini hesaplayalım.

$7 \cdot a + 3 \cdot b + c = 4$            (5)
$19 \cdot a + 5 \cdot b + c = 9$            (6)
$37 \cdot a + 7 \cdot b + c = 16$            (7)

Şimdi $c$ değişkenlerinden kurtulalım. Bunun için tabii ki (6) - (5) ve (7) - (6) farklarını hesaplayacağız.

$12 \cdot a + 2 \cdot b = 5$            (8)
$18 \cdot a + 2 \cdot b = 7$            (9)

(9) - (8) ile $b$ katsayısını ortadan kaldırırsak

$6a = 2 \implies a = \frac{1}{3}$ buluruz.

Bu değeri (8)'de yerine koyup $b$ katsayısını bulalım.

$12 \cdot \frac{1}{3} + 2 \cdot b = 5 \implies b = \frac {1}{2} \cdot (5 - 4) = \frac {1}{2}$

$a$ ve $b$ değerlerini şimdi (5) denklemine koyalım.

$7 \cdot \frac{1}{3} + 3 \cdot \frac{1}{2} + c = 4 \implies c = 4 - \frac{7}{3} - \frac{3}{2} = \frac{1}{6}$

Son olarak hepsini (1) denklemine koyalım ve $d$'yi bulalım.

$\frac{1}{3} + \frac{1}{2} + \frac{1}{6} + d = 1 \implies d = 1 - \frac{1}{3} - \frac{1}{2} - \frac{1}{6} = 0$

Var sayımımıza göre $\sum\limits_{i=1}^n {i^2} = \frac{1}{3} \cdot n^3 + \frac{1}{2} \cdot n^2 + \frac{1}{6} \cdot n = \frac{1}{6} \cdot n \cdot (n+1) \cdot (2n + 1)$

Şimdi formülümüzün doğruluğunu tümevarımla test edelim.

önce formülü $n=1$ için test edelim.

$\frac{1}{6} \cdot 1 \cdot (1+1) \cdot (2 \cdot 1 + 1) = \frac{1}{6} \cdot 1 \cdot (2) \cdot (3) = 1$

Şimdi formülü $n$ için doğru kabul edip $n+1$ için doğru olup olmadığına bakalım.

 $\frac{1}{6} \cdot n \cdot (n+1) \cdot (2n + 1) + (n+1)^2 = \frac{1}{6} \cdot n \cdot (n+1) \cdot (2n + 1) + n^2 + 2 \cdot n +1 = \frac{1}{6} (2 \cdot n^3 + 3 \cdot n^2 + n)  + n^2 + 2 \cdot n +1 = \frac{1}{6} (2 \cdot n^3 + 3 \cdot n^2 + n)  + \frac{1}{6}(6 \cdot n^2 + 12 \cdot n +6) =  \frac{1}{6}(2 \cdot n^3 + 9 \cdot n^2 + 13 \cdot n + 6) = \frac{1}{6} \cdot (n+1) \cdot (n+2) \cdot (2 \cdot n + 3)$

Demek ki formül $n+1$ için de doğruymuş. Böylece formülümüzün bütün $n \ge 1$ doğal sayıları için doğru olduğunu ispatladık.

Şimdi toplam yükseklik için formülü tekrar yazalım.

Toplam yükseklik = $\sum\limits_{i=1}^n {\frac{i \cdot (i-1)}{2} + 1} = \frac{1}{2} \sum\limits_{i=1}^n {i^2} - \frac{1}{2} \sum\limits_{i=1}^n {i} + \sum\limits_{i=1}^n {1} = \frac {1}{12} n \cdot (n+1) \cdot (2\cdot n + 1) - \frac {1}{4} n \cdot (n+1) + n = \frac {1}{6} n \cdot (n^2 + 5)$

$N$ katlı bir bina için $\frac {1}{6} n \cdot (n^2 + 5) \ge N$ eşitsizliğini n için çözersek gereken maksimum deneme sayısının en küçük değerini buluruz.

Çözümlerde eşitsizliğin derecesi küre sayısına eşit olduğunu görüyoruz, yani iki küre için ikinci derece bir eşitsizlik,  üç küre için de üçüncü derece bir eşitsizlik. Küre sayısı arttıkça eşitsizliğin derecesi de artacaktır. Daha yüksek sayılı küreler için eşitsizlikler aynı mantıkla bulunabilir.

Bu soruyla ilgili bahsetmek istediğim bir şey de verilen bir $N$ için en düşük maksimum deneme sayısının alt limiti iki tabanına göre $\log N$ ile verilir. Yani bu sayıda ya da daha fazla küremiz var ise yapılması gereken tek şey ikili arama algoritmasını kullanmaktır. Yani kısaca her adımda kalan aralığı eşit iki parçaya ayıracak şekilde deneme katını seçmek gerek. Bu şekilde yukarıda verilen adım sayısında her kata ulaşmak mümkün.