Matematik Olimpiyatı 2023, 2. Aşama, Soru 3

Rakamlarının biri 1, biri 2, ..., biri 9 olan 9 basamaklı tüm sayılara dengeli sayı diyelim. Tüm dengeli sayıların yan yana ve küçükten büyüğe doğru yazılarak oluşturduğu rakam dizisi \(S\) olsun. \(S\) dizisindeki \(k\) ardışık terimden oluşan herhangi iki alt dizinin birbirinden farklı olmasını sağlayan en küçük \(k\) değerini bulunuz.

Şıklar:


Çözüm:
Cevap 17. 


Öncelikle, dizinin iki farklı yerinde geçen 16 uzunluklu bir alt dizi örneği verelim. Bu dizideki ilk iki dengeli sayı 


\[1234567891234567908\]


olduğu için 2345678912345679 alt dizisi bu sayıların arasında geçer. Şimdi, 234567891 dengeli sayısının geçtiği yere bakalım. Bu sayıdan bir sonra geçen sayı 234567918 olacağı için, bu iki sayı yan yana yer alır ve ilk sayının 9 basamağı, ikinci sayının 7 basamağıyla oluşan 16 ardışık terimin oluşturduğu alt dizi yine 2345678912345679 olur, böylece bu alt dizi 2 farklı yerde geçer. Şimdi, \(S\) dizisinde 17 uzunluklu herhangi bir alt dizinin iki farklı yerinde geçmesinin mümkün olmadığını gösterelim. Öncelikle bir gözlem ile başlayalım. 


**İddia:** \(D_1\), \(D_2\) sayıları \(S\) dizisindeki iki ardışık dengeli sayı olsun ve \(n \le 8\) bir pozitif tam sayı olsun. \(D_1\) sayısının ilk \(k\) basamağının oluşturduğu sayı \(P_1\) ve \(D_2\) sayısının ilk \(k\) basamağının oluşturduğunu sayı \(P_2\) olsun. \(P_1\) ve \(P_2\) de geçen rakamlar birbirleriyle aynıysa \(P_1 = P_2\) olmalıdır. 


**İspat:** Aksini varsayalım, \(P_1\) ve \(P_2\) de geçen rakamlar birbirleriyle aynı fakat bu iki sayı birbirinden farklı olsun. Bu iki sayının ilk \(k\) basamak içinde birbirinden farklı olduğu ilk basamağı alalım. Bu iki sayı ardışık olduğu için, \(P_1\) sayısında bu basamak \(j\) ise, \(P_2\) sayısında bu basamak \(j+1\) olmalıdır ve

k. basamaktan önce yer almalılardır. Dolayısıyla, bu basamaktan önceki sayılar aynı oldukları için, \(P_1\) sayısında \(j\) den sonraki rakamlarla yazılabilecek en büyük sayı, \(P_2\) sayısında ise \(j + 1\) den sonraki rakamlarla yazılabilecek en küçük sayı yazılmıştır. Dolayısıyla, \(P_2\) sayısında bu basamaktan sonraki en büyük rakam en sonda, \(P_1\) sayısında ise \(j\) nin hemen yanındadır. Dolayısıyla, bu en büyük rakam \(P_1\) sayısının ilk \(k\) basamağında yer alacak fakan \(P_2\) sayısının ilk \(k\) basamağında yer almayacaktır, bu da rakamların aynı olması şartıyla çelişir. Dolayısıyla \(P_1 = P_2\) olmalıdır. □ 


17 uzunluklu bir alt dizinin iki farklı yerde geçtiğini varsayalım. 17 ardışık rakamdan oluşan her alt dizi, içinde bir dengeli sayının tamamını içermek zorundadır, aksi halde iki dengeli sayıyı kısmen içererek en fazla \(8 + 8 = 16\) basamağa sahip olabilirdi. Bu alt dizinin geçtiği iki farklı yeri alalım ve bu iki basamak dizisinde bütün halinde yer alan dengeli sayıları inceleyelim. Bu sayılar \(K_1\) ve \(K_2\) olsun. İki farklı yerdeki diziye baktığımız için, \(K_1\) ve \(K_2\) aynı sayı olamazlar. Ayrıca, bu iki sayının paylaştığı ortak basamaklar olmalıdır, aksi halde ayrık olsalardı bu dizinin uzunluğu en az \(9 + 9 = 18\) olurdu. Bu iki sayının paylaştığı basamak dizisi \(u_2\) olsun. İki rakam dizisi \(a\) ve \(b\) nin birleşimiyle oluşan diziyi \(a|b\) ile gösterelim. Genelliği bozmadan, \(K_1 = u_1|u_2\) ve \(K_2 = u_2|u_3\) olsun. Böylece, \(u_1|u_2|u_3\) dizisi her iki yerde de geçer. Ayrıca, \(u_1\) ve \(u_3\) sayılarının her ikisi de \(u_2\) de olmayan tüm rakamlardan oluştuğu için, bu iki sayının içerdiği basamaklar ve uzunlukları birbirleriyle aynıdır. 


\(K_1\) sayısını içeren diziyi inceleyelim. \(K_1 = u_1|u_2\), ilk basamakları \(u_1\) olan bir dengeli sayıdır ve bundan hemen sonra gelen dengeli sayı da ilk basamakları \(u_3\) olan bir dengeli sayıdır. Dolayısıyla, iddiamız gereği \(u_1 = u_3\) olmalıdır. 


Şimdi de \(K_2\) sayısını içeren diziyi inceleyelim. \(K_2 = u_2|u_3\) şeklindedir ve bundan hemen önce gelen dengeli sayı \(u_1\) ile bitmektedir, bu sayı \(v|u_1\) olsun. Dolayısıyla, \(v|u_1\) ve \(u_2|u_3\) ardışık iki dengeli sayıdır. \(u_1 = u_3\) olduğu için \(v\) ve \(u_2\) sayısının basamakları birbirleriyle aynıdır, dolayısıyla iddiamız gereği \(v = u_2\) olmalıdır. Bu durumda, \(v|u_1 = u_2|u_3\) elde edilir fakat ardışık iki dengeli sayı birbirinin aynısı olamaz. Dolayısıyla 17 basamaklı herhangi bir alt dizi iki farklı yerde geçemez.