دو نفر با هم بازی می‌کنند. در ابتدا یک گراف ‎$2n$-رأسی با رئوس ‎$v_1‎, ‎v_2‎, ‎\ldots‎, ‎v_{2n}$‎ داریم که هیچ یالی ندارد. در هر مرحله، نفر نخست یک یال به گراف اضافه می‌کند، طوری که دور ایجاد نشود؛ سپس نفر دوم به هر رأسی که عددی ندارد و درجه‌ی آن نیز صفر نیست، یک عدد از مجموعه‌ی ‎$A=\{2^1‎, ‎2^2‎, ‎\ldots‎, ‎2^{2n}\}$‎ نسبت می‌دهد. پس از ‎$2n-1$‎ مرحله، بازی تمام می‌شود و یک درخت ساخته می‌شود. نفر دوم باید طوری بازی کند که در انتها، هر عدد مجموعه‌ی ‎$A$‎، دقیقا به یک رأس نسبت داده شده باشد.

فرض کنید پس از پایان بازی، رأس ‎$v_i$‎، درجه‌ی ‎$d_i$‎ داشته باشد و عدد نسبت داده شده به آن، ‎$a_i$‎ باشد. امتیاز هر یال ‎$v_iv_j$‎ را برابر ‎$a_i+a_j$‎ در نظر می‌گیریم. جمع امتیاز یال‌ها در پایان بازی را ‎$f(n)$‎ می‌نامیم. به عبارتی دیگر، ‎ $$\begin{equation*}‎ ‎f(n)=\sum_{i=1}^{2n}d_i\times{}a_i‎ ‎\end{equation*}$$ ‎ است. نفر نخست می‌خواهد ‎$f(n)$‎ کمینه شود و نفر دوم می‌خواهد ‎$f(n)$‎ بیشینه شود. فرض کنید هر دو بازی‌کن، به‌ترین بازی ممکن را انجام دهند. ثابت کنید: ‎ $$\begin{equation*}‎ ‎f(n)=\frac{2^{2n+3}-8}{3}+2n-4‎ ‎\end{equation*}$$ ‎

• سوال بعد
• سوال قبل