ข้อสอบสอวน.ค่ายที่ 2 ปี 2550
 

มาช่วยกันเฉลยข้อสอบสอวน.

ทำไมผมหาข้อสอบไม่เจอล่ะคับ ?? :sweat:

:laugh: :laugh: :laugh: :laugh:

ทฤษฏีจำนวน
3.จงพิสูจน์ทฤษฏีบทของวิลสัน
4.จงหาจำนวนเต็มบวก m,n ทั้งหมดที่ทำให้ 2^m+3ⁿ เป็นกำลังสองสมบูรณ์

คอมบินาทอริค
1.ทาสี 2 สีในระนาบคือสีแดงและสีน้ำเงินจงพิสูจน์ว่าจะต้องมีสี่เหลี่ยมผึนผ้าที่มีจุดยอดมุมทั้งสี่เป็นสีเดียวกัน

ให้ $x^2=2^m+3^n$

พิจารณา modulo $3$ จะพบว่า $x^2\equiv(-1)^m\pmod3$ แต่ $x^2\equiv-1\pmod3$ ไม่มีคำตอบ ดังนั้น $m$ จะต้องเป็นจำนวนคู่ ให้ $m=2a$ นั่นคือ $x^2=2^{2a}+3^n$

พิจารณา modulo $4$ จะพบว่า $x^2\equiv(-1)^n\pmod4$ แต่ $x^2\equiv-1\pmod4$ ไม่มีคำตอบ ดังนั้น $n$ จะต้องเป็นจำนวนคู่ ให้ $n=2b$ นั่นคือ $x^2=2^{2a}+3^{2b}$

เราจึงได้ว่า $3^{2b}= (x-2^a)(x+2^a)$ และเนื่องจาก $\gcd(x-2^a, x+2^a)$ จะต้องหาร $(x+2^a)-(x-2^a)=2^{a+1}$ ลงตัว และหาร $3^{2b}$ ลงตัวด้วย แสดงว่า $\gcd(x-2^a, x+2^a)=1$

ดังนั้นเราจึงได้ว่า $x-2^a=1$ และ $x+2^a=3^{2b}$ นั่นคือ $x=1+2^a$ และ $1+2^{a+1}=3^{2b}$ แสดงว่า $(3^b-1)(3^b+1)=2^{a+1}$ แต่เนื่องจาก $\gcd(3^b-1, 3^b+1)$ จะต้องหาร $(3^b+1) - (3^b-1)=2$ ลงตัว ดังนั้น $\gcd(3^b-1, 3^b+1)$ เท่ากับ $1$ หรือ $2$

ถ้า $\gcd(3^b-1, 3^b+1)=1$ เราจะได้ว่า $3^b-1=1$ ซึ่งเป็นไปไม่ได้

ถ้า $\gcd(3^b-1, 3^b+1)=2$ เราจะได้ว่า $3^b-1=2$ นั่นคือ $b=1$ ซึ่งเมื่อคิดย้อนกลับไป เราจะได้ว่าคำตอบทั้งหมดคือ $(m,n)=(4,2)$ ครับ

ข้อนี้ ฮิตจริงๆ

สอวน.ปีนี้ไม่มีอสมการครับ มีสมการเชิงฟังก์ชันแทน
สมการเชิงฟังก์ชัน
2.จงหา $f:N \rightarrow N$ โดยที่ $f(m-n)+f(m+n)=\frac{f(2m)+f(2n)}{2}$

2.จงหา f:N→N โดยที่ f(m−n)+f(m+n)=2f(2m)+f(2n)
ข้อนี้คุ้นๆนะ

dektep ทฤษฏีบทของวิลสัน คืออะไร ???

ทฤษฏีบทของ Wilson กล่าวว่า
ถ้า p เป็นจำนวนเฉพาะแล้ว (p-1)!สมมูลกับ -1(mod p) ครับ

ช่วยอธิบายละเอียดกว่านี้ได้มั๊ยคะ

