11
$\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$

This question has an open bounty worth +100 reputation from athin ending in 3 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 :)

6
$\begingroup$

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.

![8x8_1

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.

![8x8_2

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.

![8x8_3

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.

![enter image description here

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.

![enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – athin May 18 at 0:39
  • $\begingroup$ Whoops, copy error. I fixed it, thanks $\endgroup$ – Dark Thunder May 18 at 10:40
8
$\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
7
$\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
7
$\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.