MathDB

Bowling Pins is a game played between two players in the following way: We start with

14

bowling pins in a line:
X X X X X X X X X X X X X X
Players alternate turns. On each turn, the player can knock down one, two or three consecutive pins at a time. For example:
Jing Jing bowls:
X X \:\:\:\: X X X X X X X X X X
Soumya bowls:
X X \:\:\:\: X X X X X X X X X
Jing Jing bowls again:
X X \:\:\:\: X X X X X \:\: X
The player who knocks down the last pin wins. In the above game, it is Soumya’s turn. If he plays perfectly from here, he has a winning strategy (In fact, he has four diﬀerent winning moves.) Imagine it’s Jing Jing’s turn to play and the game looks as follows
X \:\: X\dots
with 1 X on the left and a string of

k

consecutive X’s on the right. For what values of

k

from

1

10

does she have a winning strategy?

A permutation of a set is a bijection from the set to itself. For example, if

\sigma

is the permutation

1 7\mapsto 3

2 \mapsto 1

, and

3 \mapsto 2

, and we apply it to the ordered triplet

(1, 2, 3)

, we get the reordered triplet

(3, 1, 2)

. Let

\sigma

be a permutation of the set

\{1, ... , n\}

. Let

\theta_k(m) = \begin{cases} m + 1 & \text{for} \,\, m < k\\ 1 & \text{for} \,\, m = k\\ m & \text{for} \,\, m > k\end{cases}

Call a finite sequence

\{a_i\}^{j}_{i=1}

a disentanglement of

\sigma

\theta_{a_j} \circ ...\circ \theta_{a_j} \circ \sigma

is the identity permutation. For example, when

\sigma = (3, 2, 1)

, then

\{2, 3\}

is a disentaglement of

\sigma

. Let

f(\sigma)

denote the minimum number

k

such that there is a disentanglement of

\sigma

of length

k

. Let

g(n)

be the expected value for

f(\sigma)

\sigma

is a random permutation of

\{1, ... , n\}

. What is

g(6)

9

Problems(2)