Combinatorics Marathon
 

ตามคำแนะนำของน้อง dektep ... I shall commence another marathon thread :)

กติกาก็เหมือนกระทู้มาราธอนอื่นๆ คือ ใครตอบคำถามข้อก่อนหน้าได้ มีสิทธิ์ตั้งโจทย์ข้อถัดไปครับ
ขอเชิญชวนเหล่าจอมยุทธ์ทั้งหลายร่วมแสดงพลังยุทธ์คอมบินาทอริกได้เลยครับ

ข้อแรก โดยน้อง dektep ครับ

ขอเป็นโจทย์ง่าย ๆ แล้วกันครับ
1. จงหาจำนวนวิธีในการเลือกจำนวน 5 จำนวนที่แตกต่างกันจากเซต $\left\{\,1,2,\dots,18\right\}$ โดยที่ผลต่างของสองจำนวนใด ๆ ที่เลือกมามีค่าอย่างน้อย 2

ทำประมาณนี้ได้ไหมอะโจทย์สมนัยกับการจัดเรียง x จำนวน 5 ตัวจาก y จำนวน 13 ตัวโดยที่ x ต้องไม่ติดกันก็มีจำนวนวิธีเรียงโดยที่ไม่มี x 2 ตัวใดๆเรียงติดกันก็เหมือนการเลือกช่องว่าง 5 ช่องจากช่องว่าง 14 ช่อง ก็ $\binom{14}{5} $ (ผมไม่ค่อยเก่งคอมบินะ T_T)

ยังไม่ถูกต้องครับ

ถูกต้องแล้วครับ :great:
เชิญตั้งข้อต่อไปได้ครับ

น้อง dektep ไม่ต้องบอกนะครับว่าเอาโจทย์มาจากไหน :) ผมค่อนข้างอ่อนคอมบิยังไงก็เอาโจทย์มาให้ฝึกหน่อยนะครับ

ผมก็ไม่รู้หรอกครับว่าโจทย์อะไร :D
วิธีทำ
พิจารณากล่อง $1,2,...,n+k$
ให้ $A_i$ คือเซตของการแจกของ $a_1,a_2,...,a_n$ ลงในกล่องโดยกล่องที่ห้ามใส่ของลงในกล่องที่ $i$ และ $i=1,2,...,n$
พิจารณา $|{A_1}' \cap {A_2}' \cap ... {A_n}'| = |U|-|A_1 \cup A_2 \cup ... \cup A_n|$
โดย $PIE$ จะได้ว่า $|U|-|A_1 \cup A_2 \cup ... \cup A_n|=(n+k)^n-\binom{n}{1}(n+k-1)^n-...+(-1)^n\binom{n}{n}k^n$
โดยการนับแบบที่สอง พิจารณาว่า ${A_1}' \cap {A_2}' \cap ... {A_n}'$ คือวิธีแจกของต่าง $a_1,...,a_n$ ลงใน $n$ กล่องแตกต่างกัน
ซึ่งทำได้ $n!$ วิธี
เนื่องจากการนับทั้งสองทางต้องมีค่าเท่ากันดังนั้น $(n+k)^n-\binom{n}{1}(n+k-1)^n-...+(-1)^n\binom{n}{n}k^n = n!$

ต่อเลยนะครับ
3.จงหาจำนวนวิธีในการเลือกสองจำนวนที่ติดกันใน $\left\{\,\right. 1000,1001,...,2000\left.\,\right\}$ โดยเมื่อบวกสองจำนวนที่เลือกมาแล้วจะไม่มีการทดในหลืกใด ๆ

ผมได้ 151 อะครับ...
ประมาณว่าหลักแรกผมไม่สนแล้วหลักที่สองสามสี่ก็ 01234 ตามลำดับเลยเปลี่ยนไงก็ได้อย่างผมใช้ 1342 อีกตัวก็เป็น 1343 อะครับซึ่งยังไงๆมันก็ไม่ซ้ำกันอยู่แล้วเพราะ 1343 ก็เป็น1344 ได้ $125$ วิธีแล้วอีกแบบคือหลักร้อยเป็น 01234 แล้วหลัก 10 ก็เป็นได้ตั้งแต่ 0 ถึง 4 มี 5 แบบแล้วหลักหน่วยให้เป็น 9 อะครับ อย่าง 1449 อีกตัวก็ 1450 อะไรประมาณนี้อะครับก็มีอีก 25 วิธีอ่า ส่วนตัวผมคิดว่าถูกนะ T_T แล้วมันมี 1999 กับ 2000 อีก 1 ตัว

Ps.ตะกี๊อ่อ 5 คูณ 5 คูณ 5 ของผมได้ 215 ครับอย่าไปใส่ใจ -*- คืนนี้ผมบวกกับคูณเลขผิดครับ Edit ครั้งที่ 9 หวังว่าคงเป็นครั้งสุดท้าย

ยังไม่ถูกนะครับ
ปล.ข้อ2.พี่ RoSe-JoKer ใช้วิธีไหนครับ

ผมได้ $126$ วิธีครับ
เริ่มจากพิจารณาแค่ ${1000,1001,...,1999}$ ก่อน
จะได้ว่ามันอยู่ในรูป $1abc$ (ไม่ใช่ผลคูณนะครับ เป็นเลข 4 หลัก) กับ $1ab(c+1)$ (เลข 4 หลัก)
จะได้ว่าผลบวกของ 2 จำนวนเท่ากับ $2(2a)(2b)(2c+1)$ (เลข 4 หลัก)
$\therefore 2a\leq\ 8, 2b\leq\ 8, 2c+1\leq\ 9$
$\therefore a=0,1,2,3,4, b=0,1,2,3,4, c=0,1,2,3,4$
ได้ $125$ วิธี
คราวนี้ถ้ามี 2000 ได้ว่า คู่ $1999$ กับ $2000$ ใช้ได้
ดังนั้นมี $126$ คู่

ตอนแรกเห็นโจทย์เป็น "เลือก 2 จำนวนใดๆ" ก็เลยนั่งงงไปเลย... :)

ถูกต้องเเล้วครับ
เชิญตั้งข้อต่อไปเลยครับ :great:

ผมสงสัยว่า อย่าง 1249 กับ 1250 นิไม่ได้หรอครับ c=9 - -* ช่วยชี้แนะทีครับ

4.(easy)Let M be a subset of {1,2,3,...,2006} with the following property:For any three elements $x$,$y$ and $z$($x<y<z$) of M,$x+y$ does not divide $z$.Determine the largest
possible size of M
5.(hard,BMO1985)On a conference 1985 people take apart.In every group of three prople
at least two speak the same languages,prove that there exist 200 people on the conference
which all speak the same language
:)Hint for problem5
1.Graph theory
2.Extheme Principle

:cry:ผมคิดว่าผมคิดผิดแหละครับ... ถ้างั้นก็ควรจะตอบ 225 คู่ครับ...

ทำไมมันเยอะจังอะครับ