16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can they only move from 1 slab to another, or can they step off a slab at the edge? $\endgroup$ – gnovice Jan 30 '18 at 17:53
  • $\begingroup$ @gnovice No, they must stay within the parade ground. Edited to clarify. $\endgroup$ – Rand al'Thor Jan 30 '18 at 17:59
  • 2
    $\begingroup$ @APrough Like it says in the question, "each soldier moves". Staying still isn't allowed, or they'll be court-martialled ;-) $\endgroup$ – Rand al'Thor Jan 30 '18 at 18:54
  • 5
    $\begingroup$ @Randal'Thor So the optimum solution is nobody moves, they all get dragged away to their courts martial and there are now 25 unoccupied slabs? :) $\endgroup$ – Philipp Jan 30 '18 at 21:43
  • 1
    $\begingroup$ @Talset No direction is specified. (Otherwise the problem would be trivial, at least if the soldiers obey.) $\endgroup$ – Rand al'Thor Jan 30 '18 at 23:04
18
$\begingroup$

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 .
$\endgroup$
  • $\begingroup$ This is basically the same answer given by @gnovice's and Oray. Can you prove it's optimal? $\endgroup$ – PopularIsn'tRight Jan 30 '18 at 20:35
  • 2
    $\begingroup$ @Bachrach44 My first paragraph is the optimality proof. $\endgroup$ – Mike Earnest Jan 30 '18 at 20:37
  • 1
    $\begingroup$ Ah, "different slabs than each other". That makes sense now. $\endgroup$ – gnovice Jan 30 '18 at 21:18
  • 5
    $\begingroup$ Good work! Bonus question: judging from your diagram with the xs, which historical army are the soldiers part of? ;-) $\endgroup$ – Rand al'Thor Jan 30 '18 at 23:04
  • 3
    $\begingroup$ @Randal'Thor D: it’s no fair, man, everything with 90 degree symmetry ends up looking like a swastika! $\endgroup$ – Mike Earnest Jan 31 '18 at 3:09
13
$\begingroup$

Basically, the insight to make this problem easier is:

To view the board as a checkerboard.

enter image description here

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.

enter image description here

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.

enter image description here

Then, move to the second part:

The soldier on black slab.

enter image description here

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).

enter image description here

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.

$\endgroup$
  • $\begingroup$ Well, I just want to share this observation which I think may help to prove the answer simpler (and more elegant?), while actually the answer is already given by @MikeEarnest :) $\endgroup$ – athin Jan 31 '18 at 2:14
  • 1
    $\begingroup$ Man, I was really overthinking the proof. I was trying to use Markov models and minimizing linear equations. $\endgroup$ – gnovice Jan 31 '18 at 2:48
  • $\begingroup$ The only thing missing is proving that 4 and 5 are the minimum (for example by picking 4 Os on 1st and last lines and 5 Xs on corners and center and showing they need to land on different squares). $\endgroup$ – Tibos Jan 31 '18 at 13:19
  • $\begingroup$ @Tibos, yes good point. Actually, we can prove by taking what is the lowerbound of the answer; i.e. the first one cannot be 3 and the second one cannot be 4. Maybe using bruteforcing that 3 and 4 is impossible, and we got 4 and 5 as upperbound (we showed that there is exist the placement for 4 and 5), then 4 and 5 is proven to be minimum. Well, haven't figured out the formal proof that 3 and 4 is not exist tho. $\endgroup$ – athin Jan 31 '18 at 13:28
  • 1
    $\begingroup$ @athin Sorry, my comment was not clear. You can pick 4 white squares on the edges (first on each edge going clockwise for example) and it's obvious any 2 of them are too far apart to reach the same square, so 4 is lower bound for soldiers starting on white squares. Same rationale for picking 5 black squares (corners + center). $\endgroup$ – Tibos Jan 31 '18 at 17:32
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Good answer, but not the optimal number. $\endgroup$ – Rand al'Thor Jan 30 '18 at 17:46
  • $\begingroup$ 4th row, last x, can be removed, making it 17 $\endgroup$ – Mart10 Jan 30 '18 at 21:20
  • $\begingroup$ @Mart10: Nope, that soldier in the bottom right corner needs somewhere to move. $\endgroup$ – gnovice Jan 30 '18 at 21:21
  • $\begingroup$ good point, didnt notice $\endgroup$ – Mart10 Jan 30 '18 at 21:22
3
$\begingroup$

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 :)

$\endgroup$
  • 1
    $\begingroup$ Pro tip: you can create your own gif files (not embedded in a website) using a tool called LICEcap, which you can then make visible in your post just like any other image. (It's what I used for this answer - very useful tool!) $\endgroup$ – Rand al'Thor Jan 30 '18 at 18:17
  • $\begingroup$ Anyway ... 16 is pretty good. Can you prove that it's optimal? :-) $\endgroup$ – Rand al'Thor Jan 30 '18 at 18:18
  • $\begingroup$ @Randal'Thor there was 2MB limit, this gif is 2.5MB :) but i will check that app out. lastly, i will try to confirm this is optimal.. i am not sure yet it is... $\endgroup$ – Oray Jan 30 '18 at 18:45
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Soldiers must stay within the parade ground (sorry if this was unclear). And even if they could move off, this solution wouldn't be optimal. $\endgroup$ – Rand al'Thor Jan 30 '18 at 18:04
  • $\begingroup$ Ahh understood. Can there be more than two on the same block? Or is the limit two? The way I hastily read it the first time, I assumed there was a limit. $\endgroup$ – doggify Jan 30 '18 at 18:19
  • $\begingroup$ No, there's no limit on the number that can stand on the same slab. It's a big parade ground :-) $\endgroup$ – Rand al'Thor Jan 30 '18 at 18:24
2
$\begingroup$

I got:

17

by using this board:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ But where do the soldiers on the white squares move to? $\endgroup$ – gnovice Jan 30 '18 at 18:50
  • $\begingroup$ I have arrows in each square showing their movements, and each total on each square. a 1 is a soldier, a > means right an ^ means up dn means down and < means left. Each square without a sildier is highlighted in yellow. I apologize for formatting, i can fix it once i get back on my windows machine. $\endgroup$ – Jason V Jan 30 '18 at 18:51
  • $\begingroup$ What I mean is, each soldier has to move. They can't stay in one spot, so the ones already on white squares have to move somewhere. $\endgroup$ – gnovice Jan 30 '18 at 18:53
  • 1
    $\begingroup$ Every one of the 25 soldiers has to move. You've indicates where the ones originally on yellow cells move to (the white cells), but what about the ones originally on white cells? $\endgroup$ – Rand al'Thor Jan 30 '18 at 18:54
  • $\begingroup$ did not realize they all had to move. Thanks! $\endgroup$ – Jason V Jan 30 '18 at 18:54
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.