12
$\begingroup$

Problem: Prove that a set of nine consecutive integers cannot be partitioned into two subsets with same product

My attempt:

This problem would be solved if it could be proven that 9 consecutive numbers cannot exist such that all the numbers are of the form $2^a 3^b 5^c 7^d$ where $a,b,c,d$ are integers.

A suitable hint would be appreciated, I don not want a complete solution.

Edit:

If there existed a prime factor greater than $7$ of any number present in the set, then its multiple cannot exist b/c $22-11>9$

Edit 2: As mentioned by Erick, my reasoning is not valid for numbers $1-9$ and $2-9$, let this be an exception.

$\endgroup$
  • 1
    $\begingroup$ 1) Why would your hypothesis be sufficient to solve the problem? 2) Your hypothesis is false for the consecutive numbers 1–9 and 2–10. However, it is known that there are only finitely many counterexamples. The original problem is definitely true by a classic (and much stronger) theorem of Erdős and Selfridge. $\endgroup$ – Erick Wong Oct 14 '15 at 7:28
  • $\begingroup$ Hint: using the fact that nine is odd, you can bound how large the consecutive integers could possibly be. $\endgroup$ – Erick Wong Oct 14 '15 at 7:33
  • 2
    $\begingroup$ @ErickWong How is it wrong? Can you give the subsets with same product? $\endgroup$ – guest Oct 14 '15 at 7:55
  • 3
    $\begingroup$ @guest I believe Erick Wong is referring to your hypothesis about numbers of the form $2^a3^b5^c7^d.$ $\endgroup$ – bof Oct 14 '15 at 8:06
  • 1
    $\begingroup$ This is a problem which you can find (with full solution) in the first chapter of Putnam and beyond $\endgroup$ – CIJ Oct 14 '15 at 17:10
15
$\begingroup$

Hint

  1. Show that none of the 9 consecutive numbers can be a multiple of $13$.

  2. Denote the product of the 9 consecutive numbers by $a$. Show that $a$ must be square.

  3. Look at the remainder of $a$ modulo $13$. Use 1. to see that there are only $4$ possibilities. Use 2. to find a contradiction in all 4 cases.

(This is inspired by this answer. Note that taking the residues modulo $11$ won't work but, quite surprisingly, $13$ does.)

$\endgroup$
  • 1
    $\begingroup$ I was thinking along the same lines but I was discouraged by the fact residues modulo $11$ didn't work. This seems to be a lucky guess. $\endgroup$ – guest Oct 14 '15 at 8:41
  • $\begingroup$ @guest Yeah, I was quite surprised that mod 13 works. Quite a "coincidence" that all 4 possibilities give non-squares. $\endgroup$ – azimut Oct 14 '15 at 8:43
  • $\begingroup$ I would have to register for that. btw, does that matter? $\endgroup$ – guest Oct 14 '15 at 8:48
  • $\begingroup$ Hey! I was right about the 5! $\endgroup$ – fleablood Oct 14 '15 at 22:05
  • $\begingroup$ Let me ask you question about 1. Why none of the 9 consecutive numbers can be a multiple of 13? If we take the set $\{13, 14, 15, \dots, 21\}$ we see that set has element which is multiple of $13$. $\endgroup$ – ZFR Mar 5 '17 at 18:53
13
$\begingroup$

Another idea is to write your numbers $a,a+1,...,a+8$. Let $A$ and $B$ your equal products. Then one of them (say $A$) has at most $4$ factors, and the second (B) has $\geq 5$ factors. Then $A\leq (a+8)^4$ and $B\geq a^5$, hence $(a+8)^4\geq a^5$, this show $a\leq 15$. Now you can finish using the point 2) of the answer of @azimut, using for $a=1$ the fact that the exponent of the prime $5$ is $1$ in the product $a(a+1)...(a+8)$, for $a=2$, the prime $7$, etc.

$\endgroup$
  • $\begingroup$ (+1) nice! You could also use the stronger $A \leq (a+5)(a+6)(a+7)(a+8)$ and $B \geq a(a+1)(a+2)(a+3)(a+4)$ to directly arrive at $a \leq 5$. $\endgroup$ – azimut Oct 14 '15 at 9:09
  • $\begingroup$ @azimut Yes, You are true; I have only given the idea. But It works for $9$, but not for $8$ for exemple, Your proof seems to be more general (+1). $\endgroup$ – Kelenner Oct 14 '15 at 9:19
  • 1
    $\begingroup$ @azimut Did you arrive at $a \leq 5$ from your inequalities by trying various values for $a$, or is there a more general approach? $\endgroup$ – Lawrence Oct 14 '15 at 11:58
  • $\begingroup$ @Lawrence: I just plugged in a=1, a=2, ... $\endgroup$ – azimut Oct 14 '15 at 12:47
  • $\begingroup$ .... so a = 1, 2, 3, 4, 14 or 15. However there are two multiples of 7 so either a and a+7 are multiples of seven or a+1 and a + 8 are. So a = 14. But 14.... 23 include the single primes 17, 19 and 23. So impossible. Nice! $\endgroup$ – fleablood Oct 15 '15 at 16:44
