FFTMO9

[จูกัดเหลียง]

ข้อความเดิมเขียนโดยคุณ PP_nine

ถ้าเริ่มเข้าใจ inverse modulo $p$ สำหรับจำนวนเฉพาะ $p$ แล้วล่ะก็ ขอขยับขึ้นมาให้ใกล้กับกรณีทั่วไปอีกหน่อยละกัน

10. สำหรับจำนวนนับ $k,a,b$ ซึ่ง $k \ge 2$ และ $(a,b)=1$ สอดคล้องกับ
$$1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{2^k-1}=\frac{a}{b}$$
พิสูจน์ $2^k|a$

จากโจทย์
$$a=b(1+\frac{1}{3}+\frac{1}{5}+...+\frac{1}{2^k-1})$$
เพราะว่า $(2^k-1,i)=1$ สำหรับ $i\in \left\{\,1,3,5,...2^k-1\right\} $
ทำให้ได้ว่า $$a\equiv (1+3+5+...+(2^k-1))b\equiv 2^k\cdot2^{k-1}b\equiv 0\pmod{2^k}$$
$\therefore 2^k|a$

[PP_nine]

#29 จะเขียนอย่างงั้นมันก็ได้แหละครับ แต่ถ้าเขียนแบบนี้แล้วเหมือนเจตนาว่ามันไม่ซ้ำ อาจโดนหักคะแนนได้ในข้อสอบจริงนะครับ

#30 ลืม $1^{-1} \equiv 1 \pmod{p}$ หรือเปล่าเอ่ย??? ต้องเป็นแค่ $2\cdot3\cdot...\cdot(p-2) \equiv 1 \pmod{p}$ ก่อนสิครับ

#31 ก็ควรพิสูจนเพิ่มเติมเล็กน้อยด้วยนะครับ เพราะคราวนี้ไม่ใช่จำนวนเฉพาะ (อาจเขียนว่า ทำนองเดียวกับจำนวนเฉพาะ เพิ่มหน่อยก็ดีครับ )

ปล.ที่ย้ำจุกจิกเพราะกรรมการ TMO เค้าก็จุกจิกอย่างนี้แหละ หาจุดหักคะแนน ผมเคยผ่านมาแล้ว

มาเฉลยข้อนี้ให้ละกัน

ข้อความเดิมเขียนโดยคุณ PP_nine

7.สำหรับจำนวนเฉพาะ $p$ ซึ่ง $p \equiv 3 \pmod{4}$ ถ้าเรา partition เซต $\left\{\,1,2,...,p-1 \right\}$ ออกเป็นสองเซตที่มีจำนวนสมาชิกเท่ากัน

โดยที่สมาชิกในแต่ละเซตมี inverse modulo $p$ อยู่ในเซตเดียวกันแล้ว เราจะสามารถ partition แบบนี้ได้กี่วิธี

(ข้อนี้ไม่ยากครับ แค่ทดสอบความรู้พื้นฐานของอินเวอร์ส)

ขั้นแรก จับคู่อินเวอร์สเป็นคู่ๆ ได้ $(1,1), (p-1,p-1), (a,a^{-1})$

ซึ่งกลุ่ม $(a, a^{-1})$ จะมีทั้งหมด $\frac{p-3}{2}$ คู่อันดับ

กรณี 1 $(1,1),(p-1,p-1)$ อยู่ในเซตเดียวกัน

แต่เนื่องจากแบ่งเป็นสองเซตที่มีสมาชิกเท่ากัน เซตละ $\frac{p-1}{2}$ ตัว

ดังนั้น เซตที่มี $(1,1),(p-1,p-1)$ อยู่แล้ว ก็ต้องหาเพิ่มมาอีก $\frac{p-5}{4}$ คู่

แต่ $\frac{p-5}{4}$ ไม่เป็นจำนวนเต็ม กรณีนี้จึงเป็นไปไม่ได้

กรณี 2 $(1,1),(p-1,p-1)$ อยู่คนละเซต

