Brilli the ant has a Jumping Flea circus act. She places one flea in each square of a 8 × 8 board. When she cracks her whip, each flea jumps to an adjacent square which shares a common side. What is the maximum possible number of empty squares after the whip is cracked?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
"I believe the solution (coverage) is minimal because each non-empty square has exactly and only 1 red neighbor." - can this be formalized?
Log in to reply
Indeed. Personally I just did some trial and error so I don't know myself, but I'd be interested to hear a formal argument as to why 4 4 is the answer.
Log in to reply
The 'formal argument' is that the fleas in those 20 red squares must land in different squares. Hence at least 20 squares are occupied.
And since any flea can reach one of these red squares, hence 20 is sufficient.
Log in to reply
@Calvin Lin – I mean, a formal argument to show that "there is a configuration with N red squares where each non-red square has exactly one red neighbour" implies that N is minimal, i.e. "there is no other configuration with fewer than N red squares such that each non-empty square has exactly one red neighbour", which seems to be what the original submission is relying on.
I have a counterexample of sorts: if we consider just the 12 light squares of a 5x5 board which has the corners as dark squares , then red squares {a1, e1, a5, e5, c3} satisfies "each light square has exactly one red neighbour", but the red square set is not minimal ; {c1, a3, e3, c5} also satisfies the condition.
I haven't found a counterexample yet which satisfies both the light and dark squares simultaneously but the existence of this example makes me think that maybe the principle actually doesn't work.
Log in to reply
@Matt McNabb – I was replying to Mike.
I believe (no proof) that this is not an accurate classification of the minimal case. The issue in part is that not all red squares are created equal, with the corners and sides being less useful.
@Matt McNabb – Your counter example is a board of odd size, while the principle s formalized for even sided boards.
Log in to reply
@Nicholas DelGaudio – I don't see even-sized boards mentioned in this principle?
Each flea in a red square will occupy a position different from each other flea in red squares, so there will be at least 20 different occupied squares
a 0x0 board will have 0 empty spaces a 2x2 board will have 2 empty spaces (maximum) a 4x4 board will have 10 empty spaces a 6x6 board will have 24 empty spaces a 8x8 board will have 44 empty spaces
It is a quadratic with the second degree difference being 6, so a 10x10 board will have 70 empty spaces.
this makes it possible to calculate the number of empty squares for a NxN board? (N being pair)
Oh.:( I got 20, but i forgot to subtract it from 64.
Main idea : Find a lower bound on the number of squares occupied and realize it by a model.
Complete proof :
First, color the board in a chessboard pattern. Observe that fleas on the black squares will end up on white squares and vice versa, and they don't disturb each other, so our task is simplified to observe only the fleas on the black squares that moves to white squares and multiply the result by two.
Next, observe the following image . Light blue squares are black ones. Note that no white square is adjacent to more than two white circles, so no three fleas from white-circled squares can gather in a single white square. There are 20 white circles, so we need at least 10 occupied white cells. This is also realized by the black circles; note that every light blue square is adjacent to at least one black circle, so they can move there. This frees up 3 2 − 1 0 = 2 2 white squares.
By symmetry, we can also free up 2 2 black squares, so the maximum number of squares freed is 2 2 + 2 2 = 4 4 .
Motivation : To be honest, I'm not sure how I came up with that. I quickly obtained the model with 1 0 filled squares easily by doing some greedy collections, but it's surprisingly hard to prove that. I tried to put the white circles so no white square is adjacent to more than one white circle, but I kept only getting 9 on the board. So I somehow got the idea to use two white circles per white square, and for some reason got the above quickly. I'm still figuring out whether the maximum number of white circles such that no white square is adjacent to more than one white circle is indeed 9 or not; if it is, then this problem is one of the most devious problems I've ever seen. If it isn't, then it's still one of the most devious since then the configuration is hard to obtain.
Generalization : Making it to any board size of even length seems not terribly fun; that configuration is easily extensible. More interesting is of odd length, as the symmetry of white and black squares is broken. I believe this deserves its own discussion...
Oh right I haven't found a model. I have the lower bound of occupied cells, but I forgot that the model is not easily extensible, especially as there are black squares not containing white circles. Okay, let's put aside the generalization for odd lengths; this even lengths problem is not even solved yet.
Log in to reply
It's hard to generalize, in part because you don't have a clear pattern in your attached image. Even if you refer to Anis' solution, there seems to be a pattern, but it doesn't easily extend either.
I don't know of a generalization, and would be interested in seeing one. I don't think that the 9 × 9 case can be dealt with as cleanly.
Log in to reply
Ah, but this is easily extensible, no? That takes quite some time to figure out though. I'm not sure what motivates me to make that pattern; mostly just from greedy.
Log in to reply
@Ivan Koswara – It's hard to say. When it comes to the greedy algorithm, the choice of path can affect the final outcome. It is not immediately obvious that it will work.
Log in to reply
@Calvin Lin – The picture I have is not a greedy algorithm. It's a pattern, which you can see at the bottom-left triangle and the top-right triangle of the grid separately.
(The motivation is greedy, but once I noticed the pattern, I can quickly prove it rigorously that the pattern can complete the board.)
Log in to reply
@Ivan Koswara – Its more like the black dots placed on the daigonals(top left to bottom right) and all such alternate daigonals are filled....Is it??
By the way what is that "Greedy" algorithm??
Log in to reply
@Santanu Banerjee – Not exactly, since there are many blank spots.
Greedy algorithm is simply an algorithm that selects the local maximum. For example, with a different problem:
To reach city B from city A, you must either take a route A-C-B or A-D-B. It takes 1 hour from A to C, 4 hours from C to B, 2 hours from A to D, and 1 hour from D to B. Suppose there is no other road.
A greedy algorithm takes the "local best". For example, the algorithm will start from city A and only see the routes A-C and A-D (!). Since A-C is shorter, it takes that route without checking A-D. Of course, we know A-C-B is longer than A-D-B due to C-B, but the greedy algorithm doesn't know this. Hence the greedy algorithm doesn't always work (and in fact rarely works for optimal solutions, but in most cases gives good approximations).
In this problem, I didn't use greedy algorithm rigorously; it was just scratch work, just like in math competitions not everything you write on your scratch paper will be submitted/graded. The greedy algorithm gives me an insight that the above pattern works, which I can prove rigorously without using greedy algorithm (for example by induction).
Nice solution, Ivan.
I have another way of showing that at least 10 white squares must be occupied. I don't have time now to write it up formally, but here's the idea roughly: considering the black squares as 8 diagonals, each with an odd number of squares (1,3,5,7,7,5,3,1 -- in your picture, each diagonal going up-to-the-right) we can see that the number of fleas-on-white cannot be more than 4 n − 8 , where n is the number of occupied (white) squares. But 4 n − 8 ≤ 3 2 means n ≤ 1 0 .
Since each flea starting on a white square jumps to a black square and vice versa, we can consider the fleas starting on black separately to the fleas starting on white. In fact, if we find an optimal solution for the fleas starting on black, then by symmetry that will give us the optimal solution for the fleas starting on white.
I'm going to use chess notation here for simplicity. To maximise the number of empty white squares after the whip, it is equivalent to minimizing the number of kings we can place on white squares such that every black square is attacked (i.e. is adjacent to a king). The squares with kings correspond to the squares that fleas jump to, and any flea is adjacent to a king because we stipulated that.
Here is a solution with 1 0 kings: the kings are on d1, a2, g2, d3, b5, f5, h5, d7, a8, g8.
Now we will show that 9 kings is not possible, by showing that in the lower-left half of the board, there must be 4 kings which only cover at most 1 3 squares between them. The same argument will also show that the upper-right half of the board must have the same; so the maximum coverage of 9 kings will be 1 3 + 1 3 + 4 = 3 0 , but there are 3 2 black squares.
Consider the square a 1 . To attack it, there must be a king on a 2 or b 1 . By symmetry we can assume this king is on a 2 without loss of generality.
Now consider c 1 . To attack this square there must be a king on c 2 or d 1 . (Having a king on b 1 is sub-optimal, this will become clear shortly if it isn't already).
In either case, only three new squares are attacked, so we have 2 kings placed with only 6 squares attacked.
If the second king is on c 2 , then consider the square e 1 . Regardless of which square a king is placed on to attack e 1 , it can only attack 3 new squares. So we would have 3 kings placed that only cover 9 squares, therefore (choosing any other king in this half) there are 4 kings that only cover 1 3 squares.
If, instead, the second king is on d 1 , consider the square b 4 . In order to place a third king that attacks at least 3 new squares including this one, that king must be on b 5 or c 4 . In both cases, the third king attacks 4 new squares.
If the third king is on b 5 then consider c 3 . Regardless of where a king is placed adjacent to c 3 , at most one new square is attacked besides c 3 , so our first four kings attack at most 1 2 squares.
If the third king is on c 4 then consider a 5 . Regardless of where a king is placed adjacent to a 5 , at most 3 new squares are attacked including a 5 , so our first four kings attack at most 1 3 squares.
We have exhaustively traversed a tree of possibilities now, and proven that 9 kings can only cover 3 0 squares.
Therefore 1 0 kings must be on white squares. Going back to the fleas, this means there can be at most 3 2 − 1 0 = 2 2 empty black squares after the whip. By symmetry there can be at most 2 2 empty white squares, for a total of 2 2 + 2 2 = 4 4 .
Very small correction, twice I say "9 kings can cover at most 30 squares", should say "9 kings cannot cover more than 30 squares", I didn't actually show if this bound can be attained.
Log in to reply
Yes, covering 30 squares is possible. From my solution, remove the black circle on (4,4), where the lower left square is (1,1). All blue squares but (3,4) and (4,3) are covered.
But both wordings are valid nevertheless; "9 kings can cover at most 30 squares" doesn't imply that it's possible for 9 kings to cover 30 squares.
Problem Loading...
Note Loading...
Set Loading...
Look at the following image, where the red are the non-empty squares.
Non-empty squares