1
$\begingroup$

OK, here is my second attempt at answering the question. Again, the language is not entirely math-eese. I don't see any way to make Venn diagrams with MathJax either and I mark some proofs of simple Lemmas as trivial rather than go through the elementary steps to show they are true. If you really want to spell them out you can.

The proof of the Theorem would go something like this ....

Definition 1 : Let Sn be the set of 9 consecutive integers starting with n.

Definition 2 : Let Tn be a partition of Sn into two subsets, A and B, of Sn.

Definition 3 : Let Ap and Bp be the products of the elements of A and B respectively.

Theorem : There does not exist any Tn of any Sn for which Ap = Bp.

Proof : By contradiction. Assume Ap = Bp for some subsets A and B of some Tn of a Sn.

We then can set up a number of basic Lemma.

Lemma 1 : No element of Sn is divisible by any prime greater than 7.

Proof : If an element of Sn is divisible by a prime greater than 7, note that no other element of Sn can be divisible by the same prime since the closest other number divisible by the same prime would be more than 9 units away from the element divisible by that prime. Thus in partition Tn when that element would be placed into either subset A or subset B, Ap would not equal Bp. Contradiction.

Corollary 1 : Any element of Sn that is not the number 1 can only be divisible by 2, 3, 5 or 7.

Proof : Follows from Lemma 1.

Lemma 2 : There are exactly two elements of Sn that are divisible by 7.

Proof : Trivial.

Lemma 3 : There are exactly two elements of Sn that are divisible by 5.

Proof : Trivial.

Lemma 4 : There are exactly three elements of Sn that are divisible by 3.

Proof : Trivial.

Lemma 5 : There are either 4 or 5 elements of Sn that are divisible by 2.

Proof : Trivial.

Lemma 6 : If Sn contains the number 1 it must be S1.

Proof : Trivial.

Lemma 7 : Sn can contain at most three elements which are powers of two and divisible by no other prime.

Proof : If Sn contains four or more elements which are powers of two and divisible by no other prime then let the smallest be 2x and the largest be 2y. Then we have x>= 1 and y>=x+4 and the length of any set of consecutive numbers that contain them must be at least 2x+4-2x = 2x(24-1) = 2*7 = 28 which is too large for S.

Lemma 8 : If Sn contains three (and only three) elements which are powers of two and divisible by no other prime then Sn must be S1 or S2.

Proof : Trivial.

Lemma 9 : If Sn contains two (and only two) elements which are powers of two and divisible by no other prime then Sn must be S3, S4 or S8.

Proof : Trivial.

Now that we have our Lemmas, on to the proof. Let's make a Venn diagram for the elements of Sn consisting of three circles; one for elements divisible by 3, one for elements divisible by 5 and one for elements divisible by 7. Now, either these three circles are completely disjoint or they overlap somewhere. Let's look first at the case where they are completely disjoint.

Note that I don't see any way to make Venn diagrams in this post using MathJax so I'll just make boxes using dashes and such.

      -----7-----       -----5-----     -----3-----
     |    x   x  |     |   x   x   |   |   x x x  |         x  x
     ------------      -------------    -----------

Note we can now make two more Lemmas.

Lemma 12 : The number 1, if it's an element of Sn will be outside the circles, as will any element that is strictly a power of two.

Proof : From Lemma 1, Corollary 1 and the Venn diagram.

Lemma 13 : Any element outside the circles must either be the number 1 or else a power of two that is not divisible by any other prime.

Proof : Since any element of Sn can only be divisible by 2, 3, 5, or 7 and the elements outside the the circles are not divisible by 3, 5 or 7 the only number they can possibly be divided by is 2. The only numbers that qualify are powers of 2 and the number 1 itself.

Note that Lemma 13 then forces the two elements outside the circle to be either 1 and an element which is a power of 2 or else two elements that are powers of 2. If one of them is the number 1 then S must be S1 (by Lemma 6). But S1 only has one element that is divisible by 7, so it can't satisfy the assumptions. So the two elements outside the circles must both be elements that are powers of 2 with no other prime divisor. By Lemma 9, S must then be either S3, S4 or S8. However, none of these have two elements which are divisible by 7. Therefor no S can satisfy the condition where the Venn circles are disjoint. So they must overlap if our assumption is to hold.

Note however that if we overlap the circles, we force more elements outside the circles since Lemmas 2, 3 and 4 limit how many can be in each one of them. For example, if an element is divisible by both 3 and five, our diagram loses an element when we overlap the circles.

      -----7-----       -----5-------------3-----
     |    x   x  |     |   x      |  x  |   x x  |         x  x
     ------------       -------------------------