สังเกต ดอกจัน (4x7) พวกนี้ดูนะครับ

* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *

พิจารณาแถวล่างสุดก่อน โดยจากหลังรังนกพิราบ จะพบว่ามีอย่างน้อย 4 จุดทาสีเดียวกัน สมมติเป็นสีแดง จากนั้นพิจารณาตัวที่อยู่เหนือดอกจันสีแดงเหล่านี้ขึ้นไปครับ (ผมจะใช้สัญลักษณ์ X นะครับ)

x x * * x * x
x x * * x * x
x x * * x * x
* * * * * * *

แบ่งคิด 2 cases ครับ
(i) ถ้ามีตัว x 2 ตัวในแถวใดแถวหนึ่ง ทาสีแดง การพิสูจน์ก็จะสิ้นสุด นั่นคือได้สี่เหลี่ยมที่จุดมุมเป็นสีแดง เช่น
x x * * x * x
x x * * x * x
x x * * x * x
* * * * * * *

(ii) ถ้า (i) ไม่เกิด แสดงว่า ตั้งแต่แถว 1 ถึง 3 ทาสีน้ำเงินอย่างน้อย 3 จุด (ดังตัวอย่างข้างล่าง) ซึ่งก็จะได้สี่เหลี่ยมแบบที่ต้องการ เช่นเดียวกัน แต่เป็น version สีน้ำ้เงิน
x x * * x * x
x x * * x * x
x x * * x * x
* * * * * * *

NOTE: ถ้าสังเกตดีๆ ข้อนี้ก็เทียบเท่ากับ combinatorics ข้อนึงของ สอวน. FINAL ROUND ปี 2549 ลองไปค้นดูนะครับว่าข้อไหน

ขอมีส่วนร่วมเฉลยสักนิด :-)
 

เฉลย COMBINATORICS

ข้อ 1.ให้สีแก่จุดบนระนาบด้วยสีเพียงสองสี คือ สีแดงและสีน้ำเงิน
จงแสดงว่าต้องมีสี่เหลี่ยมผืนผ้าที่จุดยอดมุมของสี่เหลี่ยมผืนผ้ามีสีเดียวกัน

วิธีทำ พิจารณาระนาบใดๆ ที่คลุมด้วยจำนวนจุดแนวนอน n จุด และจุดแนวตั้งจำนวน 2^n + 1 แถว
เนื่องจากมีสีอยู่เพียง 2 สี ดังนั้นการสลับสีในแต่ละแถวที่มี n จุด จึงเป็นไปได้เพียง 2^n วิธีเท่านั้น
(แนวคิดเหมือนกับการคิดระบบเลขฐาน 2 ที่ว่าเลขฐานสอง 8 หลักมีได้เพียง 2^8 = 256 จำนวน)

ฉะนั้นโดยหลักรังนกพิราบ จะได้ว่าแนวตั้ง 2^n + 1 แถวนั้น ต้องมี 2 แถวใดๆ ที่เหมือนกันทุกประการ

จากนั้นเมื่อพิจารณา 2 แถวที่เหมือนกันทุกประการนั้น จะพบว่าเมื่อ n > 2 ย่อมมีคู่ที่มีสีเหมือนกัน
อย่างน้อย 2 คู่ ซึ่งทำให้เกิดสี่เหลี่ยมผืนผ้าตามที่ต้องการเสมอ

การยกตัวอย่างของคุณ passer-by ในความเห็นที่ 11 อาจไม่เกิดสี่เหลี่ยมผืนผ้าเสมอไป
ตามความเห็นที่ 12 ที่ผมอธิบายไปแล้ว

Number Theory ข้อ 1 กับ 2 ผมเฉลยไว้ใน วิชาการ.คอม (ความเห็นที่ 25 และ 26 ในนั้น)

Number Theory ข้อ 1 กับ 2

Algebra ข้อ 3 ผมเฉลยไว้ในความเห็นที่ 30 ตามลิงค์นี้

Algebra ข้อ 3