Binom eng dvi

Binom koeffitsientlarining ajoyib xossalari - 4

Oldingi mavzularga qo'shimcha muammolar

9. 
   m manfiy bo'lmagan butun son, p 5 tub son bo'lsin. Buni isbotlang
   

¹ + ¹ + · · · + ¹ ≡ 0 (mod p2).

mp + 1

mp + 2

mp + (p − 1)

9. 
   p va q tub sonlar bo‘lsin. Buni isbotlang^2pq−1 ≡ 1 (mod pq) agar va faqat agar ^2p−1 ≡ 1 (mod q) va
   

2q−1

q−1

≡ 1 (mod p).

pq−1

p−1

3. Binom koeffitsientlarining yig'indisi

1. 
   a) yig'indi ekanligini isbotlang
   

3 ^a−1


2k
k
ga bo'linadi 3;b) 3a ga bo'linadi.

2. 
   
   

1 2k

k=0

n

C bo'lsin_k = _{k+1 k}

katalon raqamlari bo'lsin. Buni isbotlang

k=1

Ck ≡ 1 (mod 3) agar va faqat n + 1 raqami bo'lsa

o'z ichiga oladis at least yoqilgane digit “2” 3-bazada.

3. 
   p 3, k = [2p/3] bo'lsin. summa ekanligini isbotlang^p + ^p + . . . +^p p2 ga bo'linadi.
   

_. 12 k

4. 
   Keling, n. (p - 1), bu erda p - toq tub son. Buni isbotlang
   

nn n

++

+ . . .≡ 1 + p(n + 1) (mod p2).

p − 1 2(s − 1)3( p − 1)

5. 
   
   −
   Prove that if 0 j p 1 < n ad q = n⁻¹] then
   

p−1

_{L n}


−
(1)m


q
m

≡ 0 (mod p ).

m:m≡j (mod p)

6. 
   p g'alati roim bo'lsin. Buni isbotlang
   

n . (p + 1)

agar va faqat agar

nnnn

j ⁻ j + (p − 1) ⁺ j + 2(s − 1) ⁻ j + 3(s − 1)

+ . . .≡ 0 (mod p)

hamma uchun j = 1, 3, . . . , p - 2.

Yechimlar

1 Poezdda yechish uchun muammolar

_{1.1. a) S yechim 1. p−1 =} (p − 1) (s − 2) . . . (p− k) _≡ (−1)(−2) . . . (−k) _{≡ (−1)k (mod p).}

^k 1 · 2 · · · k 1 · 2 · · · k

S eritmasi 2. Binomial koeffitsientlar formulasidan ko'rinib turibdiki, p qachon p ga bo'linadi

p−1

p−1

_p

p−1

p−1 ⁱ

p−1 _.

1. 
   i p − 1. beri
   

k−1 ⁺ k

= _k va

₀ = 1 ≡ 1 (mod p), keyin ( ₀

+ ₁ ). p, va shuning uchun

^p−1 ≡ −1 (mod p). Lekin^p−1 + ^p−1 p ga ham bo'linadi, shuning uchun ^p−1 ≡ 1 (mod p) va boshqalar.

112

2

2n+2

_2n
p−1

/
p−1

b) Thismasala [3, muammo 162] dan olingan. Kasrlardan beri

n+1 ^/ n

va

² 2

n+1 ⁿ

bor

juda kamaytirilishi mumkin, bayonot induksiya orqali osonlik bilan isbotlanishi mumkin. Lekin biz to'g'ridan-to'g'ri hisoblashni taklif qilamiz

[3] dan.

Ko'rish oson bu _2n

n

= 2n ·

1 · 3 · · · (2n − 1)

n!

va
1 · 3 · · · (2n − 1) = (−1)n(−1)(−3) · · · (−2n + 1) ≡ (−1)n(p − 1) (s − 3) · · · (p − 2n + 1) =

_nn⁽ p − 1 ⁾⁽ p − 3 <sup>)

(</sup> p − 2n + 1 ⁾

_nn⁽ p − 1 ⁾⁽ p − 1

) ( _{p − 1} )

= (−1) 2 <sub>2

2</sub> · · · ₂

= (−1) 2 ₂

₂ − 1 · · · ₂ − n + 1 =

₍ p−1 _)!

2n _n

p−1 _)!
n p−1

= (−1) n2n ²

