Кээде кечки программадагы бир гана суроо (бул учурда урматтуу алып баруучу Кай Пфлаумеден) зыянсыз викториналык финалды кичинекей оптималдаштыруу маселесине айландырууга жетиштүү болот. "Ким эмнени билет?" программасында дал ушундай болот. Негизги суроо: Категория белгилүү, жооп азырынча жок - бирок кайсы натыйжалар дагы эле жакшы экенин коюмдар аныктайт.
Келгиле, эки команданы алалы \(A\) жана \(B\) . Акыркы суроого чейин, \(A\) командасы \(x_a\) суммасын, ал эми \(B\) командасы \(x_b\) суммасын утуп алган. Биз төмөнкү учурду карайбыз
$$
x_a > x_b > 0.
$$
Командалар азыр бүтүн сандарга коюм коюп жатышат.
$$
1 \leq y_a \leq x_a,\qquad 1 \leq y_b \leq x_b.
$$
Эгерде жооп туура болсо, анда коюлган сумма кошулат; эгер жооп туура эмес болсо, ал кемитилет. Төрт мүмкүн болгон натыйжа үчүн төмөнкү акыркы упайлар алынат.:
$$
\begin{array}{c|c|c}
\text{Fall} & A & B\\
\hline
A \text{ richtig}, B \text{ richtig} & x_a+y_a & x_b+y_b\\
A \text{ richtig}, B \text{ falsch} & x_a+y_a & x_b-y_b\\
A \text{ falsch}, B \text{ richtig} & x_a-y_a & x_b+y_b\\
A \text{ falsch}, B \text{ falsch} & x_a-y_a & x_b-y_b
\end{array}
$$
Көрсөтүүдө тең чыгуу баалоо суроосуна алып келет. Ошондуктан, ал матрицада өзүнчө учур катары көрүнүп турат "=". Утуш ыктымалдуулугунун пайыздык маанилери үчүн биз төрт бирдей ыктымалдуулуктагы суб-учурлардагы түз жеңиштерди эсептейбиз. \(|A|B|A|A|\) сыяктуу схема \(A\) командасы үчүн үч түз жеңиш жана \(B\) командасы үчүн бир түз жеңиш берет. Тең чыгуу эки команданын тең жеңиши катары эсептелбейт. Бул так эсептөө абдан маанилүү; жөн гана бүтүндөй уячаны "көк" же "кызыл" деп эсептөө жетишсиз.
Бул моделде төмөнкүдөй божомол камтылган: Биз төрт жооп айкалышын бирдей ыктымалдуулук менен карайбыз. Ошондуктан, бул \(A\) командасы же \(B\) командасы категорияны жакшыраак билеби же жокпу, маанилүү эмес, жооп берүүдөн мурун колдонулган стратегия гана маанилүү.
Келгиле
$$
d=x_a-x_b.
$$
Анда \(d>0\) \(A\) командасынын артыкчылыгы болуп саналат. Эми суроо туулат: оптималдуу коюм канча?
Мүмкүн болгон коюмдардын толук матрицасын динамикалык түрдө эсептесе болот.:
А командасынын көз карашы
Алгач, биз \(A\) командасы качан \(y_a\) жана \(y_b\) белгиленген коюмдар менен утаарын карап чыгабыз.
Иш
$$
A \text{ richtig}, B \text{ falsch}
$$
Ал ар дайым \(A\) командасына өтөт, анткени
$$
x_a+y_a > x_b-y_b
$$
Бул автоматтык түрдө колдонулат, анткени \(x_a>x_b\) жана \(y_a,y_b>0\) .
Калган үч учур үчүн биз алабыз:
$$
\begin{array}{c|c}
\text{Fall} & A \text{ gewinnt genau dann}\\
\hline
A \text{ richtig}, B \text{ richtig} & x_a+y_a>x_b+y_b\\
A \text{ falsch}, B \text{ richtig} & x_a-y_a>x_b+y_b\\
A \text{ falsch}, B \text{ falsch} & x_a-y_a>x_b-y_b
\end{array}
$$
\(x_a=x_b+d\) менен бул төмөнкүдөй болот:
$$
\begin{array}{c|c}
\text{Fall} & A \text{ gewinnt genau dann}\\
\hline
A \text{ richtig}, B \text{ richtig} & d+y_a>y_b\\
A \text{ falsch}, B \text{ richtig} & d-y_a>y_b\\
A \text{ falsch}, B \text{ falsch} & d-y_a>-y_b
\end{array}
$$
Ошентип:
$$
\begin{array}{c|c}
\text{Fall} & A \text{ gewinnt genau dann}\\
\hline
A \text{ richtig}, B \text{ richtig} & y_b<y_a+d\\
A \text{ falsch}, B \text{ richtig} & y_b<d-y_a\\
A \text{ falsch}, B \text{ falsch} & y_b>y_a-d
\end{array}
$$
Саноо ыкмасы азыр абдан маанилүү. Мурда ар бир уячаны анын курамында \(B\) учурга караганда көбүрөөк \(A\) учур бар же жок экендигине жараша гана баалоо азгырылышы мүмкүн эле. Бирок, бул утуп алуу ыктымалдыгын эсептөө үчүн өтө жөнөкөй. Төрт кошумча учурдун өзү бирдей ыктымалдуу окуялар. Ошондуктан, \(|A|B|A|A|\) (A \(A\) үчүн бир жеңиш катары эмес, \(A\) үчүн үч жеңишке жеткен кошумча учур катары эсептелет.
Ошондуктан, \(y_a\) \(A\) биз төрт учурдагы жеке \(A\) жазууларын бардык мүмкүн болгон \(y_b=1,2,\ldots,x_b\) коюмдары боюнча кошобуз.
" \(A\) туура, \(B\) туура эмес" деген учур ар дайым \(A\) командасына өтөт. Бул мурунтан эле \(x_b\) утулган кошумча учурларды берет.
Калган үч учур үчүн төмөнкү сандар келип чыгат.:
$$
\begin{aligned}
N_1(y_a)&=\min(x_b,d+y_a-1),\\
N_3(y_a)&=\min(x_b,\max(0,d-y_a-1)),\\
N_4(y_a)&=\begin{cases}
x_b, & y_a\leq d,\\
\max(0,x_b-y_a+d), & y_a>d.
\end{cases}
\end{aligned}
$$
Бул \(A\) командасы жеңген кошумча учурлардын саны дегенди билдирет
$$
N_A(y_a)=x_b+N_1(y_a)+N_3(y_a)+N_4(y_a).
$$
Тиешелүү утуп алуу ыктымалдыгы
$$
P_A(y_a)=\frac{N_A(y_a)}{4x_b}.
$$
Бул жерде тең чыгуу эсепке алынбагандыктан, \(P_A\) негизги суроону түз утуп алуу ыктымалдуулугуна дал келет (баалоо суроосу жок).
Бул так эсептөө жөнөкөй көпчүлүк клеткаларга салыштырмалуу оптималдуу маанини бир аз жылдырат. \(A\) командасы үчүн төмөнкү оптималдуу колдонуу аймактары келип чыгат.:
$$
\boxed{
\begin{cases}
1\leq y_a\leq2, & x_b=1,\ d=2,\\
d\leq y_a\leq x_b-d+1, & 2d\leq x_b+1,\\
1\leq y_a\leq d, & 2d=x_b+2,\\
1\leq y_a\leq \max(1,x_b-d+1,d-x_b-1), & 2d>x_b+2.
\end{cases}
}
$$
Бул аймактагы бардык коюмдар \(A\) командасынын утуп алуу ыктымалдыгын жогорулатат. Эгер сиз бирдей жакшы коюмдардын ичинен мүмкүн болушунча чоң сумманы койгуңуз келсе, ар дайым аймактын оң четин колдонушуңуз керек.
Мисал:
$$
x_a=30,\qquad x_b=22.
$$
Андан кийин
$$
d=x_a-x_b=8.
$$
Ал жерде
$$
2d=16\leq 23=x_b+1
$$
Оптималдуу диапазон колдонулат.
$$
8\leq y_a\leq 15.
$$
Ошондуктан, эң оптималдуу колдонуу
$$
\boxed{y_a=15}.
$$
Бүтүндөй клеткаларды кароонун эски ыкмасы \(9\leq y_a\leq 14\) диапазонун сунуштамак. Учурлардын жарым-жартылай саны \(8\) жана \(15\) эки чек ара маанисинин да оптималдуу экенин так көрсөтөт.
В командасынын көз карашы
Эми биз ушул эле кырдаалды артта калган \(B\) командасынын көз карашынан карайбыз. Бул жерде дагы биз мындан ары бүтүндөй уячаларды гана эмес, төрт подкейстеги жеке \(B\) жазууларын эсептейбиз.
Иш
$$
A \text{ richtig}, B \text{ falsch}
$$
\(B\) командасы ар дайым утулат. Калган үч учурда, \(B\) командасы бардык мүмкүн болгон \(y_a=1,2,\ldots,x_a\) суммаланганда \(y_b\) белгиленген коюму үчүн утулган кошумча учурлардын төмөнкү санын алат.:
$$
\begin{aligned}
M_1(y_b)&=\max(0,y_b-d-1),\\
M_3(y_b)&=x_a-\max(0,d-y_b),\\
M_4(y_b)&=\max(0,x_b-y_b).
\end{aligned}
$$
Ошондой
$$
N_B(y_b)=M_1(y_b)+M_3(y_b)+M_4(y_b)
$$
жана ага байланыштуу утуп алуу ыктымалдыгы
$$
P_B(y_b)=\frac{N_B(y_b)}{4x_a}.
$$
\(y_b\leq d\) үчүн бул жөнөкөйлөштүрүлөт
$$
N_B(y_b)=2x_b.
$$
\(y_b>d\) үчүн бирөө гана алат
$$
N_B(y_b)=2x_b-1.
$$
Бул \(B\)
$$
\boxed{
1\leq y_b\leq \min(d,x_b).
}
$$
Бул крудер клеткасынын көпчүлүк ыкмасына салыштырмалуу маанилүү оңдоо: \(B\) командасы үчүн оптималдуу коюм сөзсүз түрдө бирден-бир \(1\) эмес. Мисалы, эгер \(A\) командасы \(d=8\) менен алдыда болсо жана \(B\) командасы эң көп дегенде \(22\) коюм коё алса, анда \(B\) үчүн бардык коюмдар утуп алуу ыктымалдыгы боюнча оптималдуу болот.:
$$
1\leq y_b\leq 8.
$$
Интуиция окшош бойдон калууда: артта калган команда өтө көп коюмдарды койбошу керек. Ашыкча көп коюмдар жеке сценарийлерди жакшыртса, башкаларын начарлатат. \(y_b\) \(d\) кемчилигинен ашып кеткенде, \(B\) командасы жалпысынан бир сценарийди утулуп калат. Ошондуктан, алдыңкы команда атаандашынын бардык мүмкүн болгон коюмдары боюнча мүмкүн болушунча көп жеке сценарийлерди утуп ала тургандай кылып коюмдарды коёт.
Куугунчу сөзсүз түрдө так бир евро койбойт, бирок эң көп дегенде тартыштыктын суммасына чейин коюм коёт. Ошентип, негизги суроо оюн теориясынын жөнөкөй көрүнгөн викторина эрежесинде канчалык көп камтылганынын жакшы мисалы болуп саналат: маанилүүсү кайсы уяча көк же кызыл болуп бүтөөрү гана эмес, ошол уячанын ичиндеги төрт кошумча учурдун канчасы чындыгында утуп алынганы.