เฉลยโจทย์ประจำสัปดาห์ ครั้งที่ 3

นี่คือเฉลยของโจทย์ประจำสัปดาห์ ครั้งที่ 2 เราได้ให้ข้อคิดเห็นสำหรับโจทย์แต่ละข้อ รวมทั้งระดับความยาก $\beta$ in $[1,5]$ โดยโจทย์ค่ายสอวน. จะมี $\beta$ ประมาณ 1-2, โจทย์ TMO ปกติ จะมี $\beta$ ประมาณ 1-3, โจทย์ค่ายตุลาคม จะมี $\beta$ ประมาณ 2-4 และโจทย์ IMO จะมี $\beta$ ประมาณ 3-5

E3 [ดัดแปลงจาก IMO 2006 P4] ( $\beta =1.5$ )

จงแสดงว่าถ้า $p>3$ เป็นจำนวนเฉพาะ แล้ว $2^{p-2}+3^{p-2}+6^{p-2}-1$ หารด้วย $p$ ลงตัว

เฉลย จาก $p>3$ จะได้ $\gcd (p,2)=\gcd (p,3)=1$ จากทฤษฎีบทเล็กของแฟร์มาต์ จะได้ว่า $a^{p-1} \equiv 1\pmod{p}$ ดังนั้น $a^{p-2}\equiv \frac{1}{a} \pmod{p}$ สำหรับ $a=2,3,6$ เพราะฉะนั้น

$2^{p-2}+3^{p-2}+6^{p-2}\equiv \frac{1}{2}+\frac{1}{3}+\frac{1}{6}=1\pmod{p}\quad \blacksquare$

ข้อคิดเห็น โจทย์ข้อนี้เป็นตัวอย่างของการใช้เศษส่วนในมอดุโลจำนวนเฉพาะ $p$ ซึ่งเป็นเทคนิคที่มีประโยชน์แต่มักถูกมองข้าม

M3 [Bulgaria TST 2005] ( $\beta = 3.4$ )

จงหาจำนวนสับเซต $B$ ของเซต $\{ 1,2,...,2005\}$ ที่ผลรวมสมาชิกของ $B$ หารด้วย $2048$ แล้วเหลือเศษ $2006$

เฉลย คำตอบคือ $2^{1994}$ ซึ่งแสดงได้ดังนี้

ให้ $S = \{1,2,\ldots, 2005\} \setminus \{2^0,2^1,\ldots ,2^{10}\}$ และสังเกตว่าสำหรับสับเซต $B'$ ใดๆ ของ $S$ จะมีเซต $B$ เพียงเซตเดียว ที่ $B$ เกิดจาก $B'$ รวมกับสับเซตของ $\{ 2^0,2^1,\ldots ,2^{10} \}$ และผลรวมสมาชิกของ $B$ หารด้วย $2048$ แล้วเหลือเศษ $2006$ (ข้อสังเกตนี้เป็นจริงเพราะสำหรับแต่ละจำนวนเต็ม $a=0,1,2,...,2047$ จะมีสับเซตของ $\{2^0,2^1,\ldots ,2^{10}\}$ สับเซตเดียวพอดีที่มีผลรวมสมาชิกเป็น $a$ ) จากข้อสังเกตจะได้ว่า จำนวนสับเซต $B$ ที่เราต้องการนับ เท่ากับจำนวนสับเซตของ $S$ ซึ่งคือ $2^{2005-11}. \quad \blacksquare$

ข้อคิดเห็น ข้อสังเกตที่สำคัญในการทำโจทย์ข้อนี้คือ เราสามารถควบคุมเศษที่เหลือจากการหารด้วย $2048$ โดยใช้เพียงแค่กำลังของสอง ซึ่งเมื่อได้ข้อสังเกตแล้ว ก็จะทำให้โจทย์ที่ดูซับซ้อนกลายเป็นตรงไปตรงมาในทันที

H3 [reddit] ( $\beta = 54.3$ )

ในแต่ละตา จากคู่อันดับของจำนวนเต็มบวก $(a,b)$ คุณสามารถเดินไปยัง $(a+1,2b)$ หรือ $(2a,b+1)$ จงแสดงว่าถ้าคุณเริ่มจากคู่อันดับ $(m,n)$ ใดๆของจำนวนเต็มบวก คุณจะสามารถเดินไปยังคู่ของจำนวนเต็มบวกที่เท่ากันได้

เฉลย [@Lopsidation ที่ reddit] เราจะเรียกการเดิน $(a,b)\rightarrow (a+1,2b)$ ว่าเป็นแบบ $1$ และเรียกการเดิน $(a,b)\rightarrow (2a,b+1)$ ว่าเป็นแบบ $2$ ต่อมา เราจะเรียกคู่อันดับของจำนวนเต็มบวก $(x,2^dx+k)$ ว่าเป็นประเภท $(d,k)$ สำหรับจำนวนเต็มไม่ติดลบ $d$ และจำนวนเต็ม $k$

