Gönderen Konu: Son üç basamağı aynı olan sayılar  (Okunma sayısı 185 defa)

Çevrimdışı metonster

  • G.O Genel Moderator
  • G.O Efsane Üye
  • ********
  • İleti: 491
  • Karma: +7/-0
Son üç basamağı aynı olan sayılar
« : Haziran 21, 2021, 05:30:28 öö »
$n=20,21,2020,2021,2047,2048$ sayılarından hangileri için $\dbinom{10n}{5n}$ ve $\dbinom{2n}{n}$ sayılarının birler bölüğü aynıdır? (Birler bölüğü, sayının son üç basamağı demektir, yani $12548$ sayısının birler bölüğü $548$'dir.) (Metin Can Aydemir)

Sorunun bu halinin zor kalacağını düşündüğümden ipucu vermek istiyorum. Bu teoremini kullanırsanız işlemleriniz çok daha azalacaktır;

Her $p\geq 5$ asalı ve $a>b$ pozitif tamsayıları için $\dbinom{ap}{bp}\equiv \dbinom{a}{b}\pmod{p^3}$ denkliği sağlar.
Gerçek hikayeler aslında söylenmeyenlerdir.

Çevrimdışı metonster

  • G.O Genel Moderator
  • G.O Efsane Üye
  • ********
  • İleti: 491
  • Karma: +7/-0
Ynt: Son üç basamağı aynı olan sayılar
« Yanıtla #1 : Haziran 23, 2021, 01:41:14 öö »
Soruda aslında $\dbinom{10n}{5n}\equiv \dbinom{2n}{n}\pmod{1000}$ sağlaması isteniliyor. Verilen teoremden $a=2n$, $b=n$ için $\dbinom{10n}{5n}\equiv \dbinom{2n}{n}\pmod{125}$ olacaktır. Dolayısıyla $\dbinom{10n}{5n}\equiv \dbinom{2n}{n}\pmod{8}$ sağlaması yeterlidir. $v_2(n)$, $n$'yi bölen en büyük $2$'nin kuvvetini göstersin (Yani $m$ tek sayısı için $v_2 \left (2^am\right )=a$ olacaktır).

İddia: $n$ pozitif tamsayısı için $v_2\left (\dbinom{2n}{n}\right )=n-v_2(n!)$'dir.

İspat: $\dbinom{2n}{n}=\dfrac{(2n)!}{(n!)^2}$ olduğundan  $v_2\left (\dbinom{2n}{n}\right )=v_2((2n)!)-2v_2(n!)$ olacaktır. $v_2(n!)=\sum_{i=1}^{\infty}\left \lfloor\dfrac{n}{2^i}\right \rfloor$ olduğundan $$v_2((2n)!)=\sum_{i=1}^{\infty}\left \lfloor\dfrac{2n}{2^i}\right \rfloor=\sum_{i=1}^{\infty}\left \lfloor\dfrac{n}{2^{i-1}}\right \rfloor=\left \lfloor\dfrac{n}{2^{0}}\right \rfloor+\sum_{i=1}^{\infty}\left \lfloor\dfrac{n}{2^i}\right \rfloor =n+v_2(n!)$$ olacaktır. Yerine yazarsak $v_2\left (\dbinom{2n}{n}\right )=n-v_2(n!)$ olacaktır.

İddia 2: $a_1>a_2>\cdots>a_k$ için $n=2^{a_1}+2^{a_2}+\cdots +2^{a_k}$ ise $v_2\left (\dbinom{2n}{n}\right )=k$ olacaktır.

İspat: $n=2^{a_1}+2^{a_2}+\cdots +2^{a_k}$ için $v_2(n!)=\sum_{i=1}^{\infty}\left \lfloor\dfrac{n}{2^i}\right \rfloor$ olduğundan $a_{j}\geq i>a_{j+1}$ için $$\left \lfloor\dfrac{n}{2^i}\right \rfloor=\left \lfloor\dfrac{2^{a_1}+\cdots+2^{a_j}+2^{a_{j+1}}+\cdots+2^{a_k}}{2^i}\right \rfloor=\left \lfloor 2^{a_1-i}+\cdots+2^{a_j-i}+\dfrac{2^{a_{j+1}}+\cdots+2^{a_k}}{2^i}\right \rfloor$$ $i>a_{j+1}$ olduğundan $2^{a_{j+1}}+\cdots+2^{a_k}\leq 2^{i-1}+2^{i-2}+\cdots +1=2^{i}-1$ olduğundan $\dfrac{2^{a_{j+1}}+\cdots+2^{a_k}}{2^i}\leq \dfrac{2^{i}-1}{2^i}<1$ olduğundan $$\left \lfloor\dfrac{n}{2^i}\right \rfloor=2^{a_1-i}+\cdots+2^{a_j-i}$$ olacaktır. $$\sum_{i=1}^{\infty}\left \lfloor\dfrac{n}{2^i}\right \rfloor=\sum_{j=1}^{k}\sum_{i=a_{j+1}+1}^{a_{j}}\left (2^{a_1-i}+\cdots+2^{a_j-i}\right )=\sum_{j=1}^{k}\sum_{i=0}^{a_j-1} 2^i=\sum_{j=1}^{k}\left (2^{a_j}-1\right )=n-k$$ elde edilir. Dolayısıyla, $v_2\left (\dbinom{2n}{n}\right )=n-v_2(n!)=n-(n-k)=k$ elde edilir.

Soruya dönersek, $\dbinom{10n}{5n}\equiv \dbinom{2n}{n}\pmod{8}$ olması için $v_2\left (\dbinom{2n}{n}\right )\geq 3$ ve $v_2\left (\dbinom{10n}{5n}\right )\geq 3$ veya $v_2\left (\dbinom{2n}{n}\right )=v_2\left (\dbinom{10n}{5n}\right )$ olmalıdır. Kısaca $\dbinom{2n}{n}=C_n$ olarak gösterirsek,

$n=20$ için $20=(10100)_2$ olduğundan $v_2(C_{20})=2$ olacaktır. $100=(1100100)_2$ olduğundan $v_2(C_{100})=3$ olduğundan $n=20$ sağlamaz.

$n=21$ için $21=(10101)_2$ olduğundan $v_2(C_{21})=3$ olacaktır. $105=(1101001)_2$ olduğundan $v_2(C_{105})=4$ olduğundan $n=21$ sağlar.

$n=2020$ için $2020=(11111100100)_2$ olduğundan $v_2(C_{2020})=7$ olacaktır. $10100=(10011101110100)_2$ olduğundan $v_2(C_{10100})=8$ olduğundan $n=2020$ sağlar.

$n=2021$ için $2021=(11111100101)_2$ olduğundan $v_2(C_{2021})=8$ olacaktır. $10105=(10011101111001)_2$ olduğundan $v_2(C_{10105})=9$ olduğundan $n=2021$ sağlar.

$n=2047$ için $2047=(11111111111)_2$ olduğundan $v_2(C_{2047})=11$ olacaktır. $10235=(10011111111011)_2$ olduğundan $v_2(C_{10235})=11$ olduğundan $n=2047$ sağlar.

$n=2048$ için $2048=(100000000000)_2$ olduğundan $v_2(C_{2048})=1$ olacaktır. $10240=(10100000000000)_2$ olduğundan $v_2(C_{10240})=2$ olduğundan $n=2048$ sağlamaz.

Dolayısıyla sadece $n=21,2020,2021,2047$ istenileni sağlar.
Gerçek hikayeler aslında söylenmeyenlerdir.

 


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 32 33 34 
SimplePortal 2.3.3 © 2008-2010, SimplePortal