4 square bins
The integers 1 through n (inclusive) are separated into four 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 24.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Potential follow-up question: Find the number of ways the numbers 1 - 24 can be divided into the 4 boxes such that the "no square product" condition is satisfied.
Log in to reply
Sounds good! Not sure I know the answer yet tho... :-/
Log in to reply
Yeah, I'm not sure how to tackle it yet either. I think we would first have to identify all the pairs of non-squares whose products are squares and make sure that their components are put in separate boxes.
Log in to reply
@Brian Charlesworth – I find only a few combinations which would need to be avoided:
- 2,8
- 2,18
- 3,12
- 5,20
- 6,24
- 8,18
Any I missed?
The 2,8,18 trio is interesting. It means that even if you exclude the square numbers themselves, with 2 bins you could only go up to 17.
Log in to reply
@Geoff Pilling – Yes, I think you've found all the pairs. So without worrying about how the boxes are labeled, this would yield 2 4 ∗ 1 2 3 = 4 1 4 7 2 possible arrangements.
Log in to reply
@Brian Charlesworth – Hmmm... Lemme think about it for a bit... Does that take into account that 1,4,9, and 16 need to be in different bins? And the 2-8-18 triad?
Log in to reply
@Geoff Pilling – Hi Geoff. I think the answer should be your answer ×4! Because 1,4,9,16 can also be arranged in 4! different ways. What do you think?
Log in to reply
@Kushagra Sahni – Well, if it asked how many different ways they could be arranged, then, yes, I believe you would be correct, however it is only asking what is the largest number for which this is possible. And 24 is the largest number. Beyond that you have 5 square numbers which will be impossible to put into 5 bins without two multiplying together in one of the bins to make a square.
Log in to reply
@Geoff Pilling – Oh yeah, that is perfectly fine. I did solve the question that way only but I was talking about the question Brian Sir gave to you.
Log in to reply
@Kushagra Sahni – Ah, ok, got it... Yeah definitely 4! needs to be included in the count... Thanks for your input!
@Brian Charlesworth – I get over a million... But I may have an issue with my logic. It seems to me that WLOG you can label the boxes 1, 4, 9 and 16 and put those respective numbers inside.
Now there are 11 numbers which appear to be able to go into any of the 4 bins, namely 7, 10, 11, 13, 14,15, 17, 19, 21, 22, and 23.
It seems like the distribution of these numbers alone yields 4 1 1 = 4194304 possibilities.
And we haven't yet distributed the numbers in the six combinations of non squared numbers above.
Log in to reply
@Geoff Pilling – Now to finish off, the 2-8-18 triad can be put in 4! ways. Each of the other three pairs can be put in 4*3 ways.
So the total would be 4 1 1 ∗ 4 ! ∗ 1 2 ∗ 1 2 ∗ 1 2 = 1 7 3 9 4 6 1 7 5 4 8 8
Phew! Glad I didn't enumerate them all...
But did I make a mistake somewhere? (I'm pretty good at doing that! ;) )
Log in to reply
@Geoff Pilling – Yes, that's correct! I was so preoccupied with the noted pairs and triad that I totally forgot about the other 11 loners that could be placed in any box.
@Geoff Pilling very nice question.Expecting more questions like this
nice question. I am so happy I got it correct :)
The numbers 1-24 can be divided into 4 bins as follows:
However, none of the numbers 1,4,9,16, and 25 can be in the same bin, since they are square numbers, and the product of square numbers is another square number. Therefore we would need five bins to accommodate them.
Therefore, 2 4 is the largest n for which the above is possible.