hard combinatorics

[dektep]

1.A 2004 x 2004 array of points is drawn.Find the largest interger n such that it is possible to draw a convex n-sided polygon whose vertices lie on the points of the array
2. The transportation ministry has just decided to pay 80 companies to repair 2400 roads. These roads connects 100 cities.Each road is between two cities and there is at most one road between any two cities.Each company must repair exactly 30 roads,and each road is repaired by exactly one company.For a company to repair a road,it is necessary for the company to set up stations at the both cities on its endpoints.Prove that there are at least 8 companies stationed at one city.

[putmusic]

อ่านไม่รู้เรื่องครับ

[konkoonJAi]

นิยาม convex ให้หน่อยนะคะ จำไม่ได้ค่ะ

[dektep]

2.Solution: For each company, it is easy to see that it repairs at least 9 cities as K8 contains only 28 lines. So there are at least 720 different stations. By the PigeonHole Theory, it is easy to see that at least 8 companies stationed at one city. We are done.

[dektep]

convex n-sided polygon = รูป n เหลี่ยมนูน

[tatari/nightmare]

ขอมาเพิ่มโจทย์ให้ครับ(เป็นENGLISH ด้วยนะครับ)
1.Find the number of permutation $(p_{1},....,p_{6})$of $1,2....,6$ such that for any $k,1\leq k\leq5$ and $(p_1,...p_k)$ does not form a permutation of $1,2,...k$
2.For each interger $n\geq 3$,find the number of ways in which one can place the numbers $1,2,...,n^2$ in the square of nxn chessboard (one on each)such that the numbers in each row and in each column form an arithmetic progression
3.Some 46 unit square of a 9x9 board are colored red.Show that there exists a 2x2 square
containing at least three red unit square
4.Prove that among any 181 perfect square there exists 19 whose sum is divisible by 19(use a little of number)

[nongtum]

ข้อ 4 ใน #6
มีแค่ี $\bar{n}\in\{0,1,4,5,6,7,9,11,16,17,18\}$ ที่เป็น quadratic residue modulo 19
โดย pigeonhole principle เราจะสามารถเลือกจำนวนจัตุรัสมา 19 จำนวนที่มีเศษใน mod 19 เหมือนกันมาได้ และผลรวมก็จะหารด้วย 19 ลงตัวตามที่ต้องการ ##

[Aermig]

คุณ dektep ช่วยแสดงข้อ 2 ให้ละเอียดกว่านี้ได้มั๊ยครับ
แล้วก็ คือผมว่าคุณ konkoonJAi เค้าไม่ได้ถาม"คำแปล"ของ n-sided polygon แต่เค้าถามถึงนิยามต่างหากครับ(ผมก็อยากรู้เหมือนกัน) เอาภาษาไทยหรืออังกฤษก็ได้ครับ

[dektep]

convex n side polygon คือ รูป n เหลี่ยมที่มุมแต่ละมุมไม่เกิน 180 องศาครับ

[nooonuii]

ความหมายโดยทั่วไปของ convex set คือ เซตซึ่งจุดสองจุดใดๆสามารถเชื่อมต่อด้วยส่วนของเส้นตรงที่ลากผ่านเซตนั้นได้

จะเห็นว่ารูปหลายเหลี่ยมที่มีมุมบางมุมเป็นมุมกลับจะไม่เป็น convex set ครับ