Distinct Arrangements of Balls on Tiles

Question

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

Answer 1

First off... who puts balls on tiles? They roll away and not to mention the cat keeps batting at them. Am I the only one who thinks about these things???

Sorry. I like this problem, I know you didn't really ask, and this is now the distant future, but I'd like to solve the bigger question of N x N grids:

An N x N grid requires (3N-2)/2 balls to ensure the required 2N unique combinations. I will note an odd value for N requires that the equation be rounded up, and that N=1 and N=2 are not solvable for any # of balls. This equation represents the limit using the least ball-centric combinations, but also represents the actual solution for all N>2 because there is an easy-ish method for building the puzzle.

The big strategy I am putting forward is that you must first tackle the 1-ball combinations and everything else will fall into place.

This is an example 8x8 grid. I have labeled some of the rows and columns to remind myself how many balls I intend on putting in that row or column. I have eight total 1-ball combinations and I must use all of them. These four balls generate the eight combinations I need.

But when I go to fill in the 2-ball combinations I have a problem. The rows and columns, when added up, come out to different values. This isn't a big deal, we just need to fix it up a bit in those last two rows. I just sort of flipped the labels in the corner.

The last step isn't magic, I just started filling in balls to satisfy the 2-ball rows and columns and it just sort of solved itself. We have many 2-ball combinations at our disposal and better yet this alternating spacing happens to be awesome for not making duplicate combinations. I don't know... maybe it is magic.

So check this out. This pattern emerges from filling in those 2-ball combinations. N is odd here so you will note the labels in the lower corner look a bit different. Bottom two rows look a little funny, and that's always going to happen. I figure there's twelve or so different ways that pattern could end in the corner.

I would love to know if there is a way to arrange things where you don't have to fix up the bit in the corner. It's pretty elegant if not for that. I had fun.

Answer 2

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

Answer 3

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.

Answer 4

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