Soldiers in the Parade Ground

Question

Twenty-five soldiers are standing in a parade ground consisting of a five-by-five grid of large concrete slabs, laid out in a neat north-to-south, east-to-west square array. Each soldier is standing on his own slab, but there's space for more than one on the same slab.

Their sergeant yells an order, and each soldier moves north, south, east, or west onto one of the slabs directly adjacent to them.

After this operation, how many slabs at most can be empty?

_{Inspired by a problem from the Dutch Junior Mathematical Olympiad.}

Answer 1

The soldiers starting on the slabs marked with an x must all end up at different slabs. Therefore, there will be at least 9 occupied slabs and therefore at most 16 empty slabs.

One solution involves every soldier ending up on one of the slabs marked O. Notice that every slab is adjacent to some O, so this is possible.

x . . x x   . O O . .
x . . . .   . . . . O 
. . x . .   O . . . O
. . . . x   O . O . .
x x . . x   . . O O .

Answer 2

Basically, the insight to make this problem easier is:

To view the board as a checkerboard.

Therefore we can see that:

The soldier who stands on white slab will always move to black slab, and
the soldier who stands on black slab will always move to white slab.

Now, let's divide them into to parts. The first part is:

The soldier on white slab.



It is simple to prove (by observation a.k.a. instinct) that we can "squeeze" them into 4 slabs, denoted by red mark of x.

Then, move to the second part:

The soldier on black slab.



This one is a bit tricky, but I think we can squeeze them into 5 slabs as below. Note that only one of four green x is required (as destination of the center soldier).

So, combining them:

We can squeeze all the soldiers into (4+5) slabs which means there are 25 - (4+5) = 16 empty slabs at most.

Answer 3

Improved things a bit. My new answer is...

16. Take this board...
X X O O O
O O O X X
O O O O O
X X X O X
O O O O X
If all soldiers on the Os moved to an X, and all soldiers on an X moved to an adjacent X, then 16 spots are left open.

Old answer was...

15. Consider the series of columns running North to South. If the West-most one all moved East, the center moved East, and the East-most one moved West, then they would all be occupying the even columns. If soldiers on the even columns moved only North or South (i.e. all North except for the ones in the North-most spots, who, move South), then they would end on already occupied spots, leaving the odd columns, totaling 15 slabs, still open.

Answer 4

My first guess would be

16

on my first try.

I have used just my intuitions

Here is a gif type answer, o's are soldiers, and after they move a one stop, they become red.

http://gph.is/2GxKAh5

Probably there is a better answer :)

Answer 5

First I'll just assume that

All soldiers on the edges can move off, leaving at least 16 spots blank and 9 soldiers left in the resulting 3x3 square

Then (assuming everyone has to move at least once)

The middle row of remaining soldiers moves up, the top row moves down, and the bottom row moves up. The middle row which moved up is still on their own, but the previously top and bottom rows now rendezvous in the middle row. This leaves only 2 rows of 3 slabs, meaning only 6 slabs are occupied.

So my answer is

19 slabs at most can be empty

Answer 6

I got:

17

by using this board:

Answer 7

First off:

A slab can be populated by at most 4 soldiers, so roughly 25/4=6 (app.) + 1 = 7 slabs are full at least.

Is it conclusive?

Let's paint the grid black and white with the upper-left slab being white. At first there's 12 soldiers on black slabs and the remaining 13 are on white slabs. Then they move to the opposite color, allowing 13 of them to be on black slabs and 12 on the white ones. Two back-to-back same-color slabs can't both be populated by 4 soldiers, because the slabs adjacent to both can only "give" a soldier to one of these neighbours.

If there's a 4-strong black slab at all, the black inner slabs diagonally neighbouring it can't have more than 2 soldiers, and the remaining black inner slab can have 3 soldiers at most. 4+3+2+2=11, meaning there's at least one black slab left. Likewise, there can't be more than 2 3-strong black slabs if there's a 4-strong one, requiring at least 5 black slabs. Same if the latter doesn't exist.

Similarly, there can't be more than two 4-strong white slabs, so there are at least 4 white slabs with soldiers. If there are two, they're on opposite corners of the 3x3 inner area, and there can be at most 2 soldiers on the other two each.

Any slab must have at least one populated adjacent slab as the soldier originally on the former must go to one of them. Using T-shaped tetrominoes on the borders, this rule guarantees 5 white slabs if the center slab is. If it isn't, and there are 4 populated white, 5 black slabs, the former slabs are at a5, b2, d4 and e1 (or a rotated version), or a3, c1, c5 and e3.

Let's cut from each corner the 3 slabs at the corner and the two adjacent slabs. Assuming there are 4 white and 5 black occupied slabs, there must be at least one occupied black slab in each trio. There's at least one more is in the remaining part, so there must be only one in each part. Then let's divide the grid differently: 4 T-shaped tetrominoes, each leaning on the non-corner border slabs. All the remaining slabs are white. The lone white slab in each tetromino is only adjacent to the black ones, meaning there's also at least one occupied black slab in each tetromino (two in one of them and only one in the rest). That extra black slab is inside (at the tip of the T shape). Assuming b1 and c2 are occupied (because there's symmetry):

-0-V-
V-0-0
-000-
0-V-V
-V-0-

-0-3-
3-0-0
-000-
0-V-V
-V-0-

Assuming a3, c1, c5 and e3 are occupied (3 soldiers each):

00330
30000
30003
00V0V
0V300

A possible solution:

00330
30000
30003
00103
03300



Result:

25-9=16