(s⁻¹ − n)!
2

(mod p).

Shuning uchun

_n ≡ (−1) 4

² = (−4)


n!( p⁻¹ − n)!

_n (
2

2. 
   (mod p). n
   

2. 
   Bu to'g'ridan-to'g'ri Paskal arifmetik uchburchagining o'ziga o'xshash tuzilishidan kelib chiqadi, bu yo'qxt muammos. Bu ergashadi dan Lukas' nazariyam alshunday, you mumkin read the proof in [1].
   
3. 
   Biz o'zimizni kichik tafakkur bilan cheklaymiz, to'liq yechimni [3, muammo 133] da topish mumkin.
   

0
dan beri s-chi qator nollarning uzun ketma-ketligini o'z ichiga oladi, so'ngra (s + 1)-chi qatordagi bu nollarning ostida bizda ham nollar ketma-ketligi mavjud (u yuqori ketma-ketlikdan bitta element qisqaroq); (s + 2)-chi qatorda nollar ketma-ketligi ham mavjud (u yana bitta element qisqaroq) va hokazo. Bu ∆0 dan pastda kulrang uchburchak mavjudligini tushuntiradi (1-rasm).

Bundan tashqari, s-qatorning nolga teng bo'lmagan elementlari 1 ga teng, shuning uchun raqamlar qiyalik bo'ylab joylashgan.kulrang uchburchakning barcha tomonlari 1 ga teng (binomial koeffitsientlarning takrorlanishi tufayli). Shunday qilib, barcha

raqams yolg'izg the qiyalik tomonlar of the uchburchaks ∆0 ad ∆1 are 1's, va shuning uchun ikkala uchburchak ham bir xil

11

0
∆0 gacha.

Hozir it is aniq, nimat is the (2s)-th row of the uchburchak. The lefut- ad the o'ngmost elements are 1's, all boshqa elementlar 0 ga teng, 2 ga teng bo'lgan markaziy elementdan tashqari, chunki u ikkita yuqori elementning yig'indisidir.

1's. Payss we obtain that two grey uchburchaks are joylashgan below 2s-th qator, the uchburchaks ∆0 va ∆2 ga

22

left ad to the to'g'rit of them are identifikatorl to ∆0, ad the uchburchake ∆1 aqllih 2's yolg'izg bus qiyalik tomonlar is esifat

02

0
2 · ∆0 gacha.

Va hokazo.

2. 
   Biz [21] da topilgan ushbu bayonotda binomial koeffitsientlar haqidagi bir qancha faktlar Xanoy minorasi va THn grafigi orqali isbotlangan.
   

Birinchi novda ustidagi ustki diskning diametri a, ikkinchi novdadagi yuqori diskning diametri b va uchinchi novdadagi yuqori diskning diametri c bo'lsin. Wlog a < b < c, keyin bu konfiguratsiyada bizda 3 ta mumkin bo'lgan harakat bor: a dan b yoki c gacha va b dan c gacha, agar bitta novda disksiz bo'lsa, xuddi shunday 3 ta harakatga ega bo'lamiz. Agar barcha disklar bitta tayoqqa joylashtirilgan bo'lsa, bizda faqat 2 ta harakat qilish mumkin; A1, A2, A3 bu turdagi konfiguratsiyalarni bildirsin.

Obxizmat qilish that by the muammom 1.2 all the elements of 2s-th row of Patarozi t rian gle ar e 1 lar . Manaoldin tortishh

=
Pn uchinchi tartibli aylanish simmetriyasiga ega, chunki takrorlanish

n ₊ n

k−1 k

n+1

k

, bu imkon beradi

u s uchburchakni yuqoridan pastgacha qurish uchun 2 arifmetik modulda takrorlanishlarga tengdir

+

=
n ₌

k−1

nn +1

kk

va

nn ₊

kk −1

n+1

k

, bu bizga uchburchakni pastki chap tomondan qurishga imkon beradi

Ris. 3:
burchak yuqori o'ng yo'nalishda va pastki o'ng burchakdan yuqori chap yo'nalishda. Bundan tashqari, qo'sh o'lchamdagi uchburchakda dastlabki uchburchakning 3 nusxasi mavjud.

Endi induksiya orqali THn va Pn o‘rtasida shunday ikkilanish mavjudligini isbotlaymiz, Pn uchburchakning uchlari A1, A2, A3 konfiguratsiyalariga mos keladi. n = 1 asosi aniq.

Induksiya bosqichining isboti. THn va Pn o'rtasidagi o'zaro bog'lanish qurilgan deb faraz qilaylik. The 2-arifmetikal Patarozi uchburchake aqllih the tomoni uzunlikh 2ⁿ⁺¹ o'z ichiga oladis 3 nusxas of the uchburchake aqllih the yon uzunligi 2n. Nusxalarni raqamlang va uning uchlarini 3-rasmda ko'rsatilganidek belgilang. Xanoy minorasining barcha konfiguratsiyasini ko'rib chiqing, ular uchun (n + 1)-chi (eng katta) disk i rodga joylashtirilgan. Agar biz ushbu diskning joylashishini aniqlasak, boshqa disklarning siljishi TPn ga izomorf bo'lgan grafikga mos keladi. Induksiya gipotezasiga ko'ra, biz ushbu grafik va uchburchakning i-nusxasidagi Pn grafigi o'rtasida ikkilanishni tanlashimiz mumkin, shunda Aj konfiguratsiyalari bir xil belgilarga ega uchburchaklar cho'qqilariga mos keladi. Eng katta diskni, aytaylik, birinchi novdadan ikkinchisiga o'tkazganimizda, qolgan barcha disklar 3-tayoqda bo'lishi kerak. Bu harakat katta uchburchakning chap qiyalik tomonidagi ikkita qo'shni A3 cho'qqisini bog'laydigan chekkaga to'g'ri keladi. Xuddi shu sabablar eng katta diskning boshqa harakatlariga tegishli. Shuning uchun biz TPn+1 orasida izomorfizmga erishamiz ad Pn.

2. 
   
   2
   Xanoy minorasi bilan ikkilanish bizga formulani beradi (qatorlar soni 2 ga teng bo'lsa): birinchi 2^k qators of 2-arifmetikal Patarozi uchburchake o'z ichiga oladin 3^k 1's. The formula taxminann be alshunday isbotlashd by induksiyan orqali takrorlanishe dan the muammom 1.3. Foydalanish this formula we ca obtain an erag'batlantirish. Since 10⁶ < 220, the jami raqamr of elements in these qators esifatlar 1 · 106 (106 + 1) va 1 ning soni ko'pi bilan 320 ga teng.
   

10⁶(10⁶ +1)
mutanosib emas oshib ketish ^2·320

2. 
   Biz bu bayonotni [18] da topdik.
   

« 0,01.

k

k
1-chi variant ([CSTTVZ]). p = 2 uchun bayonotosongina tekshirilishi mumkin. Shunday qilib, p ni toq tub son deb taxmin qilishimiz mumkin. n = x(p − 1) + k bo‘lsin. X da induksiyadan foydalanamiz.

X = 0 asosi ahamiyatsiz:

j ^≡ j

(mod p).

Induksiya bosqichini isbotlash uchun binomial koeffitsientlarning quyidagi xossasi zarur:

a + b

_{L a}

=

b

(tabiiy chegaralarda yig'indi),

s _i s − ii
ning ikkala tomoni qaysi biz qora va o'z ichiga olgan qutidagi s sharlarni tanlash mumkin necha yo'llar bilan hisoblash

b oq sharlar. n = m + (p - 1) bo'lsin. Shuni kuzating

n ₌ m + (p−1) <sub>=

L</sub>p−1 _m

p − 1 <sub>≡

L</sub>p−1


m
(−1) i
(mod p)

f(p−1) + j

f(p−1) + j

i=0

f(p−1) + j − i i

i=0

f(p−1) + j − i

(oxirgi ekvivalentlik 1.1 a muammosiga bog'liq). E'tibor bering, birinchi va oxirgi atamalarning belgisi oxirgi

so'm is “plys”. Endi muammo bayonotidan yig'indini o'zgartiring:

_{L n}


−
f(p 1) + j ^≡

mm

mmm

≡ _j −

j − 1

+ . .. +

p − 1 + j

^— p − 1 + j − 1

+. . .++

j

mmm

+

2(s−1) + j

^— 2(s−1) + j − 1

_Lm

+. . .+

−
m

2(s−1) + j

_{L m}

+ . . .

=

i=0

(1)i +

i

f(p−1) + j

(mod p).

j
birinchi yig'indi 0 ga teng, ikkinchi yig'indi induksiya gipotezasi bo'yicha ekvivalent k (mod p).

S yechim 2 ([J], [T]). n tomonidan induksiya. n p - 1 asosi ahamiyatsiz: ikkala tomon ham bir xil atamani o'z ichiga oladi. Induksiya bosqichini isbotlang.

nn

+

j (p − 1) + j

+ . . . =

n − 1

j

₊ n − 1 ₊

j − 1

n − 1

(p − 1) + j

₊ n − 1

(p − 1) + j − 1

+ . . . =

₌ n − 1 ₊ n − 1

+ . .. +

n − 1 ₊

n − 1

+ . .. ≡

j (p − 1) + j

j − 1

(p − 1) + j − 1

≡
k − 1

j

₊ k − 1 ₌ k j − 1 j
(mod p).

Lekin u p - 1 j yoki k ni bo'lgan hollarda aniq bo'lishi kerak, chunki j = 0 yoki k = 0 uchun induksiya gipotezasi bajarilmaydi (u 0 o'rniga p - 1 qiymatidan foydalanadi). Shuning uchun j = 1 yoki k = 1 bo'lgan holatlarni diqqat bilan ko'rib chiqishimiz kerak. Biz faqat bitta qisman holatni ko'rib chiqish bilan cheklanamiz. p = 5, j = 1 bo'lsin va biz n = 13 ga qadamni bajaramiz. Keyin biz bor

1 ? 131313

1 ^≡ 1 ⁺ 6 ⁺ 11 ⁼

121212

+++ 1611

121212

++ .

0510

Induksiya gipotezasiga ko'ra, birinchi qavsdagi yig'indi 4 qoldiqga ega (oldingi kabi 0 emas, balki 4).

11

4


hisoblash ko'rsatadi). Bunda induksion gipoteza birinchisidan tashqari barcha atamalarni qamrab oladi

−

₁ +

−



≡

1

+
biri, shuning uchun so'm qoldiqga ega

12 ₊

. Aniqlik uchun 4 o'rniga p - 1 ni yozsak, biz butun yig'indini olamiz

ekvivalentdir uchun

_{n 1} 0

p−1 0

_p ⁰ ₁

01

(mod p), kerak bo'lganda.

S o l u t i o n3 (Luka teoremasi bilan algebraik fikrlash, [18]). n tomonidan induksiya. n p - 1 asosi ahamiyatsiz. Endi np bo'lsin, barcha parametrlarni p asosga yozing, sp(m) m raqamlari yig'indisini bildirsin. Ko'rinib turibdiki, agar m ≡ j (mod p) bo'lsa, u holda sp(m) ≡ j (mod p). Ko'rib chiqilayotgan yig'indi Luka teoremasi bo'yicha tengdir

0

1
^uchun _{L n} n

nd

. . .
(mod p),

m₀ m₁ md


≡
bu erda yig'indi barcha m = md ustidan bo'ladi. . . m1m0 n, buning uchun sp(m) j (mod p). Bu miqdor ga teng the so'm of koesamarali of xj, xj^+p−1, xj^+2(p−1), . . . in the eifodalash

(1 + x)n⁰ (1 + x)n¹ . . .(1 + x)n^d = (1 + x)s^p(n) .

Ammo ko'rinib turibdiki, bu koeffitsientlar yig'indisi tengdir

L
^{1 r s}p⁽ⁿ⁾

r≡j (mod p−1)

sp(n) , r

1 σp(n) n − 1 bo‘lgani uchun induksiya gipotezasini qanoatlantiradi va shu vaqtdan boshlab kerakli ekvivalentlikni beradi.

sp(n) ≡ n ≡ j (mod p).

S yechim 4 (chiziqli algebra, [D]). x, x2, polinomlari. . . , xp−1 Zp va ustidan chiziqli mustaqil shakl a baopa-singil in the bo'sh joy of funktsiyalarif : Zp → Zp, f (0) = 0. Fermaning kichik teoremasi (1 + x)n ≡ (1 + x)k (mod p). xi+a(p−1) ≡ xi munosabatlarini e chap tomoniga qo‘llasak, yig‘indimiz quyidagicha bo‘ladi.

j

.
Zp ning elementi o'ng tomondagi xj koeffitsientiga teng, ya'ni k

2.