OPINION by David Ginat,
Tel-Aviv University COLORFUL CHALLENGES
The current column involves challenges of different types. The new chal- lenge requires the development of
winning strategies for two-player games.
The better way to develop and verify the
strategies is to devise invariant assertions,
which will show that the winner always has
a suitable reply to each of her opponent’s
moves (until winning). The previous challenge underlines the importance of careful
examination of diverse input examples,
together with inductive progression and
recognition of hidden patterns.
Two players play the following game.
Given a line of N empty cells (N>100), each
player, in her turn, writes the letter D or
the letter V in an empty cell. The player
who obtains the sequence DVD first (in
three consecutive cells) wins the game.
(The sequence may involve letters that any
of the players wrote.) Although a draw is
possible (no DVD in the end), one of the
players has a winning strategy. 1. What
would the winner’s strategy be? 2. Answer
the question when the goal is to obtain the
A fence of N columns is made of a total
of N·H tiles. The height (number of tiles)
of each column is an integer. One wants
to “level” the fence, so that the height of
each column will be exactly H. In order to
do that, it is allowed to transfer blocks of
one or more tiles between neighboring
columns. Thus, a block transfer may be to
the adjacent column on the left or to the
adjacent column on the right. Different
transfers may involve different amounts
of tiles, and transfers between neighbor-
ing columns may be repeated. Given the
heights of the N columns, output the min-
imal number of block transfers necessary
for obtaining the goal. Answer first the
case where the fence is linear, and then—
the case where the fence is circular.
For example, for the fence whose column heights are 7 1 8 4 5 the minimal
number of block transfers is 3 (in both cases), as we may transfer a 2-tile block from
the 7 to the 1, a 2-tile block from the 8 to
the 1, and a 1-tile block from the 8 to the 4.
At first glance, the challenge may seem
confusing, as tiles may be transferred in
both directions. Some problem solvers
suggest to focus on the tallest columns,
and to calculate the amounts of tiles that
should be taken from them and transferred
to the left and to the right. Those who
follow this train of thought try to explicitly tell the amounts and directions of the
block transfers. But their transfer rules
are not clear. Others offer “not to touch
the columns that are initially in the right
height H”. This is possible in the example
of the problem statement; but it is easy
to see that it is not always suitable for the
linear case (e.g., 6 5 4). A sound pattern
In trying several examples, in which
we “pass” over the columns from left to
right, starting at the leftmost one, we may
notice that we will eventually reach a point
in which the total sum of the first S tiles is
S·H. This point will surely be at the end of
the sequence, but possibly much earlier. An
examination of the first such point shows
that these S columns can be “leveled”
autonomously. Block transfers inside this
sub-sequence of columns may be in both
directions, and the total number of transfers
for leveling this sub-sequence is exactly S- 1.
No shorter sub-sequence that starts at the
leftmost column may be leveled autonomously, as such a sub-sequence contains
either too many or too few tiles.
The number of tiles in the remaining
columns is (N-S)·H. We may proceed
inductively, and seek the next autonomous sub-sequence, that starts at the S+ 1
column. Notice that no transfer is required
between the S and the S+ 1 columns. This
greedy, inductive process may be continued until reaching the right-end. Every
“border” between two adjacent autonomous sub-sequences requires no transfer.
In order to obtain the minimal number of transfers, we want the maximal
number of autonomous sub-sequences.
The leftmost autonomous sub-sequence
is the shortest possible for the leftmost
column. So is the one that starts with the
next column, and so on. Thus, the solution
for the linear case, in which the fence has a
left-end and a right-end, may be summarized in the following two assertions.
1. The min number of block transfers is
N-A, where A is the max number of
autonomous sub-sequences of columns.