Square bins

Probability Level 3

The numbers 1 through $n$ (inclusive) are separated into 2 bins.

For each bin, no two different numbers in it can multiply together to form a square number.

What is the largest $n$ for which this is possible?

If you think the answer is infinite, please put 99999 as your answer.

The answer is 8.

1 solution

Geoff Pilling
Nov 21, 2016

The numbers 1-8 can be separated in the following way::

Bin 1: 1,2,3,5,6,7
Bin 2: 4,8

Now, once we get to 9, there is no solution. Consider only the numbers 1, 4, and 9. No two of them can be placed in the same bin since the product of any two is a square. Therefore, you would need at least 3 bins to accommodate them.

Therefore, $\boxed{8}$ is the highest value for $n$ .

Great question!

Unfortunately, the argument of "the case of 9 must be obtained from the case of 8" isn't valid. We need a seperate argument.

Calvin Lin Staff - 4 years, 6 months ago

Good point... I've updated the solution!

Geoff Pilling - 4 years, 6 months ago

Square bins

The answer is 8.

1 solution

0 pending reports