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

## This question has an open bounty worth +100 reputation from athin ending in 5 days.

One or more of the answers is exemplary and worthy of an additional bounty.

I initially wanted to start this bounty later at some point as there was no exact answer to construct the lower-bound. But after a 3-months vacuum, @DarkThunder comes with a brilliant answer to complete this puzzle :)

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.

• Woah finally.. A very great answer! And shouldn't it be $(3N-2)/2$ balls instead of $(3N+2)/2$? :) As the lowerbound is proven by @KradCigol , hence your construction is indeed optimal. Congratulations!! :D – athin yesterday
• Whoops, copy error. I fixed it, thanks – Dark Thunder yesterday

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:

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.

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