Loading [MathJax]/jax/output/HTML-CSS/jax.js

سوال ۳۱

می‌خواهیم به هر کدام از نقطه‌های توپر در شکل مقابل٬ یکی از اعداد ۱ تا k را تخصیص دهیم به طوری که هر مسیری که دو نقطه با شماره‌های یکسان i را به هم وصل می‌کند٬ از حداقل یک نقطه با شماره‌ی بیش‌تر از i عبور کند. کم‌ترین مقدار k چه قدر است؟

  1. ۲
  2. ۳
  3. ۴
  4. ۵
  5. ۶

پاسخ

گزینه (۳) درست است.

بهترین حالت ممکن به شکل زیر می‌باشد: