(ISL-20-$1988$) Find the least natural number $ n$ such that, if the set $ \{1,2, \ldots, n\}$ is arbitrarily divided into two non-intersecting subsets, then one of the subsets contains 3 distinct numbers such that the product of two of them equals the third.

WARNING: You can probably already see that the approach would be to conjecture the answer. My question is how one can conjecture the answer. So if you want to work on the problem first, don't read ahead.

You can find its solution here. I don't know if his solution is right, but you can also find a solution in THE IMO COMPENDIUM. The answer seems to be right though.

My initial idea was that the value of $n$ has to be sufficiently small, probably less than $50$, for someone to be able to conjecture a solution. My next idea was that I would have to use PHP somewhere. Clearly, none of them are true.

My question is:How do you conjecture that the answer is $96$?

My take on it is that I should have realized that the solution has to be sufficiently easy after guessing the solution. So one must increase the number of divisors of $n$ in order to to be able to get a contradiction.

How do you think you would conjecture the solution?

Thanks .

  • $\begingroup$ Presumably, you really want to ignore $1$? $\endgroup$ – Thomas Andrews Jun 24 '15 at 18:37
  • $\begingroup$ @ThomasAndrews, n=1 doesn't satisfy the conditions, I think. $\endgroup$ – rah4927 Jun 24 '15 at 20:47
  • $\begingroup$ Yeah, I was meaning the membership of $1$ in the partition, but I forgot he wrote distinct. Basically, which partition $1$ is in is irrelevant. $\endgroup$ – Thomas Andrews Jun 24 '15 at 20:49

I'm not sure this question has a right answer. The question is basically, how do you find the right answer efficiently? That is, can an answer be found without trying every possibility? For that, you'll need heuristics.

My approach was to look for numbers that are combinations of as many small prime factors as possible while keeping the number small. For example, if you restrict yourself to numbers that are a power of 2 and look at all of the factorizations of that number into factors which are not necessarily prime, you can determine whether it is possible to partition those factors into sets not satisifying the condition. I looked at 8, 16, 32, 64, and 128. When I got to 128, I saw that there was no way to partition its factors and all of the factors of those factors.

$128 = 2 * 64 = 4 * 32 = 8 * 16$

$64 = 2 * 32 = 4 * 16$

$32 = 2 * 16 = 4 * 8$

$16 = 2 * 8$

$8 = 2 * 4$

That told me that the answer was less than or equal to 128. But, 128 might not be the best solution, because the smallest pair of distinct factors is 2 and 4. So, that got me thinking that numbers that have a lot of factors of 2 and 3 might give a better solution. If you just march through all of the numbers that are products of 2 and 3, I think you'll find that 96 is the smallest number whose factors can't all be partitioned.

Edit: Based on Calvin's comment below, it appears that I might have stopped one iteration too soon. I should have gone to 256.

$256 = 2 * 128 = 4 * 64 = 8 * 32 = 2^1 * 2^7 = 2^2 * 2^6 = 2^3 * 2^5 = 2^8$

The number $8$ cannot be included in either of Calvin's sets without satisfying the partitioning property and, therefore, the $256$ cannot be included without satisfying the condition specified in the original post.

  • $\begingroup$ Nice answer, thanks.+1 $\endgroup$ – rah4927 Jun 24 '15 at 20:49
  • 1
    $\begingroup$ Note that the question about partitioning the divisors of $128$ is easier if you think of it as partitioning $\{1,2,3,4,5,6,7\}$ so that there is no distinct $a,b,c$ in one partition so that $a+b=c$. $\endgroup$ – Thomas Andrews Jun 24 '15 at 20:50
  • $\begingroup$ @ThomasAndrews What about $\{1,2,4,7\}$ and $\{3, 5, 6\}$? Isn't that a valid partition? $\endgroup$ – Calvin Lin Jun 26 '15 at 5:45
  • $\begingroup$ I wasn't saying it could or couldn't be done, just that the problem was easier to see in terms of sums. I assumed answerer was correct, but I couldn't quite follow the reasoning, hence my suggestion to rephrase that part this way. @CalvinLin $\endgroup$ – Thomas Andrews Jun 26 '15 at 10:58

The first thing I'd note is that if the set does not contain any number with four not-necessarily distinct prime factors, then you can easily partition it into the sets of numbers with two prime factors and numbers with one or three prime factors. So that means that $n\geq 16$.

Are you sure that your answer of $96$ is correct?

If you let $f(d)$ be the number of prime divisors of $d$ (including repetitions) then you can define $A=f^{-1}\{0,1,2,4,7\}$ and $B=f^{-1}\{3,5,6\}$. Then $A\cap \{1,2,\dots,255\}$ and $B\cap\{1,2,\dots,255\}$ should satisfy your condition for $n=255$.


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.