المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۴:سوال ۱

سوال 1

$n$ گلوله با وزن‌های متفاوت و یک ترازوی دوکفه‌ای بدون وزنه داده شده است. نشان دهید که با حداکثر $\lceil \frac{3n}2 - 2 \rceil$ بار وزن کردن می‌توان سبک‌ترین و سنگین‌ترین گلوله‌ها را مشخص کرد. روش وزن کردن خود را به دقت توضیح دهید و فرمول فوق را برای کلیه‌ی مقادیر $n$ اثبات کنید. (منظور از $\lceil x \rceil$ _بخوانید سقف $x$ _ کوچک‌ترین عدد صحیح بزرگ‌تر یا مساوی $x$ است.)


ابزار صفحه