ก็แปลว่าต้องหาให้เพิ่มอีกเซตละ $\frac{p-3}{4}$ คู่อันดับพอดี

จำนวนวิธี (ทั้งในกรณีนี้ และทั้งหมด) จึงเท่ากับ
$$\binom{\frac{p-3}{2}}{\frac{p-3}{4}}$$

***โจทย์นี้ หากเราเปลี่ยนเงื่อนไขเป็น $p \equiv 1 \pmod{4}$ แล้วล่ะก็ คำตอบก็จะเกิดที่กรณี 1 เท่านั้น

คำตอบก็จะกลายเป็น
$$\binom{\frac{p-3}{2}}{\frac{p-5}{4}}$$

[AnDroMeDa]

อ่อครับขอแก้ไขโดยการไปดูนี่แทนนะ
http://www.artofproblemsolving.com/F...f=462&t=150391
แก้แล้วนะครับไม่ทราบว่าถูกหรือเปล่าเช็คทีครับ

[PP_nine]

#31 ทดเลขผิดไปบางจุดนะครับ

ส่วนที่เป็นกรณีทั่วไปก็น่าจะมองออกกันแล้วนะครับ ขอเก็บโจทย์เอาไว้ละกัน

ลุยโจทย์อินเวอร์สเซตสุดท้าย (สำหรับเนื้อหาระดับนี้ที่ผมมี) แทนดีกว่า โจทย์เซตนี้เป็นผลพลอยได้จาก Wolstenholme's Theroem ครับ


11.Wolstenholme's Theorem (ข้อคาดการณ์)
11.1) จากข้อ 9.1 ที่บอกว่า $p^2|a$ มีจำนวนเฉพาะ $p$ ที่ทำให้ $p^3|a$ ด้วยหรือไม่???
11.2) จากข้อ 9.2 ที่บอกว่า $p|a$ มีจำนวนเฉพาะ $p$ ที่ทำให้ $p^2|a$ ด้วยหรือไม่???


12.สำหรับจำนวนเฉพาะ $p \ge 5$ และจำนวนนับ $x,y$ ซึ่ง $(x,y)=1$ สอดคล้องกับ
$$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p}=\frac{x}{y}$$
พิสูจน์ว่า $px \equiv y \pmod{p^4}$


13.สำหรับจำนวนเฉพาะ $p \ge 5$ และจำนวนนับ $x,y$ ซึ่ง $(x,y)=1$ สอดคล้องกับ
$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{p^2}=\frac{x}{y}$$
พิสูจน์ว่า $p^2x \equiv y \pmod{p^5}$


คราวนี้ใครจะต่อเรื่องอื่นก็เชิญได้นะครับ ก่อนที่อินเวอร์สมอดุโลจะฝังเข้าไปในหัวมากกว่านี้

[จูกัดเหลียง]

#35 เเล้วถ้าเป็น $p^2|a$ จะทำไงอ่ะครับ

[PP_nine]

แบบที่ผมเฉลยมันก็คือการจับ $1,p-1$ แยกออกมา ที่เหลือให้หาคู่อินเวอร์สของตัวเอง

ซึ่งไม่ว่ายังไง คู่อินเวอร์สก็ต้องมีคู่ของมันเพียงตัวเดียวอยู่แล้ว ตรงจุดนี้จึงยังไม่นับเป็นวิธีน่ะครับ

คล้ายกับว่า partition {1,2,3,...,12} เป็นสองเซต โดยสมาชิกในแต่ละเซตต้องมีอีกสมาชิกในเซตเดียวกันที่บวกกันได้ 13

นั่นคือ ไม่ว่ายังไงก็ต้องจับคู่ (1,12), (2,11), (3,10), (4,9), (5,8), (6,7) เอาไว้ก่อนเสมอ ไม่ได้นับเป็นวิธี

จากนั้นค่อยจับกลุ่ม แบ่งเป็นสองกลุ่มที่มีจำนวนสมาชิกเท่ากัน ก็จะได้ $\binom{6}{3}$ วิธี ก็เป็นอันจบพิธี

