70 lines
2.9 KiB
Markdown
70 lines
2.9 KiB
Markdown
---
|
||
id: 5900f4e51000cf542c50fff7
|
||
title: 'Задача 376: Нетранзитивні набори кубиків'
|
||
challengeType: 5
|
||
forumTopicId: 302038
|
||
dashedName: problem-376-nontransitive-sets-of-dice
|
||
---
|
||
|
||
# --description--
|
||
|
||
Розглянемо такий набір кубиків з нетиповою розміткою:
|
||
|
||
$$\begin{array}{} \text{Die A: } & 1 & 4 & 4 & 4 & 4 & 4 \\\\
|
||
\text{Die B: } & 2 & 2 & 2 & 5 & 5 & 5 \\\\ \text{Die C: } & 3 & 3 & 3 & 3 & 3 & 6 \\\\
|
||
\end{array}$$
|
||
|
||
За правилами гри, двоє гравців по черзі підкидують гральний кубик. Переможцем стає той, чий кубик показав найвище значення.
|
||
|
||
Якщо перший гравець обере кубик $A$, а другий $B$, тоді ми отримуємо
|
||
|
||
$P(\text{second player wins}) = \frac{7}{12} > \frac{1}{2}$
|
||
|
||
Якщо перший гравець обере кубик $B$, а другий $C$, ми отримуємо
|
||
|
||
$P(\text{second player wins}) = \frac{7}{12} > \frac{1}{2}$
|
||
|
||
Якщо перший гравець обере кубик $C$, а другий $A$, ми отримуємо
|
||
|
||
$P(\text{second player wins}) = \frac{25}{36} > \frac{1}{2}$
|
||
|
||
Отже, який би кубик не обрав перший гравець, другий може обрати інший кубик і його шанс перемогти становитиме більше 50%. Набір кубиків, що має таку властивість, називається нетранзитивним.
|
||
|
||
Ми хочемо дослідити, яка загальна кількість нетранзитивних наборів кубиків. Візьмемо до уваги такі умови:
|
||
|
||
- Існує 3 шестисторонні кубики, на кожній грані якого розташовано від 1 до $N$ точок включно.
|
||
- Кубики з однаковими наборами точок є рівними, незалежно від того, на якій стороні розташовані ці точки.
|
||
- Однакове значення точок може з'являтись на декількох кубиках; якщо обом гравцями випаде однакове значення точок, жоден із гравців не переміг.
|
||
- Набори кубиків $\\{A, B, C\\}$, $\\{B, C, A\\}$ і $\\{C, A, B\\}$ є рівними.
|
||
|
||
For $N = 7$ існує 9780 таких наборів.
|
||
|
||
Скільки їх існує для $N = 30$?
|
||
|
||
# --hints--
|
||
|
||
`nontransitiveSetsOfDice()` має повернути `973059630185670`.
|
||
|
||
```js
|
||
assert.strictEqual(nontransitiveSetsOfDice(), 973059630185670);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function nontransitiveSetsOfDice() {
|
||
|
||
return true;
|
||
}
|
||
|
||
nontransitiveSetsOfDice();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|