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

Question

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.

Answer 1

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.)

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.