อินเวอร์สก็คล้ายกัน เพียงแต่มีกรณีพิเศษที่ว่า $1,p-1$ ต้องอยู่โดดเดี่ยว

[PP_nine]

#35 ขอโทษครับ ผมทดเลขผิด เอาเป็นว่า ข้อนี้เป็นข้อคาดการณ์แทนละกัน เพราะตอนนี้ผมเองก็ไม่รู้ซะแล้วว่ามันจริงหรือเปล่า

[จูกัดเหลียง]

#37 งั้นช่วยเเสดงที่ทดผิดให้ดูหน่อยครับ (เผื่อผมจะได้นำไปประยุกต์ใช้)
ที่ว่าจงเเสดงว่า $p^2|a$

ปล.ข้อ 12-13 สรุปมันเป็น $x,y$ หรือ $a,b$ อ่ะครับ = =

[PP_nine]

ที่ผมทดผิดก็คือ $p$ ย่อมไม่มี inverse ใน mod p อยู่แล้ว (ผิดแบบโง่ๆ = =)

ถ้าที่ผมทด อย่างข้อ 11.1 ก็สมมติว่ามีจำนวนเฉพาะ $p$ ที่ทำให้ $\frac{a}{p^2} \equiv 0 \pmod{p}$ หลังจากจัดรูปสมการก็จะได้
$$\frac{a}{p^2} = \frac{b}{2p} \Big(\frac{1}{1(p-1)}+\frac{1}{2(p-2)}+\cdots+\frac{4}{(p-1)(p+1)} \Big)$$
แต่เราสมมติว่า LHS $\equiv 0 \pmod{p}$ ดังนั้น
$$\frac{b}{2p} \Big( -1^2-2^2-...-\Big( \frac{p-1}{2} \Big)^2\Big) \equiv 0 \pmod{p}$$
$$\frac{b}{2p} \Big( \frac{p-1}{2} \Big) \Big( \frac{p+1}{2} \Big) \Big( \frac{p}{6} \Big) \equiv 0 \pmod{p}$$
ซึ่งถ้าสมมติว่า $p$ มีอินเวอร์ส ก็จะสามารถตัดกันเหมือนเศษส่วนธรรมดา แต่มันทำไม่ได้

ถ้ายังจะทำต่อ ก็ใช้ความจริงที่ว่า สำหรับจำนวนเฉพาะ $p \ge 5$ นั้น $p^2 \equiv 1 \pmod{24}$ เสมอ

ก็จะเหลือแต่ว่า
$$\frac{b}{2} \equiv 0 \pmod{p}$$ $$b\cdot 2^{p-2} \equiv 0 \pmod{p}$$
แต่ $p\nmid b$ และ $p \nmid 2$ เสมอ จึงเกิดข้อขัดแย้ง

ปล.ข้อ 12-13 ใช้ $x,y$ ดีกว่า จะได้ไม่ปนกับของ Wolstenholmes'

[AnDroMeDa]

ข้อความเดิมเขียนโดยคุณ PP_nine

12.สำหรับจำนวนเฉพาะ $p \ge 5$ และจำนวนนับ $x,y$ ซึ่ง $(x,y)=1$ สอดคล้องกับ
$$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p}=\frac{x}{y}$$
พิสูจน์ว่า $px \equiv y \pmod{p^4}$

13.สำหรับจำนวนเฉพาะ $p \ge 5$ และจำนวนนับ $x,y$ ซึ่ง $(x,y)=1$ สอดคล้องกับ
$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{p^2}=\frac{x}{y}$$
พิสูจน์ว่า $p^2x \equiv y \pmod{p^5}$

คราวนี้ใครจะต่อเรื่องอื่นก็เชิญได้นะครับ ก่อนที่อินเวอร์สมอดุโลจะฝังเข้าไปในหัวมากกว่านี้

