A probability problem by soumyaranjan ram
On a large 9 9 9 × 9 9 9 board, each cell is colored either white or black.
Define a coordinated triple of cells ( C 1 , C 2 , C 3 ) as the formation such that
- C 1 and C 2 are in the same row;
- C 2 and C 3 are in the same column;
- C 1 and C 3 are white;
- C 2 is black.
What is the maximum number of coordinated triples? Enter your answer as the last three digits of that maximum.
The answer is 852.
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.
1 solution
We are looking for a maximum value of 999 * n * (999-n)^2, where n is the number of black squares in each row and column.
Differentiate f(n)=n^3 - 2 * 999 * n^2 + 999^2 and solve the quadratic
f'(n) = 3 * n^2 - 4 * 999 * n + 999^2 =0
To give solutions n=333 and 999. The second of these is a minimum value, since f (n)=0, so it only remains to calculate 999 * 333 * 666^2 (mod 1000)
Log in to reply
Sorry again but my solutions seem to be losing the multiplier symbols.
f (n) = n^3 - 2 x 999 x n^2 + 999^2
The final calculation is:
999 x 333 x 666 x 666
Log in to reply
FYI The reason why you're losing the multiplier symbols, is because we use markdown for our text. Placing * directly next to words would cause them to be italicized, like so: * 123 * (with no spaces) will produce 123 .
So, to avoid losing the multiplier symbols, just leave spaces all over. I've edited your first comment to reflect this.
How do you know that the number of black squares in each row and column is a constant?
Log in to reply
You can demonstrate this is a local maximum by seeing what happens if any of the squares switches from black to white, or vice versa, but I'd accept this is not a comprehensive proof that the result has to be a regular pattern.
Log in to reply
@Malcolm Rich – Right. The proper proof is slightly more involved, and uses a bunch of counting and inequality arguments to get at it. Studying the 3 × 3 and 6 × 6 case might provide some insights.
Solution here works for symmetric arrangements
Let n be the number of black squares in each column and row. Goal is then to maximise 999*n999-n)^2
The problem needs to describe the board better, with an odd number the answer will change if the corners are black or white.
Log in to reply
You get to determine how to color the board, and have to find the maximum over all such possibilities.
One (not so reliable way) to get an approximation is to use an iterative repair approach. You start by choosing a random permutation of a board and change the configuration of some small number of squares so that the new configuration is better according to some heuristic.
just leaving a reply incase someone posted a full solution, btw where can i report a bug in the website?
Log in to reply
You can email support at brilliant.org for bugs in the product.
If you see an issue with a problem, select "Report Problem" from the menu, which will make it much easier for us to respond.
[This is not a solution. Discuss in the comments how one can approach this problem.]