7
$\begingroup$

You want to put several balls on $8 \times 8$ tiles, such that all $16$ ball arrangements on its rows and columns are different. What is the minimum number of balls to be put?

Two arrangements of balls are different if there exists a ball on some $i$-th tile of the first one but no ball on $i$-th tile of the second one. (For row, the $i$-th tile means the $i$-th column; for column, the $i$-th tile means the $i$-th row.)

For example, we need at least $4$ balls for $3 \times 3$ tiles and the configuration as the following:

enter image description here

Bonus: How about $N \times N$?

$\endgroup$
6
$\begingroup$

A solution in:

17

 00000000
 X0000000
 0X00000X
 00XX0000
 000XXX00
 0000XXXX
 X0000XXX
 0000000X

Borrowing from @Jaap:

11

   ....x...
   .....x..
   ......x.
   .......x
   .x.....x
   .xx.....
   ..xx....
   ...x....

$\endgroup$
  • $\begingroup$ Beat me to it. And a better solution is clearly not possible. $\endgroup$ – Daniel Mathias Feb 10 at 15:29
5
$\begingroup$

I think this might be an optimal solution, but I’m not sure. (Edit: It's not optimal - one fewer balls is possible)

   ....x...
   .....x..
   ......x.
   .......x
   xx......
   .xx.....
   ..xx....
   x..x....

This generalises in an obvious way for even $N$ to give a solution with $3N/2$ balls. For odd $N$ you can do almost the same, but with one fewer row an column with two balls, giving a total of $(3N-1)/2$ balls.

$\endgroup$
  • $\begingroup$ nicely done! Your answer inspired me to solve mine. You were so close! The general formula was only slightly off. Thanks @Jaap $\endgroup$ – Krad Cigol Feb 11 at 14:09
5
$\begingroup$

Piggybacking off @JonMarkPerry:

The answer is 11.

Proof:

We have a total of 2N rows and columns, with each having a unique permutation of balls.
We get N c 1 ways to place 1 ball.
We get N c 2 ways with 2,
And so on.
Now, we need to find the minimal number of balls to give each row a unique permutation.
Note that N c 1 = N.
N c 2 = N(N-1)
And so on.

Adding the two, we get

N$^2$
Which is clearly greater than 2N, assuming that $N>2$

So the requirement is:

0 balls for 1 row/column.
$N*1$ balls for next N row/columns.
Remaining N require $2(2N-N-1)=2N-2$
This adds up to a total minimum of $3N-2$ We need to divide by two, as we counted each ball twice, once in a row and once in a column.

Therefore,

The general formula is
$ceil((3N-2)/2)$

$\endgroup$
  • $\begingroup$ what if N is odd? $\endgroup$ – JonMark Perry Feb 10 at 16:03
  • $\begingroup$ We round it down, @JonMarkPerry. $\endgroup$ – Krad Cigol Feb 10 at 16:12
  • $\begingroup$ By the way, I think I missed the one row without balls. And a few other errors. Will fix it later. It adds a good amount of error to the equation. Sorry, @JonMarkPerry! $\endgroup$ – Krad Cigol Feb 10 at 16:13
  • $\begingroup$ how does your general formula give the answer as 11 for N=8? $\endgroup$ – JonMark Perry Feb 10 at 21:45
  • 2
    $\begingroup$ this answer provides the lower bound, however how to construct the arrangements for such lower bound? :) $\endgroup$ – athin Feb 11 at 23:00

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.