12.เนื่องจากWolstenholme's Theorem เราได้ $1+\frac{1}{2} +\frac{1}{3} +...+\frac{1}{p-1}=\frac{p^2k}{b}$โดย$(k,b)=1 \Rightarrow 1+\frac{1}{2} +\frac{1}{3} +...+\frac{1}{p-1}+\frac{1}{p} =\frac{p^3k+b}{bp} $
แต่ $(p^3k+b,pb)=1$ (ทำต่อเองนะ) จึงได้ $x=p^3k+b,y=pb$
$\therefore px-y=p^4k-pb+pb=p^4k$ หารด้วย $p^4$ ลงตัวซึ่งเห็นได้ชัด

13.เนื่องจากWolstenholme's Theorem เราได้ $1+\frac{1}{2^2} +\frac{1}{3^2} +...+\frac{1}{(p-1)^2}=\frac{pk}{b}$โดย$(k,b)=1 \Rightarrow 1+\frac{1}{2^2} +\frac{1}{3^2} +...+\frac{1}{(p-1)^2}+\frac{1}{p^2}=\frac{p^3k+b}{p^2b} $
แต่ $(p^3k+b,p^2b)=1$ จึงได้ $p^2x-y=p^5k+p^2b-p^2b=p^5k$ หารด้วย $p^5$ ลงตัวซึ่งเห็นได้ชัด

[PP_nine]

Wolstenholme มีประโยชน์มากกว่านี้ในการจัดรูปครับ

ลองใช้ $a,b$ ที่ผมเขียนเป็น theorem มาช่วยดูครับ แล้วดูว่า $x,y$ ในโจทย์ สัมพันธ์กันอย่างไรกับ $a,b$

[จูกัดเหลียง]

ลองเปลี่ยนเป็นอสมการสัก 2 ข้อนี้นะครับ ^^~ (ข้อเเรกผมไม่เเน่ใจเลย)
เเล้วผมกะว่า จะลองลง FE บ้างอะไรบ้าง 555
1.(Samin Riasat) Let $x,y,z>0 $
Prove that $$\frac{x}{y}+\frac{y}{z}+\frac{z}{x}\ge \sqrt{\frac{x+y}{2z}}+\sqrt{\frac{y+z}{2x}}+\sqrt{\frac{z+x}{2y}}$$

My Unsure Soln

By Cauchy
$$\sqrt{\frac{x+y}{2z}}+\sqrt{\frac{y+z}{2x}}+\sqrt{\frac{z+x}{2y}}\le \sqrt{\frac{3}{2}\sum_{cyc} \frac{x+y}{z}}\le \sqrt{3(\sum_{cyc}\frac{x}{y})}\le\sum_{cyc} \frac{x}{y}$$
โดย อสมการสุดท้ายสมมูลกับ $$ \frac{x}{y}+\frac{y}{z}+\frac{z}{x}\ge 3$$
เเต่ตอนนี้ผมต้องการที่จะพิสูจน์ว่า $\sum_{cyc} \frac{x}{z}\le \sum_{cyc}\frac{x}{y}$
ซึ่งผมคิดว่ามันคงจะเป็นจริงเเต่พิสูจน์ไม่ได้ = =

2.(Samin Riasat) Let $x,y,z>0$
Prove $$\sqrt{\frac{xy}{(x+y)(y+z)}}+\sqrt{\frac{yz}{(y+z)(z+x)}}+\sqrt{\frac{zx}{(z+x)(x+y)}}\le \frac{3}{2}$$

My Soln

$$\sum_{cyc} \sqrt{\frac{x}{x+y}}\sqrt{\frac{y}{y+z}}\le \sum_{cyc} \frac{x}{x+y}$$
and $$\sum_{cyc} \frac{x}{x+y}\le \frac{3}{2}\leftrightarrow \frac{x-y}{x+y}+\frac{y-z}{y+z}+\frac{z-x}{z+x}\le 0$$
Which is True by Rearangerment With WLOG assume $x\ge y\ge z$

[nooonuii]

1.เเต่ตอนนี้ผมต้องการที่จะพิสูจน์ว่า $\sum_{cyc} \frac{x}{z}\le \sum_{cyc}\frac{x}{y}$
ซึ่งผมคิดว่ามันคงจะเป็นจริงเเต่พิสูจน์ไม่ได้ = =

