รบกวนรังนกหน่อยครับ ผมว่ามันยากมากๆเลย

[polsk133]

ในการสร้างห้องแล็บแห่งหนึ่งที่มีห้องวิจัยย่อย 15 ห้องและมีเครื่องเซิฟเวอร์ 10 เครื่อง โดยในช่วงเวลาหนึ่งเครื่องเซิฟเวอร์แต่ละเครื่องจะถูกใช้ได้จากห้องวิจัยย่อยเพียง 1 ห้องเท่านั้น จะต้องมีการเดินสายระหว่างห้องวิจัยกับเครื่องเซิฟเวอร์อย่างน้อยที่สุดกี่สายจึงจะมั่นใจได้ว่า เมื่อมีการใช้ห้องวิจัยไม่เกิน10ห้อง แต่ละห้องจะสามารถเข้าใช้เครื่องเซิฟเวอร์ได้

โจทย์ยาวหน่อยนะครับ IDEA มันคืออะไรครับข้อนี้ แล้วเขียนอย่างไรจึงจะได้คะแนนเต็ม

[กระบี่ทะลวงด่าน]

เหมือนกับเป็นโจทย์ที่อาจารย์สอนในค่ายนะครับ

ลองวาดรูปดูเเล้วพิจารณาหลายๆรูปสิครับเเล้วนำความสัมพันธ์มาเชื่อมกันครับ

[nongtum]

โจทย์นี้ อ. เอามาจากหนังสือ combi ของ Tucker แน่ๆ

ใช้รังนกแบบปรับปรุงนิดหน่อย กับใช้ข้อขัดแย้งช่วย รวดเดียวออก ตอบ 60 ครับ

[polsk133]

รบกวนเขียน Sol ให้ทีสิครับ ผมคิดไม่ออกจริงๆ

[nongtum]

Hint?

Let $S_i, 1\le i\le 10$ be the set of servers and $W_j, 1\le j\le 15$ be the set of workstations.
Connect $W_k$ to $S_k$ for $1\le k\le 10.$ Then connect $W_k$ for $11\le k\le 15$ to $S_i,1\le i\le 10.$
Clearly, one requires 60 cables. Assume that there are fewer than 60 connections between workstations and servers.
Hence some servers would be connected to at most $\lfloor \frac{59}{10}\rfloor =5$ workstations.
Thus, the remaining 9 servers are not enough to allow the other 10 workstations to simultaneously access different servers.

[polsk133]

แล้วเรามั่นใจได้หรอครับว่า59สายที่ทำไม่ได้นั้นเราต่อแบบดีที่สุดแล้ว
ยังงงตรง59สายอะครับ

[Thgx0312555]

#6 คุณ nongtum แสดงให้ดูแล้วว่าต้องมีอย่างน้อย 60 สาย แต่ที่ผมสงสัยคือต้องแสดงอีกว่า 60 สายนั้นเป็นไปได้ใช่ไหมครับ ซึ่งตรงนี้ไม่รู้จะแสดงยังไงครับ ช่วย Hint เพิ่มหน่อยครับ

[artty60]

สมมติให้เครื่องservers10เครื่องเป็น$1, 2, 3, 4, 5, 6, 7, 8, 9,10$

ห้องวิจัย15ห้องเป็น $A, B, C, D, E, F, G, H, I, J, K, L, M, N, O$

วิธีคือ ให้ต่อสาย10ห้องใดๆกับเครื่อง servers เต็ม10 ห้องก่อน 10 ห้องก็ใช้ 10 สาย

ที่เหลือ 5 ห้องก็ต่อสายห้องละ 10 สายกับเครื่อง servers ทั้ง 10 เครื่อง 5ห้องก็เป็น 50 สาย

เพราะฉะนั้นใช้สายทั้งหมดอย่างน้อย $=10+50=60$ สาย

[polsk133]

Hence some servers would be connected to at most 5 workstations.

แล้วสรุปได้อย่างไรว่าได้9ห้องหรอครับ

[Thgx0312555]

แต่ละ server ต้องมีอย่างน้อย 6 ห้องที่ต่อ
เพราะถ้ามี server A ต่อน้อยกว่า 6 ห้อง จะมีห้องที่ไม่ได้ต่อมากกว่าหรือเท่ากับ 10 ห้อง

เลือกห้องวิจัยที่ไม่ได้ต่อมา 10 ห้อง จะไม่มีห้องใดต่อกับ server A เลย อีก 9 servers ที่เหลือจึงไม่เพียงพอต่อการต่อสายจึงเกิดข้อขัดแย้งครับ

[polsk133]

อ่อ ขอบคุณมากครับ

แล้วก็ขอแสดงความยินดีกับคุณ Thgx0312555 ที่ได้ สพฐ เหรียญทองครับ

[Thgx0312555]

ขอบคุณครับ

[artty60]

#10 ผมว่า idea ถูกต้องแล้วครับที่ servers แต่ละเครื่องจะต้องต่อกับห้องวิจัยอย่างน้อย 6 ห้องใดๆ
แต่คำอธิบายแบบ hint ของคุณnongtumจะชัดเจนกว่านะครับ ไม่งง

[kongp]

แสดงว่าไม่เจอหนังสือดี โชคร้ายจัง

[artty60]

จริงๆแล้วตกลงข้อนี้เฉลยเป็นยังไงครับ

เพราะไปคิดดูแล้วถ้า 60 สายนี่เวลาใช้งานจริงๆอาจทำให้บางช่วงเวลาแต่ละห้องวิจัยใดๆ

อาจใช้เครื่องเซิฟเวอร์ไม่ได้เพราะไม่ได้ต่อสายกับเซิฟเวอร์เครื่องที่ว่างอยู่นั้น

จะต้องไปใช้ห้องวิจัยที่ว่างอยู่และได้ต่อเชื่อมกับเครื่องเซิฟเวอร์ที่ว่างนั้น ก็จะขัดกับโจทย์

ที่ว่าถ้ามีห้องวิจัยใช้เครื่องเซิฟเวอร์ไม่เกิน 10 ห้อง ห้องใดๆจะเข้าใช้เครื่องเซิฟเวอร์ที่ว่านั้นได้

หรือไม่ก็ต้องswitchสายซึ่งอาจทำให้การใช้งานเครื่องเซิฟเวอร์(ที่สำคัญมากๆ)ของบางห้องวิจัยต้องถูกรบกวนหรือขาดช่วง

หรือว่าผมตีโจทย์ผิด หรือคิดมากไป

ผมจึงอยากรู้คำอธิบายของเฉลยจริงๆข้อนี้ครับ