เป็นการเพียงพอที่จะแสดงว่าสำหรับจำนวนเต็มบวก $k$ ใดๆ ถ้าเราเริ่มจากคู่อันดับที่มีประเภท $(0,k)$ โดย $k$ เป็นจำนวนเต็มบวกแล้ว เราจะสามารถเดินไปยังคู่อันดับที่มีประเภท $(0,m)$ สำหรับบาง $-k< m<k$ ได้ (*)

(หมายเหตุ: เพราะรูปแบบที่เราเดินได้ สมมาตรบนตัวแปร $a,b$ ถ้าเราต้องเริ่มจาก $(x,y)$ เราจึงสามารถบอกว่าเราจะเริ่มจาก $(y,x)$ แทน และสลับแบบการเดินของเรา (จากแบบ $1\to 2, 2\to 1$ ) ซึ่งทำให้เราสามารถเปลี่ยนคู่อันดับประเภท $(0,-k)$ เป็นประเภท $(0,k)$ ได้)

สังเกตว่าการเดินแบบ $1$ จะเปลี่ยนคู่อันดับประเภท $(d,k)$ เป็นประเภท $(d-1,k+1)$ และการเดินแบบ $2$ จะเปลี่ยนคู่อันดับประเภท $(d,k)$ เป็น $(d+1,2k-2^{d+1})$

ดังนั้นถ้า $\ell$ เป็นจำนวนเต็มบวกใดก็ได้ที่ไม่เกิน $k$ เราจะสามารถเดินและเปลี่ยนประเภทของคู่อันดับได้ดังนี้:

$(0,k)\rightarrow_2 (1,2^1k-1\times 2^1)\rightarrow_2 (2,2^2k-2\times 2^2)\rightarrow_2 \ldots \rightarrow_2 (k,2^{k}k-k\times 2^{k})=\\(k,0)\rightarrow_{1} (k-1,1) \rightarrow_1 (k-2,2)\rightarrow_1 \ldots \rightarrow_1 (\ell -1,k-\ell +1) \rightarrow_2 \\ (\ell ,2k-2^{\ell} -2\ell+2) \rightarrow_1 (\ell -1,2k-2^{\ell}-2\ell +3)\rightarrow_1 \ldots \rightarrow_1 (0,2k-2^{\ell}-\ell +2).$

สังเกตว่าถ้ามี $\ell$ ที่สอดคล้อง $-k<2k-2^{\ell}-\ell +2<k$ ก็จะได้ว่าเราสามารถทำ (*) ได้ทันที ซึ่งเงื่อนไขนี้สมมูลกับ $k<2^{\ell} +\ell -2<3k$ .

สำหรับจำนวนเต็มบวก $\ell$ ใดๆ ให้ $f(\ell )=2^{\ell} +\ell -2$ เราจะได้ว่า $f(k)>k$ สำหรับทุก $k\geq 2$ และ $\frac{f(i+1)}{f(i)} \leqslant 3$ สำหรับทุก $i\geq 2$ ดังนี้นถ้า $3k\geqslant f(2)=4$ เราจะสามารถเลือกค่า $\ell$ ที่เราต้องการได้

ดังนั้นจะเหลือเพียงกรณีเดียวคือ $k=1$ ซึ่งเราสามารถสมมติให้คู่อันดับของเราเป็น $(x,x+1)$ สำหรับบางจำนวนเต็มบวก $x$ และในกรณีนี้ เราสามารถเดินดังนี้ได้

$(x,x+1)\rightarrow_1 (x+1,2x+2)\rightarrow_1 (x+2,2x+4)\rightarrow_2 (2x+4,4x+5)\rightarrow_2 (4x+8,4x+6)\rightarrow_2 (8x+16,4x+7)\rightarrow_2 (16x+32,4x+8)\rightarrow_1 (16x+33,8x+16)\rightarrow_2 (32x+66,8x+17)\rightarrow_1 (32x+67,16x+34)\rightarrow_1 (32x+68,32x+68),$

เพราะฉะนั้นเราจึงสามารถทำ (*) ได้เสมอ $\blacksquare$

ข้อคิดเห็น โจทย์ข้อนี้มาจากกระทู้หนึ่งบนเว็บไซต์ reddit ตามลิงก์นี้: Doubling and adding 1. เราเลือกโจทย์ข้อนี้มาเพราะเป็นโจทย์ที่เข้าใจได้ง่ายมาก แต่วิธีทำค่อนข้างยาก และโจทย์ข้อนี้มาจากแหล่งโจทย์ที่ไม่ได้พบได้ทั่วไป กล่าวคือมาจากเว็บไซต์แสดงความคิดเห็นธรรมดาๆ เว็บหนึ่ง เราจึงอยากนำแหล่งโจทย์เหล่านี้มาเผยแพร่ และอยากแสดงให้ท่านผู้อ่านเห็นว่าโจทย์คณิตศาสตร์นั้นมีที่มาได้จากทุกที่

โครงการ InfinityDots

เฉลยโจทย์ประจำสัปดาห์ ครั้งที่ 3

Leave a comment Cancel reply

Share this:

Related

Leave a comment Cancel reply