ไม่จริงครับ $x=1,y=3,z=2$

2.$\sum_{cyc} \frac{x}{x+y}\le \frac{3}{2}\leftrightarrow \frac{x-y}{x+y}+\frac{y-z}{y+z}+\frac{z-x}{z+x}\le 0$
Which is True by Rearangerment With WLOG assume $x\ge y\ge z$

แน่ใจเหรอว่าไม่เสียนัยทั่วไป ผมเคยแสดงให้ดูแล้วว่าอสมการนี้ไม่จริงทั้งสองข้าง

[nooonuii]

มาเติมข้อมูลให้ครับจะได้สิ้นสงสัย

ถ้า $x,y,z> 0$ แล้ว $\dfrac{x}{x+y}+\dfrac{y}{y+z}+\dfrac{z}{z+x}$ มีเรนจ์เป็นช่วงเปิด $(1,2)$

พิสูจน์ พิสูจน์ได้ไม่ยากว่า

$\dfrac{x}{x+y+z}<\dfrac{x}{x+y}<\dfrac{z+x}{x+y+z}$

$\dfrac{y}{x+y+z}<\dfrac{y}{y+z}<\dfrac{x+y}{x+y+z}$

$\dfrac{z}{x+y+z}<\dfrac{z}{x+y}<\dfrac{y+z}{x+y+z}$

ดังนั้น $1<\dfrac{x}{x+y}+\dfrac{y}{y+z}+\dfrac{z}{z+x}<2$

ส่วนการพิสูจน์ว่าเรนจ์เป็น $(1,2)$ จริงๆ ต้องใช้ความรู้เรื่องความต่อเนื่องของฟังก์ชันครับ

ถ้าจะทำตรงๆจะต้องแก้สมการติดรากวุ่นวายมาก เว้นแต่ว่าอยากรู้บางค่าก็จะกำหนดออกมาได้

ที่สำคัญคือสองค่าที่น้อยกว่าและมากกว่า $\dfrac{3}{2}$ ซึ่งเลือกได้ไม่ยาก เช่น

$x=1,y=2,z=3$ ได้ $\dfrac{x}{x+y}+\dfrac{y}{y+z}+\dfrac{z}{z+x}=\dfrac{89}{60}<\dfrac{3}{2}$

$x=1,y=3,z=2$ ได้ $\dfrac{x}{x+y}+\dfrac{y}{y+z}+\dfrac{z}{z+x}=\dfrac{91}{60}>\dfrac{3}{2}$

[nooonuii]

ต่อให้อีกนิด เพราะเห็นว่าวิธีนี้ไม่ต้องใช้เครื่องมือหนัก

ถ้า $x,y,z\geq 0$ โดยที่สองจำนวนใดๆไม่เป็นศูนย์พร้อมกัน แล้ว $\dfrac{x}{x+y}+\dfrac{y}{y+z}+\dfrac{z}{z+x}$ มีเรนจ์เป็นช่วงเปิด $(1,2)$

พิสูจน์ พิสูจน์ได้เหมือนเดิมว่า $1<\dfrac{x}{x+y}+\dfrac{y}{y+z}+\dfrac{z}{z+x}<2$

ให้ $t\in (1,2)$ เลือก $x=0,y=1,z=\dfrac{2-t}{t-1}$ จะได้ทันทีว่า

$\dfrac{x}{x+y}+\dfrac{y}{y+z}+\dfrac{z}{z+x}=t$

ถ้า $t=1,2$ จะไม่มี $x,y,z$ ที่สอดคล้องสมการข้างบน

ถ้าลองแก้สมการ

$\dfrac{x}{x+y}+\dfrac{y}{y+z}+\dfrac{z}{z+x}=1$

$\dfrac{x}{x+y}+\dfrac{y}{y+z}+\dfrac{z}{z+x}=2$

จะพบว่าคำตอบต้องเป็นศูนย์อย่างน้อยสองค่าซึ่งเป็นไปไม่ได้