# Distinct Arrangements of Balls on Tiles

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:

Bonus: How about $$N \times N$$?

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

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

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.

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

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

• what if N is odd? – JonMark Perry Feb 10 at 16:03
• We round it down, @JonMarkPerry. – Krad Cigol Feb 10 at 16:12
• 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! – Krad Cigol Feb 10 at 16:13
• how does your general formula give the answer as 11 for N=8? – JonMark Perry Feb 10 at 21:45
• this answer provides the lower bound, however how to construct the arrangements for such lower bound? :) – athin Feb 11 at 23:00