It can't go in the circle for elements that are divisible by 7. That would violate Lemma 2. So it must go outside the circles.

      -----7-----       -----5-------------3-----
     |    x   x  |     |   x      |  x  |   x x  |      x   x  x
     ------------       -------------------------

Note that Lemma 7 and Lemma 13 limit us to moving more than two elements outside the circles to join the other two already there. So we have only two scenarios when the the circles overlap. Either there are three elements outside the circles or else there are 4.

If there are three elements outside the circles they either include 1 or they don't. If they do include 1 then S can only be S1 (Lemma 6). If they do not include 1 then all three elements must be powers of two. By Lemma 8 then S can only be S1 or S2. Thus the only S that can have three elements outside the circles when the circles overlap are S1 and S2. Note however that neither S has two elements which are divisible by 7. Contradiction.

So there must be four elements outside the circles if they overlap. In this situation also they either include 1 or they don't. If they do then by Lemma 6, S must be S1. If they do not include 1 then all four are powers of two. But this would contradict Lemma 7. So S can only be S1 when there are four elements. As noted above however this does not have two elements divisible by 7. So there can't be four elements outside the circles.

Thus none of the scenarios admit any solutions. The assumption must be false. Hence the theory must be true. QED.

$\endgroup$
0
$\begingroup$

Not exactly in math-eese but I'm on my lunch break and using an iPhone so here goes.

Let's refer to the numbers as N(0) through N(8). The residue of N(0) modulus 3 is either 0,1 or 2. So we have three cases.

If the modulus is 0 then N(0) is divisible by 3. So then too N(3) and N(6) are divisible by 3. Call them the d3 subset of the larger set.

If you partition the larger set into subsets A and B then one of them is going to contain an even number of the members of the d3 subset (0 or 2 of them) and the other will contain an odd number of the members of d3 (3 or 1 respectively). So you have two cases for the partitions.

In either of those cases one partition set's member product (either A or B) will be divisible by 9 and the other set's member product won't. So they can't be equal, and thus that situation can't occur.

By similar reasoning when the modulus of the first number is 1 then d3 will still contain an odd number of numbers divisible by three (in that case N(1), N(4) and N(7)) and the same result happens.

Same thing for when the modulus is 2 where d3 will contain N(2), N(5) and N(8).

Thus the answer is no, 9 consecutive integers can't be partitioned into two sets whose member products are equal.

The same thing happens whenever there is an odd number of elements in d3. In general when you have 6x+9 consecutive integers they cannot be partitioned into two subsets whose member products are equivalent.

$\endgroup$
  • 1
    $\begingroup$ Doesn't work. Two of the multiples of 3 will not be multiples of 9 and 1 will be. One set will have the multiple of 9 and the other set will have the other two remaining multiples of 3. $\endgroup$ – fleablood Oct 14 '15 at 18:01
  • $\begingroup$ Doh! You're right. Ok, I have a new proof that splits the problem isn't 8 distinct situations. Each situation either has no solution or else has one or two possible solutions but the solutions run into other contradictions that negate them from working. I'll write it up and post it soon. Hopefully it will pass muster better than this one. $\endgroup$ – David A. Oct 15 '15 at 16:24
  • $\begingroup$ I've got a few thoughts that never gelled. The first number must be a even number with an odd power of two as highest 2-power divisor. the number before the first and after the last must be an odd multiple of 11. The first and eighth or the 2nd and the 9th must be divisible by seven. The fifth can not be multiple of 5. The first number must be 1,2,3or 4 mod 13. The last bit somehow means the product of the 9 numbers cant be a square but I don't see that ... so I got very little more than nothing. $\endgroup$ – fleablood Oct 15 '15 at 16:32
0
$\begingroup$

Damn, I need more coffee: The following answer is going to kill my reputation as it's very idiotically not correct. !!!SHEESH!!! I'm prone to careless errors, but this one is a real doozy in carelessness...

So, my answer. !! WRONG !!!

===============

Um, wouldn't it be easiest to say that any 9 consecutive integers will have one and only one multiple of 5?

Thus the multiple five will be in one set and it's product will be a multiple of 5, and the other set will not have any multiples of 5 and its product will not be a multiple of 5.

$\endgroup$
  • 1
    $\begingroup$ That's not true, e.g. $\{ 5,6,7,8,9,10,11,12,13 \}.$ $\endgroup$ – CIJ Oct 14 '15 at 17:08
  • $\begingroup$ Yes, that has to be one of the most stupid careless errors I've ever made. blushing beet red $\endgroup$ – fleablood Oct 14 '15 at 17:10
  • 1
    $\begingroup$ Just delete your answer if you think it is not up to your standards. There's no shame in that. $\endgroup$ – guest Oct 14 '15 at 17:16
  • $\begingroup$ I haven't actually finished completing my account so I can't delete answers. I don't mind having a stupid answer public. Keeps me humble. And wrong answers (as long as they aren't misleading) can be a learning experience. $\endgroup$ – fleablood Oct 14 '15 at 17:28

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.