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

Başlangıçta tahta üzerinde her birinin 31 koordinatı olan 31 adet 


\[(1, 0, 0, \dots, 0), (0, 1, 0, \dots, 0), \dots, (0, 0, 0, \dots, 1)\]


31-lileri yazılmıştır. Her işlemde, tahtada bulunan \((a_1, a_2, \dots, a_{31})\) ve \((b_1, b_2, \dots, b_{31})\) 31-lileri seçiliyor ve \((a_1 + b_1, a_2 + b_2, \dots, a_{31} + b_{31})\) 31-lisi de tahtaya yazılıyor. En az kaç işlem sonucunda tahtada 


\[(0, 1, 1, \dots, 1), (1, 0, 1, \dots, 1), \dots, (1, 1, 1, \dots, 0)\]


31-lilerinin tümü yer alabilir?

Şıklar:

Cevap:  \(3 \cdot 31 - 6 = 87\)

Çözüm:
. Cevap: \(3 \cdot 31 - 6 = 87\). 


\(n \ge 3\) olmak üzere, başlangıçta tahta üzerinde her birinin \(n\) koordinatı olan \(n\) adet 


\[(1, 0, 0, \dots, 0), \quad (0, 1, 0, \dots, 0), \quad \dots, \quad (0, 0, 0, \dots, 1)\]


n-lisi yazıldığı durumda cevabın \(3n - 6\) olduğunu göstereceğiz. 


İlk önce \(3n - 6\) işlemin yeterli olduğunu iki farklı şekilde gösterelim. \(i\). koordinatı 1 ve kalan koordinatları 0 olan \(n\) boyutlu vektör \(v_i^n\), \(i\). koordinatı 0 ve kalan koordinatları 1 olan \(n\) boyutlu vektör ise \(u_i^n\) olsun.

Yöntem 1. *n* üzerinden tümevarım. *n* = 3 durumunda *v₁*³ + *v₂*³, *v₁*³ + *v₃*³ işlemleri sonucunda gereken *u₁*³, *u₂*³ ve *u₃*³ vektörleri elde ediliyor. *n* = *k* durumunda 3*k* - 6 işlemin yeterli olduğunu varsayalım. *n* = *k* + 1 olsun. İlk işlemde *vₖ*⁺¹ ve *vₖ*⁺¹ vektörlerini toplayarak *vₖ*⁺¹ + *vₖ*⁺¹ ≡ *wₖ*⁺¹ + vektörünü elde edelim. Tümevarım varsayımına göre, *v₁*⁺¹, *v₂*⁺¹, ..., *vₖ*⁺¹ ve *vₖ*⁺¹ vektölerinden 3*k* - 6 işlem sonucunda *u₁*⁺¹, *u₂*⁺¹, ..., *uₖ*⁺¹ ve *uₖ*⁺¹ vektörleri elde ediliyor. *v₁*⁺¹ yerine *vₖ*⁺¹ +, *v₂*⁺¹ yerine *vₖ*⁺¹ ve *vₖ*⁺¹ alıp aynı 3*k* - 6 işlemi uygularsak *v₁*⁺¹, *v₂*⁺¹ +, ..., *vₖ*⁺¹ ve *vₖ*⁺¹ + vektörlerinden *u₁*⁺¹, *u₂*⁺¹ +, ..., *uₖ*⁺¹ ve son iki koordinatı 0 olup kalan koordinatları 1 olan *wₖ*⁺¹ + vektörü elde ediliyor. Son olarak *vₖ*⁺¹ + *vₖ*⁺¹ + *vₖ*⁺¹ ve *vₖ*⁺¹ + *vₖ*⁺¹ işlemlerini uygularsak *uₖ*⁺¹ ve *uₖ*⁺¹ vektölerini elde edilir. Sonuç olarak 1 + (3*k* - 6) + 2 = 3(k + 1) - 6 işlem sonucunda gereken *u₁*⁺¹, *u₂*⁺¹, ..., *u₁*⁺¹ ve *uₖ*⁺¹ vektörleri elde e dildi. 


Yöntem 2. Önce \(A_1, \dots, A_{n-2}\), sonra \(B_1, \dots, B_{n-2}\) ve son olarak \(C_1, \dots, C_{n-2}\) işlemlerini uygulayacağız: 


\[A_1 : v_1^n + v_2^n \equiv s(1, 2).\]


\[A_2 : u(1, 2) + v_3^n \equiv s(1, 2, 3).\]


\[A_{n-3} : u(1, 2, \dots, n-3) + v_{n-2}^n \equiv s(1, 2, \dots, n-2).\]


\[A_{n-2} : u(1, 2, \dots, n-2) + v_{n-1}^n \equiv s(1, 2, \dots, n-1) = u_n^n.\]


\[B_1 : v_n + v_{n-1}^n \equiv t(n-1, n).\]


\[B_2 : t(n-1, n) + v_{n-2}^n \equiv t(n-2, n-1, n).\]


\[B_{n-3} : t(4, \dots, n-1, n) + v_3^n \equiv t(3, 4, \dots, n).\]


\[B_{n-2} : t(3, \dots, n-1, n) + v_2^n \equiv t(2, 3, \dots, n) = u_1^n.\]


\[C_1 : v_1^n + t(3, \dots, n-1, n) = u_2^n.\]


\[C_2 : s(1, 2) + t(4, \dots, n-1, n) = u_3^n.\]


\[C_{n-2} : s(1, 2, \dots, n-2) + v_n^n = u_{n-1}^n.\]


Bu \((n-2) + (n-2) + (n-2) = 3n - 6\) işlem sonucunda \(u_1^n, u_2^n, \dots, u_n^n\) vektörlerinin hepsi elde edildi.

Şimdi ise en az \(3n - 6\) işlemin gerekli olduğunu gösterelim. \(n \ge 3\) olmak üzere, \(n\) boyutlu vektörler için gereken en az işlem sayısı \(f(n)\) olsun. Tümevarımla \(f(n) \ge 3n - 6\) olduğunu gösterelim. 


\(n = 3\) durumunda \(f(3) \ge 3\) olduğu açıktır. 


Tümevarım varsayımı \(n = k\) için doğru olsun: \(f(k) \ge 3k - 6\). \(n = k\) için yapılan işlemleri inceleyelim. \(v_{k+1}^{k+1}\) vektörünün ilk kez kullanıldığı işlem \(A\) olsun: \(A\) işleminde \(v_{k+1}^{k+1}\) ve en az bir \(m \ne k + 1\) için \(m\). koordinatı 0 olmayan bir \(r(m)\) vektörü toplanmıştır. Sadece \(m\). koordinatı 0 olan vektörü elde etmek için \(v_{k+1}^{k+1}\) en az bir kez daha kullanılacaktır, bu işlem de \(B\) olsun. Bir \(C\) işleminde de sadece \(k + 1\). koordinatı 0 olan vektör elde edilecektir. \(A, B, C\) işlemlerini yapmayıp, kalan işlemlerde de sonuncu koordinatı silersek \(n = k\) için gereken vektörleri elde ederiz. Demek ki \(f(k + 1) - 3 \ge f(k) \ge 3k - 6\) ve buradan da \(f(k + 1) \ge 3(k + 1) - 6\).