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

[Switchgear]

คุณ dektep เจ้าของกระทู้ มั่นใจแค่ไหนครับกับคะแนนรอบนี้ ?

มีข้อสอบชุดไหนที่ทำได้เยอะ และชุดไหนลำบากบ้าง :-)

[warut]

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

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

อืม... แต่ผมลองอ่านดูการพิสูจน์ก็โอเคดีทั้ง 2 แบบนะครับ ที่อาจจะมีปัญหาของคุณ passer-by คือ ผมคิดว่าใช้แค่ขนาด $3\times7$ ก็น่าจะพอแล้ว เพราะแค่ 2 บรรทัดก็ force ให้เกิดสี่เหลี่ยมผืนผ้าสีน้ำเงินได้แล้วนี่ครับ

[Switchgear]

จริงอย่างที่คุณ warut แนะนำครับ ผมอาจเลือกขอบเขตที่กว้างซึ่งอธิบายได้ง่าย
แต่อาจไม่ใช่ขอบเขตที่เล็กที่สุด

[warut]

โจทย์ Ramsey Theory ก็อย่างงี้แหละครับ ถ้าการพิสูจน์เรียบง่ายก็มักให้ bound ที่ไม่ดี ถ้าต้องการ bound ที่ดีขึ้น การพิสูจน์ก็มักจะยุ่งยากตามขึ้นไปด้วย ส่วน bound ที่ดีที่สุดก็มักจะมาจาก exhaustive search โดย computer แหละครับ

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

[passer-by]

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

อืม... แต่ผมลองอ่านดูการพิสูจน์ก็โอเคดีทั้ง 2 แบบนะครับ ที่อาจจะมีปัญหาของคุณ passer-by คือ ผมคิดว่าใช้แค่ขนาด $3\times7$ ก็น่าจะพอแล้ว เพราะแค่ 2 บรรทัดก็ force ให้เกิดสี่เหลี่ยมผืนผ้าสีน้ำเงินได้แล้วนี่ครับ

ความเห็นผม ก็คือ $ 3\times 7 $ ก็เกิดแหละครับ แต่ต้องอธิบายเพิ่ม เพราะบางที ถ้า follow ตาม การพิสูจน์ใน case ที่ 2 ของผม อาจจะเกิดแบบรูปข้างล่างก็ได้ครับ

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

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

ถ้าเป็น $ 4 \times 7 $ ผมว่า ก็ save แล้วนะครับ แม้อาจจะไม่ใช่ lattice แบบที่ใช้จุดน้อยที่สุดก็ตาม

ส่วนวิธีของคุณ switchgear ก็เข้าใจง่ายดีครับ

จะว่าไป เรื่องการค้นหา minimum bound ทำให้ผมนึกถึงคำถามข้อนึงซึ่ง proveได้โดยง่าย ด้วย basic combinatorics

มีเมือง 2006 เมือง แต่ละเมืองมีถนนเชื่อมตรงถึงเมืองอื่นอีกอย่างน้อย 1004 เมือง พิสูจน์ว่า ถึงแม้มีถนนขาด 1 สาย ก็ยังหาบริเวณที่ขับรถวน ในลักษณะ สามเหลี่ยม หรือสี่เหลี่ยมได้้

ผมเคยคิดเหมือนกันว่า ถ้าไม่ใช้ 1004 จะมีเลขที่น้อยกว่านี้หรือไม่ แล้วทำให้ข้อความนี้ยังเป็นจริง

[warut]

อ๋อ...เข้าใจละ คือปกติผมนับว่า สี่เหลี่ยมจัตุรัส เป็น สี่เหลี่ยมผืนผ้า ชนิดหนึ่งน่ะครับ

ตอนนี้รู้แล้วครับว่า ถ้านับแบบผม และคิดสี่เหลี่ยมผืนผ้าทั้งที่อยู่ใน แนวตั้ง-แนวนอน และแนวทแยง ใช้ $3\times7$ นี่เล็กสุดแล้วครับ เนื่องจาก $3\times6$ ใช้ไม่ได้เพราะ

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

และ $4\times5$ ก็ใช้ไม่ได้เพราะ

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

Edit: รวมกรณีที่คิดแนวทแยงเข้าไปด้วย และแก้ไขข้อผิดพลาดแล้วครับ

[Switchgear]

ตามวิธีที่ผมใช้ในความเห็นที่ 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 แนะนำไว้

[warut]

แหม... คุณ Switchgear วิเคราะห์โจทย์ combinatorics อย่างกับเป็นโจทย์ analysis เลย

ครับ... upper bound ที่ได้จากการพิสูจน์ของคุณ Switchgear ก็คือให้ $n=3$ ซึ่งจะได้

upper bound $=3\times(2^3+1) = 3\times9 =27$

ในขณะที่ least upper bound $=3\times7=21$ ครับ

[passer-by]

จาก combinatorics ข้อนี้ ทำให้เกิดคำถามแตกแขนงออกไปได้อีก เช่น

(1) ทาสีจุดบนระนาบ ด้วยสีแดงและน้ำเงิน พิสูจน์ว่า มีสามเหลี่ยมด้านเท่าอย่างน้อย 1 รูปที่จุดมุมทาสีเดียวกััน (monochromatic equilateral triangle)
(2) ทาสีจุดบน lattice (คู่อันดับ(x,y) ของจำนวนเต็ม) ด้วยสีแดงและน้ำเงิน จะเกิดเหตุการณ์แบบข้อ(1)หรือไม่

ใครที่ว่างๆหรือสนใจ ก็ลองคิดดูเพลินๆนะคร้าบ

[TOP]

หลังจากวิ่งออกกำลังกายมาเหนื่อยๆ ระหว่างเดินก็เอาปัญหานี้มาคิดดูครับ หลังจากได้แต่อ่านปัญหานี้มานาน

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

พิจารณา การลงสองสีบน กริดขนาด 1x3 จากกฎรังนกพิราบพบว่า ต้องมี 1 คู่สีเสมอ
สมมติว่าเป็นสีน้ำเงิน จะมีรูปแบบคู่สีทั้งสิ้น 3 แบบคือ
xxx , xxx , xxx

เนื่องจากเรามีสองสี จึงมีรูปแบบของคู่สีที่เกิดขึ้นได้ทั้งหมด 3 x 2 = 6 แบบ
ดังนั้นเมื่อเรานำกริดขนาด 1x3 มาวางซ้อนกัน 7 อัน หรือเป็นกริดขนาด 7x3 จึงต้องมีรูปแบบคู่สีหนึ่งที่ซ้ำกัน

คู่สีที่ซ้ำกัน 2 คู่นี้เองที่เป็นจุดยอดมุมของสี่เหลี่ยมผืนผ้าที่มีสีเดียวกัน
สำหรับกริดที่มีขนาดใหญ่กว่า 7x3 เราก็พิจาณาเฉพาะกริดขนาดเล็ก 7x3 มาสักตำแหน่งหนึ่ง ก็จะได้สี่เหลี่ยมผืนผ้าตามต้องการ

[warut]

ตัวอย่าง $4\times5$ อันเก่าของผมมีข้อผิดพลาดครับ เนื่องจากยังมี monochromatic rectangle ตามแนวทแยงอยู่ โชคดีไม่มีใครเห็นก่อนผม ลองหาดูนะครับว่าอยู่ไหน

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