|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#16
|
||||
|
||||
คุณ dektep เจ้าของกระทู้ มั่นใจแค่ไหนครับกับคะแนนรอบนี้ ?
มีข้อสอบชุดไหนที่ทำได้เยอะ และชุดไหนลำบากบ้าง :-)
__________________
หนึ่งปีของอัจฉริยะ อาจเทียบเท่าชั่วชีวิตของคนบางคน |
#17
|
|||
|
|||
อืม... แต่ผมลองอ่านดูการพิสูจน์ก็โอเคดีทั้ง 2 แบบนะครับ ที่อาจจะมีปัญหาของคุณ passer-by คือ ผมคิดว่าใช้แค่ขนาด $3\times7$ ก็น่าจะพอแล้ว เพราะแค่ 2 บรรทัดก็ force ให้เกิดสี่เหลี่ยมผืนผ้าสีน้ำเงินได้แล้วนี่ครับ
|
#18
|
||||
|
||||
จริงอย่างที่คุณ warut แนะนำครับ ผมอาจเลือกขอบเขตที่กว้างซึ่งอธิบายได้ง่าย
แต่อาจไม่ใช่ขอบเขตที่เล็กที่สุด
__________________
หนึ่งปีของอัจฉริยะ อาจเทียบเท่าชั่วชีวิตของคนบางคน |
#19
|
|||
|
|||
โจทย์ Ramsey Theory ก็อย่างงี้แหละครับ ถ้าการพิสูจน์เรียบง่ายก็มักให้ bound ที่ไม่ดี ถ้าต้องการ bound ที่ดีขึ้น การพิสูจน์ก็มักจะยุ่งยากตามขึ้นไปด้วย ส่วน bound ที่ดีที่สุดก็มักจะมาจาก exhaustive search โดย computer แหละครับ
ป.ล. ตอนนี้ผมเริ่มสนใจโจทย์ข้อนี้ขึ้นมาเป็นพิเศษแล้วล่ะครับ อยากรู้ว่าจำนวนจุดที่น้อยที่สุด ที่จำเป็นต้องใช้ในการพิสูจน์คือกี่จุด |
#20
|
|||
|
|||
อ้างอิง:
* * * * * * * * * * * * * * * * * * * * * ซึ่งจะได้เป็น blue square แทน แต่ถ้าพิจารณาส่วนที่ยังเป็นดอกจันสีดำประกอบ ก็มีความเป็นไปได้สูงที่จะ ได้สี่ี่เหลี่ยมผืนผ้า ครับ ถ้าเป็น $ 4 \times 7 $ ผมว่า ก็ save แล้วนะครับ แม้อาจจะไม่ใช่ lattice แบบที่ใช้จุดน้อยที่สุดก็ตาม ส่วนวิธีของคุณ switchgear ก็เข้าใจง่ายดีครับ จะว่าไป เรื่องการค้นหา minimum bound ทำให้ผมนึกถึงคำถามข้อนึงซึ่ง proveได้โดยง่าย ด้วย basic combinatorics มีเมือง 2006 เมือง แต่ละเมืองมีถนนเชื่อมตรงถึงเมืองอื่นอีกอย่างน้อย 1004 เมือง พิสูจน์ว่า ถึงแม้มีถนนขาด 1 สาย ก็ยังหาบริเวณที่ขับรถวน ในลักษณะ สามเหลี่ยม หรือสี่เหลี่ยมได้้ ผมเคยคิดเหมือนกันว่า ถ้าไม่ใช้ 1004 จะมีเลขที่น้อยกว่านี้หรือไม่ แล้วทำให้ข้อความนี้ยังเป็นจริง
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว |
#21
|
|||
|
|||
อ๋อ...เข้าใจละ คือปกติผมนับว่า สี่เหลี่ยมจัตุรัส เป็น สี่เหลี่ยมผืนผ้า ชนิดหนึ่งน่ะครับ
ตอนนี้รู้แล้วครับว่า ถ้านับแบบผม และคิดสี่เหลี่ยมผืนผ้าทั้งที่อยู่ใน แนวตั้ง-แนวนอน และแนวทแยง ใช้ $3\times7$ นี่เล็กสุดแล้วครับ เนื่องจาก $3\times6$ ใช้ไม่ได้เพราะ * * * * * * * * * * * * * * * * * * และ $4\times5$ ก็ใช้ไม่ได้เพราะ * * * * * * * * * * * * * * * * * * * * Edit: รวมกรณีที่คิดแนวทแยงเข้าไปด้วย และแก้ไขข้อผิดพลาดแล้วครับ 18 เมษายน 2007 04:01 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ warut |
#22
|
||||
|
||||
ตามวิธีที่ผมใช้ในความเห็นที่ 12
ผมลองมองว่าหากให้ด้านยาวคือ 2^n + 1 = 7 แก้สมการจะได้ว่า n = 2.585 --> n = 3 ซึ่งตรงกับคำแนะนำของคุณ warut แสดงว่าที่จริงแล้วการเฉลยของผมกับคุณ passer-by สอดคล้องกันดี แต่แนวคิดนี้เอามาอธิบาย 3x6 ไม่ได้ ถ้าเราใช้การปัดขึ้นตลอด ? ฉะนั้นหากเราใช้การปัดเข้าหาจำนวนเต็มที่ใกล้สุดแทน จะอธิบายข้อนี้ได้ เพราะหาก 2^n + 1 = 6 จะได้ n = 2.32 --> n = 2 ซึ่งขัดกับเงื่อนไข ที่ผมอธิบายไว้คือ n > 2 จึงจะทำให้เกิดการบังคับให้เกิดสี่เหลี่ยมผืนผ้า สำหรับ 4x5 ก็ไม่เกิดสี่เหลี่ยมผืนผ้าเช่นกัน! ดังนั้น bound เล็กสุดคงเป็น 3x7 ตามที่คุณ warut แนะนำไว้
__________________
หนึ่งปีของอัจฉริยะ อาจเทียบเท่าชั่วชีวิตของคนบางคน |
#23
|
|||
|
|||
แหม... คุณ Switchgear วิเคราะห์โจทย์ combinatorics อย่างกับเป็นโจทย์ analysis เลย
ครับ... upper bound ที่ได้จากการพิสูจน์ของคุณ Switchgear ก็คือให้ $n=3$ ซึ่งจะได้ upper bound $=3\times(2^3+1) = 3\times9 =27$ ในขณะที่ least upper bound $=3\times7=21$ ครับ |
#24
|
|||
|
|||
จาก combinatorics ข้อนี้ ทำให้เกิดคำถามแตกแขนงออกไปได้อีก เช่น
(1) ทาสีจุดบนระนาบ ด้วยสีแดงและน้ำเงิน พิสูจน์ว่า มีสามเหลี่ยมด้านเท่าอย่างน้อย 1 รูปที่จุดมุมทาสีเดียวกััน (monochromatic equilateral triangle) (2) ทาสีจุดบน lattice (คู่อันดับ(x,y) ของจำนวนเต็ม) ด้วยสีแดงและน้ำเงิน จะเกิดเหตุการณ์แบบข้อ(1)หรือไม่ ใครที่ว่างๆหรือสนใจ ก็ลองคิดดูเพลินๆนะคร้าบ
__________________
เกษียณตัวเอง ปลายมิถุนายน 2557 แต่จะกลับมาเป็นครั้งคราว |
#25
|
||||
|
||||
หลังจากวิ่งออกกำลังกายมาเหนื่อยๆ ระหว่างเดินก็เอาปัญหานี้มาคิดดูครับ หลังจากได้แต่อ่านปัญหานี้มานาน
อ้างอิง:
สมมติว่าเป็นสีน้ำเงิน จะมีรูปแบบคู่สีทั้งสิ้น 3 แบบคือ xxx , xxx , xxx เนื่องจากเรามีสองสี จึงมีรูปแบบของคู่สีที่เกิดขึ้นได้ทั้งหมด 3 x 2 = 6 แบบ ดังนั้นเมื่อเรานำกริดขนาด 1x3 มาวางซ้อนกัน 7 อัน หรือเป็นกริดขนาด 7x3 จึงต้องมีรูปแบบคู่สีหนึ่งที่ซ้ำกัน คู่สีที่ซ้ำกัน 2 คู่นี้เองที่เป็นจุดยอดมุมของสี่เหลี่ยมผืนผ้าที่มีสีเดียวกัน สำหรับกริดที่มีขนาดใหญ่กว่า 7x3 เราก็พิจาณาเฉพาะกริดขนาดเล็ก 7x3 มาสักตำแหน่งหนึ่ง ก็จะได้สี่เหลี่ยมผืนผ้าตามต้องการ
__________________
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. |
#26
|
|||
|
|||
ตัวอย่าง $4\times5$ อันเก่าของผมมีข้อผิดพลาดครับ เนื่องจากยังมี monochromatic rectangle ตามแนวทแยงอยู่ โชคดีไม่มีใครเห็นก่อนผม ลองหาดูนะครับว่าอยู่ไหน
* * * * * * * * * * * * * * * * * * * * |
หัวข้อคล้ายคลึงกัน | ||||
หัวข้อ | ผู้ตั้งหัวข้อ | ห้อง | คำตอบ | ข้อความล่าสุด |
ข้อสอบช้างเผือก ทอ. พ.ศ.2550 | Eddie | ข้อสอบในโรงเรียน ม.ต้น | 50 | 25 พฤศจิกายน 2012 22:43 |
ข้อสอบ คัดเลือกนักเรียนระดับเขต ช่วงชั้นที่ 3 ปี 2550 | Tinyo Dragonn | ข้อสอบในโรงเรียน ม.ต้น | 55 | 31 กรกฎาคม 2008 15:23 |
สอวน.ปีนี้ (2550) | HIPPO1234 | ข้อสอบโอลิมปิก | 14 | 27 พฤษภาคม 2007 12:54 |
Advanced National Educational Test 2550 | Mastermander | ข้อสอบในโรงเรียน ม.ปลาย | 53 | 04 พฤษภาคม 2007 03:00 |
|
|