Gönderen Konu: Tübitak Lise Takım Seçme 2001 Soru 3  (Okunma sayısı 1869 defa)

Çevrimdışı scarface

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 2943
  • Karma: +21/-0
  • İstanbul
Tübitak Lise Takım Seçme 2001 Soru 3
« : Ağustos 08, 2013, 10:05:07 ös »
Tüm $x,y, z$ tam sayıları için, $$S(x,y,z) = (xy - xz, yz-yx, zx - zy)$$ olsun. $a$, $b$ ve $c$, $abc>1$ koşulunu sağlayan tam sayılar olmak üzere, $0<k\leq abc$ ve her $n\geq n_0$ tam sayısı için $$S^{n+k}(a,b,c) \equiv S^n(a,b,c) \pmod {abc}$$ koşullarını sağlayan $n_0$ ve $k$ tam sayılarının bulunduğunu gösteriniz.

($S^1 = S$ ve her $m\geq 1$ tam sayısı için, $S^{m+1} = S \circ S^m$)

($(u_1, u_2, u_3) \equiv (v_1, v_2, v_3) \pmod M \Longleftrightarrow u_i \equiv v_i \pmod M (i=1,2,3).$)
« Son Düzenleme: Haziran 22, 2014, 09:51:37 öö Gönderen: geo »
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1713
  • Karma: +8/-0
Ynt: Tübitak Lise Takım Seçme 2001 Soru 3
« Yanıtla #1 : Eylül 11, 2013, 12:24:28 öö »
Soruda sorulan aslında, belirli bir $i = n_0$ değerinden sonra $S^i$ dizisinin periyodik olduğu ve bu $k$ periyodunun $abc$ den çok olmadığı.

$S^{n_0} = (0,0,0) \pmod {abc}$ olursa, her $k\geq 1$ için $S^{n_0+k} = (0,0,0)$ olacağı için $n_0$ ve $k$ sayıları bulunuyor.
Hiçbir $n_0$ değeri için $S^{n_0} = (0,0,0)$ olmadığını varsayalım.
Bu durumda, $S$ nin alabileceği $(abc)^3 - 1$ farklı değer vardır.
$S, S^2, \dots, S^{(abc)^3}$ dizisinden $S^i  \equiv S^j$ olacak şekilde iki eleman bulunabilir. $|i-j| \leq a^3b^3c^3$ dir. $S^i \equiv S^j$ ise her $k\geq 0$ için $S^{i+k} \equiv S^{j+k}$ dir. Bu durumda $S$ nin periyodu için $0<k\leq a^3b^3c^3$ eşitsizliği sağlanır.

Aslında eşitsizliği daha da daraltabiliriz.
$S^1 = (ab-ac, bc-ba, ca-cb)$ olduğunu biliyoruz. $S^0 = (a,b,c)$ olarak tanımlayalım.
$S^0 = (a,b,c)$ ise her $S^i$ üçlüsünün ilki $a$'nın bir katıdır; çünkü $S^1 = (ab-ac, bc-ba, ca-cb)$ (İlk parametre $a$ ile bölündüğü için bundan sonra $S^i$ nin de ilk parametresi yine $a$ ile bölünecek).
Aynı şey ikinci ve üçüncü parametreler için de geçerli.
$\bmod {abc}$ de, ilk parametreyi seçmek için $bc$ seçenek var. Bu durumda değer kümemiz en fazla $bc\cdot ac \cdot ab = a^2b^2c^2$ elemanlı olacaktır.

Aslında daha iyisini yapabiliriz.
$S$ üçlüsünün parametreleri toplamı $ab-ac+bc-ba+ca-cb=0$ olduğu için, $S$ nin ilk iki parametresini seçtiğimizde üçüncü parametre otomatik olarak $ -a-b \mod {abc}$ ye denk olacaktır.
Öyleyse, değer kümesi en fazla $bc\cdot ac = abc\cdot c$ elemanlı olacaktır. Aslında, bu değer $abc\cdot \min(a,b,c)$. Bu çirkin $\min$ den kurtulabilir miyiz?

Daha iyisi de var.
İlk parametre $a$ nın bir katı,  ikincisi $b$ nin bir katı, üçüncüsü de $c$ nin bir katı ve toplamları $0$; ama az önce biz daha fazlasını saydık. Her $(a,b)$ çifti için, $c$ değerini $a+b+c \equiv 0 \pmod {abc}$ denkliği ile bulduk; ama üçüncü parametre her zaman $c$ nin bir katı olmadı.

İddia:
$\text{obeb} (a,b,c)=1$, $0\leq x < rbc$ ve $0\leq  y < rac $ olmak üzere; $ax+by \equiv 0 \pmod c$ denkliğinin $r^2abc$ tane çözümü vardır.

İspat:
$\text{obeb} (b,c)=d$ olsun. Tanım gereği, $\text{obeb} (a,d)=1$.
$x=0$ olsun.
$by \equiv 0 \pmod c \Rightarrow d\cdot \frac bd \cdot y \equiv 0 \pmod c$.
$\Rightarrow \frac bd \cdot y \equiv 0 \pmod {\frac cd} \Rightarrow y \equiv 0 \pmod {\frac cd}$.

Öyleyse, $x=0$ için $y$ lerin sayısı $\frac {rac}{\frac cd} = rad$ dir.

$ax+by \equiv 0 \pmod d$ ve $b \equiv  0  \pmod d$ olduğu için, $ax \equiv 0 \pmod d$ dir. Ayrıca $\text{obeb}(a,d)=1$, $x\equiv 0 \pmod d$.
$x$ lerin sayısı da $\frac{rbc}{d}$.

Bu durumda $(x,y)$ sıralı tam sayı ikililerinin sayısı, $\frac{rbc}{d}\cdot rad = r^2abc$ olacaktır. $\blacksquare$

Soruya geri dönelim. $\text{obeb} (a,b,c)=r$ ve $a = r\alpha$, $b = r\beta$, $c = r\theta$. Yani $\text{obeb}(\alpha, \beta, \theta) = 1$ olsun.
$S^0 = (a,b,c) \Rightarrow S^1 = (r\alpha r\beta - r\alpha r\theta, r\beta r\theta - r\beta r\alpha, r\theta r\alpha - r\theta r \beta)$.
$abc = r^3\alpha\beta \theta$ ve ilk parametre her zaman $r^2 \alpha$ nin bir katı olacağı için, ilk parametreyi seçmenin $\frac {r^3\alpha \beta \theta}{r^2\alpha} = r\beta \theta$ yolu vardır.
Yukarıdaki iddiayı kullanırsak,
$\text{obeb}(\alpha, \beta, \theta) = 1$, $0\leq x < r\beta\theta$, ve $0\leq y < r\alpha\theta$ olacaktır. Bu durumda $r^2\alpha \beta \theta$ adet çözümümüz vardır. $r^2 \alpha \beta \theta \leq r^3 \alpha \beta \theta = abc$.

Sonuç olarak, $S^i$ dizisi, en fazla $abc$ farklı değer alabilir. $\blacksquare$
« Son Düzenleme: Haziran 22, 2014, 09:51:48 öö Gönderen: geo »

 


Sitemap 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 
SimplePortal 2.3.3 © 2008-2010, SimplePortal