Ми намагаємось знайти приховане число, вибране з набору цілих чисел {1, 2, ..., $n$}, задаючи питання. На кожне поставлене нами число (питання) ми отримуємо одну з трьох можливих відповідей:
- "Ваше припущення нижче за приховане число" (і ви підпадаєте під вартість а), або
- "Ваше припущення вище, ніж приховане число" (і ви підпадаєте під вартість b) або
- "Так, це воно!" (ігра закінчується).
Враховуючи значення $n$, $a$, і $b$, оптимальна стратегія мінімізує загальні витрати <u>на найгірший з можливих випадків</u>.
Наприклад, якщо $n = 5$, $a = 2$, та $b = 3$, тоді ми можемо задати "<strong>2</strong>" як наше перше питання.
Якщо нам кажуть, що 2 більше, ніж приховане число (для вартості $b = 3$), тоді ми впевнені, що "<strong>1</strong>" - це приховане число (для загальної вартості <strong><spanstyle="color: blue;">3</span></strong>).
Якщо нам кажуть, що 2 менше, ніж приховане число (для вартості $a = 2$), тоді наше наступне запитання буде "<strong>4</strong>".
Якщо нам кажуть, що 4 більше, ніж приховане число (для вартості $b = 3$), тоді ми впевнені, що "<strong>3</strong>" - це приховане число (для загальної вартості $2 + 3 = \color{blue}{\mathbf{5}}$).
Якщо нам кажуть, що 4 менше, ніж приховане число (для вартості $a = 2$), тоді ми впевнені, що "<strong>5</strong>" - це приховане число (для загальної вартості $2 + 2 = \color{blue}{\mathbf{4}}$).
Таким чином, найгірша вартість досягнута цією стратегією, - <strong><spanstyle="color: red">5</span></strong>. Також можна показати, що це найнижча найгірша вартість, яку можна досягти. Так, насправді, ми щойно описали оптимальну стратегію для заданих значень $n$, $a$і $b$.
Нехай $C(n, a, b)$ буде найгіршою вартістю, досягнутою оптимальною стратегією для заданих значень $n$, $a$та $b$.
