#1
|
||||
|
||||
โจทย์จากจีน
ผมเห็นว่าช่วงนี้หัวข้อ"ข้อสอบโอลิมปิค" เริ่มซบเซาลงไป
ผมเลยอยากนำโจทย์ของคนจีนมาฝากครับ สำหรับคนที่มีเวลาว่างและอยากพัฒนาความสามารถของตัวเอง ก็ลองทำดูกันได้นะครับ 1.(ปี 1987 CMO ครั้งที่ 2) กำหนดให้ m,n เป็นจำนวนเต็มบวก และให้ $a_1,a_2,...,a_m$เป็นจำนวนคู่ที่แตกต่างกัน $b_1,b_2,...,b_n$เป็นจำนวนคี่ที่แตกต่างกัน ซึ่ง $(a_1+a_2+...+a_m)+(b_1+b_2+...+b_n) =1987$ จงหาค่าสูงสุดที่เป็นไปได้ของ $3m+4n$ 2.( ปี2001 โจทย์ข้อนี้เทียบเท่ากับข้อสอบ สสวท.รอบ 1 ของไทยครับ) สมมติมีจำนวนเฉพาะที่แตกต่างกันอยู่ 7 จำนวนคือ $a,b,c,a+b-c,b+c-a,c+a-b,a+b+c$ และ ในท่ามกลางจำนวน $a,b,c$ มีอยู่ 2 จำนวนที่บวกกันได้ 800 (พูดง่ายก็คือ $a+b=800$ หรือ $b+c=800$ หรือ$c+a=800$) ให้ d เป็นผลต่างระหว่างค่าสูงสุดกับค่าต่ำสุด(ใน 7 จำนวนข้างต้น) จงหาค่าสูงสุดที่เป็นไปได้ของ d 3.(ปี 1987 ข้อสอบแข่งขันระดับมัธยมศึกษาตอนปลาย ในเมืองๆหนึ่งของจีน)สำหรับทุกจำนวนเต็มบวก $n$ จงแสดงว่า $2^{n+1}|\left\lceil(3+\sqrt{5})^{2n}\right\rceil $ (ในที่นี้$\left\lceil x\right\rceil $ หมายถึงจำนวนเต็มบวกที่น้อยที่สุดที่มากกว่าหรือเท่ากับ $x$ ) สนุกสนุกนะครับ อย่าเครียด จะแก่เร็ว ป.ล. ผมยังมีโจทย์จากจีนอีกมากมาย สำหรับคนที่สนใจอยากได้โจทย์เพิ่มเิติม ถามผมได้นะครับ แต่ครั้งนี้เอาไป 3 ข้อก่อนละกันครับ กลัวว่าจะเครียดกัน 28 กรกฎาคม 2009 23:21 : ข้อความนี้ถูกแก้ไขแล้ว 3 ครั้ง, ครั้งล่าสุดโดยคุณ picmy |
#2
|
||||
|
||||
1. คิดว่าถ้าให้ $a_1,a_2...,a_m$ เป็นจำนวนคี่ แล้วให้ $b_1,b_2...b_n$ เป็นจำนวนคู่จะยากกว่านี้นะครับ? ลอกโจทย์มาผิดหรือเปล่า?
ก็ให้ $m=1 n=1985$ ก็จบแล้ว (ดูจากจำนวนคู่ทุกตัวและจำนวนคี่ทุกตัวที่จะแทนลงไปใน $a_i$ กับ $b_i$ ของเราต้องเป็น 2 กับ 1 ตามลำดับตลอด) ถ้าไม่ใช่ 2 หรือ 1 เราสามารถเพิ่มค่า 3m+4n ได้มากขึ้น สมมุติเช่นมีเลข 5 อยู่ในลำดับ ของเรา เราแยกออกมาเป็น 4+1 อะไรแบบนี้ก็ทำให้ 3m+4n มีค่ามากขึ้น 2. แปลกๆ...ผมได้ว่าไม่มี a,b,c ที่สอดคล้อง (ดู mod 3) 3.เห็นได้ว่าสำหรับทุกๆ $n\in N$ $(3-\sqrt{5})^{2n}<1$ ก็ต่อเมื่อ $4<5$ เป็นจริงอย่างเห็นได้ชัด นั้นคือเราได้ว่า $ \left\lceil\ (3+\sqrt{5})^{2n} \right\rceil = (3+\sqrt{5})^{2n}+(3-\sqrt{5})^{2n}$ นั้นเอง จึงเป็นการเพียงพอที่จะพิสูจน์ว่า $2^{n+1}| (3+\sqrt{5})^{2n}+(3-\sqrt{5})^{2n}$ หรือ $2^{n+1}| 2^{n}((7+\sqrt{5})^n+(7-\sqrt{5})^n)$ เป็นการเพียงพอที่จะพิสูจน์ว่า $2|(7+3\sqrt{5})^n+(7-3\sqrt{5})^n)$ ที่เหลือก็กระจายทวินามออกมา (แยกเคสคู่-คี่ให้ดูด้วยก็โอเค) แล้วก็จะได้ว่า $2|(7+3\sqrt{5})^n+(7-3\sqrt{5})^n)$ เป็นจริง ดังนั้น $2^{n+1}|\left\lceil\ (3+\sqrt{5})^{2n} \right\rceil $
__________________
Rose_joker @Thailand Serendipity 29 กรกฎาคม 2009 17:31 : ข้อความนี้ถูกแก้ไขแล้ว 4 ครั้ง, ครั้งล่าสุดโดยคุณ RoSe-JoKer |
#3
|
||||
|
||||
สำหรับข้อ 1 ผมพิมพ์ตกไปครับว่าต้องเป็นจำนวนที่แตกต่างกัน
ส่วนข้อ 2 ลอง $a=13,b=787,c=797$ดูนะคับ สำหรับข้อ 3 ครับ เยี่ยมมากครับ แนวความคิดถูกหมดแล้วแหละครับ แต่ผมว่าอาจพิมพ์ผิดไปนิดนึงนะ ตรง $2^{n+1}| 2^{n}((7+\sqrt{5})^n+(7-\sqrt{5})^n)$ น่าจะเป็น $2^{n+1}| 2^{n}((7+3\sqrt{5})^n+(7-3\sqrt{5})^n)$ (ไม่ใช่เรื่องใหญ่ครับ อิอิ) 28 กรกฎาคม 2009 17:47 : ข้อความนี้ถูกแก้ไขแล้ว 3 ครั้ง, ครั้งล่าสุดโดยคุณ picmy |
#4
|
||||
|
||||
แก้แล้วครับ พิมพ์ผิดเอง ขอโทษครับ
__________________
Rose_joker @Thailand Serendipity |
#5
|
||||
|
||||
เพิ่มเติมครับ สำหรับที่บอกว่าดู mod 3 แล้วได้ว่าไม่มี a,b,c ที่สอดคล้อง อาจจะเป็นเพราะลืมเคสที่ในจำนวน 7 จำนวนนั้นบางตัวมีโอกาสเป็น 3 ได้ครับ
|
#6
|
||||
|
||||
แหะๆ ข้อ 2 ผมผิดเองครับ...ผมคิดแต่ว่า 3 มันหารลงตัวเลยไม่ใช่จำนวนเฉพาะ แต่ลืมกรณีที่มันเป็น 3 ไปจริงๆนั้นแหละ ขอบคุณครับ ผมได้แล้วครับ T_T
วิธีทำ แยกเคส 1.a,b,c ประกอบด้วยเลขคู่ 3 ตัว ได้ว่า a=b=c=2 แต่ a+b+c ไม่ใช่จำนวนเฉพาะ 2.a,b,c ประกอบด้วยเลขคู่ 2 ตัว คี่ 1 ตัว สมมุติให้ a=b=2 เราได้ว่า a+b!=800 และ a+c=b+c!=800 ดังนั้นจึงไม่มี a,b,c สอดคล้อง 3.a,b,c ประกอบด้วยเลขคู่ 1 ตัว คี่ 2 ตัว สมมุติให้ a=2 เราได้ว่าถ้า a+b หรือ a+c = 800 เราจะได้ว่า b,c=798 ซึ่งไม่เป็นจำนวนเฉพาะ แต่ถ้า b+c=800 ก็ดู b+c-a=800-2=798 ไม่เป็นจำนวนเฉพาะ 4.a,b,c ประกอบด้วยเลขคี่ 3 ตัว โดยไม่เสียนัยเราสมมุติให้ a+b=800 = 2 (mod 3) ซึ่งเห็นได้ว่า มีเพียง a=2 b=0 a=0 b=2 a=1 b=1 (ใน mod 3) เท่านั้นที่ทำให้ a+b=2 (mod 3) case a=2 b=0 a=0 b=2 พิสูจน์แค่กรณี a=2 b=0 (mod 3) ก็พอมันเหมือนกัน จะได้ว่า b=3 แล้วเราได้ว่า a=797 แล้วเรามาดู 3+797-c,3-797+c,-3+797+c --> 800-c,-794+c,794+c ทั้งหมดนี้ต้องเป็นจำนวนเฉพาะ โดยเห็นได้ว่า c!= 0 (mod 3) เพราะถ้า c= 0 (mod 3) นั้นคือ c=3 แล้วเราได้ว่า 803 ไม่เป็นจำนวนเฉพาะ แต่ 800-c = 2-c (mod 3) -794+c = 1+c (mod 3) 794+c = 2+c (mod 3) เห็นได้ว่า ถ้า c=1,2 (mod 3) ก็จะมีตัวที่ทำให้ 3 หารลงตัวในสามตัวนี้ > 800-c,-794+c,794+c เสมอ ซึ่งจะมีปัญหาคือถ้าเกิด มันเท่ากับ 3 พอดี มันก็จะเป็นจำนวนเฉพาะ ลองดู กรณี 800-c=3 หรือ 800-c=-3 เราได้ว่า c=797,c=803 เห็นได้ว่า c=797 ใช้ได้เพียงตัวเดียว (c ต้องเป็น prime) แต่ 794+c=794+797=1591 ไม่เป็นจำนวนเฉพาะ ลองดู กรณี -794+c=3 หรือ -794+c=-3 เราได้ว่า c=797,791 เห็นได้ว่า c=797 ใช้ได้เพียงตัวเดียว (c ต้องเป็น prime) แต่ 794+c=794+797=1591 ไม่เป็นจำนวนเฉพาะ ลองดู กรณี 794+c=3 หรือ 794+c=-3 เราได้ว่า c=-791,-797 เห็นได้ว่า c=-797 ใช้ได้เพียงตัวเดียว (c ต้องเป็น prime) แต่ -794+c=-794-797=-1591 ไม่เป็นจำนวนเฉพาะ ดังนั้นกรณี a=2 b=0 (mod 3) จึงไม่มีจำนวนเฉพาะ a,b,c ที่สอดคล้องกับเงื่อนไข กรณี a=1 b=1 (mod 3) เราได้ว่า a+b-c= 2-c (mod 3) a-b+c= c (mod 3) -a+b+c= c (mod 3) a+b+c=2+c (mod 3) ตรงนี้เห็นได้ว่าถ้า c=0,1,2 (mod 3) เราก็จะได้ว่ามีซักตัวใน a+b-c,a-b+c,-a+b+c,a+b+c มี 3 หารลงตัว แต่มันอาจเป็น 3,-3 เองก็ได้ ดังนั้นก็ต้องไล่นิดหน่อย... กรณี c=0 (mod 3) นั้นคือ c=3 เราได้ว่า a+b+c=803 ซึ่งไม่เป็นจำนวนเฉพาะ กรณี c=1 (mod 3) เราได้ว่า a+b+c= 0 (mod 3) ดังนั้นอาจมีกรณี a+b+c=3 หรือ a+b+c=-3 ซึ่งจาก a+b=800 เราจะได้ว่า c=-797,-803 ซึ่งก็อาจจะใช้ได้แค่ c=-797 (เพราะ 803 ไม่เป็น prime) จากตรงนี้เราก็ต้องลองไล่จำนวนเฉพาะ a,b= 1 (mod 3) ดูจำนวนเฉพาะที่ con กับ 1 (mod 3) ตัวแรกๆเช่น 7,13,19 จะเห็นได้ว่าจาก 793 ไม่เป็นจำนวนเฉพาะและ 787 เป็นจำนวนเฉพาะ แสดงว่าจำนวนเฉพาะที่เราจะเอามาเป็นจำนวนเฉพาะที่มากสุดใน a,b,c ที่เป็นไปได้คือ 787 แล้วอย่างน้อย 1 ตัว ลองเอาไปแทนค่าดูใน a,b,c,a+b-c,a-b+c,-a+b+c,a+b+c จะเห็นได้ว่าเป็นจำนวนเฉพาะหมด ดังนั้น a=13 b=787 c=-797 เป็นชุดจำนวนเฉพาะ 1 ชุดที่ทำให้เงื่อนไขเป็นจริง ซึ่งทำให้เกิด d=787-(-797)= 1584 (กรณี a,b คู่อื่นไม่จำเป็นต้องคิด เพราะต่อให้มีก็ไม่สามารถให้ค่า d ที่มากกว่านี้ได้) กรณี c=2 (mod 3) เราได้ว่า a+b-c = 0 (mod 3) ซึ่งเราต้องเช็คกรณี a+b-c = 3 หรือ a+b-c=-3 (จาก a+b=800) เราได้ว่ามี c ที่เป็นไปได้คือ c=797 (c=803 ไม่ได้เพราะเป็นจำนวนเฉพาะ) จากตรงนี้เราก็ต้องลองไล่จำนวนเฉพาะ a,b= 1 (mod 3) ดูจำนวนเฉพาะที่ con กับ 1 (mod 3) ตัวแรกๆเช่น 7,13,19 จะเห็นได้ว่าจาก 793 ไม่เป็นจำนวนเฉพาะและ 787 เป็นจำนวนเฉพาะ แสดงว่าจำนวนเฉพาะที่เราจะเอามาเป็นจำนวนเฉพาะที่มากสุดใน a,b,c ที่เป็นไปได้คือ 787 แล้วอย่างน้อย 1 ตัว ลองเอาไปแทนค่าดูใน a,b,c,a+b-c,a-b+c,-a+b+c,a+b+c จะเห็นได้ว่าเป็นจำนวนเฉพาะหมด แต่คราวนี้ d=797-13=784 ซึ่งน้อยกว่าอันแรก ดังนั้น d=1584 จึงเป็น d max (เอามาจาก a=13 b=787 c=-797) ...... เขียนมาถึงตรงนี้แอบสับสน กรณี a เป็นลบ แล้ว b เป็นบวก...
__________________
Rose_joker @Thailand Serendipity 28 กรกฎาคม 2009 18:50 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ RoSe-JoKer |
#7
|
||||
|
||||
ไม่รู้ว่าโจทย์สนใจแต่จำนวนเฉพาะบวกรึเปล่า
|
#8
|
||||
|
||||
ใช่ครับ สนใจแค่จำนวนเฉพาะบวกครับ และผมพิมพ์ตกอีกตามเคยว่า จำนวน 7 จำนวนนั้นแตกต่างกันหมดครับ ขอโทษด้วยครับ
28 กรกฎาคม 2009 20:09 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ picmy |
#9
|
|||
|
|||
ผมงงๆข้อ 3 อยู่ครับ คือ...
ตั้งแต่ที่โจทย์เขียน มันเขียนว่า ในที่นี้ $\lfloor x\rfloor$ หมายถึงจำนวนเต็มบวกที่น้อยที่สุดที่มากกว่าหรือเท่ากับ $x$ จากที่บรรยายมา มันคือ ceiling function ไม่ใช่เหรอครับ? มันก็ึควรจะเป็น $\left\lceil x\right\rceil$ แต่ทำไมทั้งตัวโจทย์ แล้วก็ตัววิธีทำของคุณ rose-joker สัญลักษณ์มันออกมาเป็น floor หมดเลย... แล้วก็... ขอแสดงอีกวิธีที่คล้ายๆ แต่ไม่เหมือน: ขอ claim เลยว่า $\lceil (3+\sqrt{5})^{2n}\rceil=(3+\sqrt{5})^{2n}+(3-\sqrt{5})^{2n}$ (เพราะมีคนอธิบายแล้ว) ให้ $a_n=(3+\sqrt{5})^{2n}+(3-\sqrt{5})^{2n}$ จะได้ว่า $a_n=28a_{n-1}-16a_{n-2}$ โดยที่ $n\geq 3$ เป็นจำนวนเต็มบวก และ $a_1=28,a_2=752$ (ตรงนี้ก็พิสูจน์โดยกระจาย บวกลบคูณหารเอา ไปเรื่อยๆ) คราวนี้ก็ induct บน $n$ ได้เลยว่า $2^{n+1}|\lceil (3+\sqrt{5})^{2n}\rceil$ เพราะ $4|28,4|16,4|28,4|752$ ข้อ 1 ดูเหมือนว่าจะตอบ $221$ เมื่อ $m=27,n=35$;$a_1=2,a_2=4,a_3=6,\cdots ,a_{26}=52,a_{27}=60$;$b_1=1,b_2=3,b_3=5,\cdots ,a_{34}=67,a_{35}=69$ 28 กรกฎาคม 2009 23:07 : ข้อความนี้ถูกแก้ไขแล้ว 3 ครั้ง, ครั้งล่าสุดโดยคุณ beginner01 เหตุผล: แก้เพื่อให้สอดคล้องกับ #12 |
#10
|
||||
|
||||
อ้างอิง:
แต่โดยทั่วไปแล้วเราใช้ $\left\lceil\,\right\rceil$ แทน ceiling function ครับ สามารถดูจากลิงค์ข้างล่างนะครับ http://mathworld.wolfram.com/CeilingFunction.html แต่ผมก็เพิ่งสังเกตเหมือนกันครับว่า เมื่อเราพิมพ์คำสั่ง \left\lceil\,\right\rceil ใน Latex กลับได้ออกมาเป็น $\left\lfloor\,\right\rfloor $ และเมื่อใช้ \left\lfloor\,\right\rfloor กลับได้ออกมาเป็น $\left\lceil\,\right\rceil$ อันนี้คงต้องลองสอบถามผู้ดูแลเว็บครับ ว่าเป็นเพราะบางประเทศใช้เครื่องหมายอย่างนี้หรือเปล่า แต่ที่ผมเข้าใจคือ การใช้ $\lceil x\rceil$ แทน ceiling ของ $x$ ค่อนข้างจะ make sense กว่า เพราะว่าขีดเล็กๆข้างบนสองขีด จะเตือนสติเราว่า $\lceil x\rceil$ เป็นจำนวนเต็มที่มากกว่าหรือเท่ากับ $x$ 28 กรกฎาคม 2009 23:23 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ picmy |
#11
|
||||
|
||||
อ้างอิง:
คุณ beginner01 มีวิธีการทำอย่างไร ลองโพสต์มาให้เพื่อนๆได้ ชื่นชมกันได้นะครับ |
#12
|
|||
|
|||
*คุณ TOP มาไขกระจ่างใน คห.13 เรียบร้อยแล้ว*
ส่วนข้อ 1... คือมันน่าจะมีวิธีที่ดีกว่าของผมแน่ๆ เพราะมันดูถึกไปหน่อย สิ่งที่ทำไปก็คือ: 1.ลองไล่ $n$ จากมากไปน้อย ไปเรื่อยๆ โดยสังเกตว่า $n$ ต้องเป็นจำนวนคี่ ไม่นั้น ผลรวมพวก $a_i,b_i$ จะไม่เท่ากับ 1987 แล้วก็เราสามารถเรียงลำดับ $a_i$ ด้วยกัน และ $b_i$ ด้วยกันได้ 2.สำหรับแต่ละ $n$ เื่พื่อให้ $m$ มากที่สุด เราก็ควรจะทำให้ $b_1+b_2+\cdots+b_n$ มีค่าต่ำสุดเท่าที่เป็นไปได้ ก็คือ $b_1=1,b_2=3,...$ ส่วน $a_i$ แต่ละตัวก็ควรจะน้อยๆเข้าไว้ก่อน จะได้ $m$ มีค่ามากๆ ก็คือ $a_1=2,a_2=4,...$ -สังเกตผลบวก ก็จะได้ว่า $a_1+a_2+...+a_m=m(m+1)$ ส่วน $b_1+b_2+...+b_n=n^2$ ดังนั้น $m(m+1)=1987-n^2$ แต่ในบางครั้ง สมการนี้มันไม่มีคำตอบ เราก็ต้องไปเปลี่ยน $a_m$ ก็คือตัวสุดท้าย เพื่อให้ผลรวมมันเป็นไปได้ ก็จะสรุปได้ว่า เพื่อจะให้ $m$ มากที่สุด เราก็ควรจะมี $b_1=1,b_2=3,...,b_n=2n-1$ และ $a_1=2,a_2=4,...,a_{m-1}=2m-2,a_m=k$ ที่เหลือก็นั่งไล่แต่ละกรณี... 22 กรณี... 28 กรกฎาคม 2009 23:12 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ beginner01 เหตุผล: มากมายหลายเหตุผลจนพิมพ์ไม่พอ |
#13
|
||||
|
||||
อ้างอิง:
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson. 28 กรกฎาคม 2009 23:08 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ TOP |
#14
|
||||
|
||||
ที่แท้เราก็มีความเข้าใจที่ตรงกัน แต่สิ่งที่เรามองเห็นไม่เหมือนกันนี่เอง นะครับคุณ Beginner01
ขอบคุณคุณ TOP ที่ให้ความกระจ่าง ทำให้ผมมองเห็นในสิ่งที่คนส่วนใหญ่เห็น ฮาๆๆ ผมแก้เครื่องหมายในโจทย์ให้ถูกต้องแล้วนะครับ สำหรับข้อ 1 ของคุณ Beginner01 ผมว่าจริงอย่างที่คุณว่าครับว่าอาจจะถึกไปนิด แต่ยังไงสุดท้ายก็ได้คำตอบ เพราะฉะนั้นมันไม่ใช่เรื่องเลวร้ายครับที่จะถึก แต่ที่แน่ๆ เป็นเรื่องดีแน่ๆ ถ้าเราจะหาวิธีที่กระทัดรัดกว่า หลังจากที่เราได้คำตอบแล้ว สู้ๆต่อไปนะครับ |
#15
|
||||
|
||||
อ้างอิง:
ขอบคุณล่วงหน้าครับ
__________________
Rose_joker @Thailand Serendipity |
|
|