given 9 consecutive naturals, no partition into two sets will give set one product = set two product

95 Views Asked by At

I know another user already asked this but I want to do another approach.

Can we list the numbers as $y, y+1, y+2, y+3, y+4, y+5,y+6,y+7,y+8$ and go case by case

for the partition into a set with $8$ elements another set with $1$ element:

Say the element in the set with one element is $y+x_0$ (where $x_n$ is an integer less than nine and greater than or equal to zero)then select a integer in the other set directly below or above $y+x_0$ which gives:

$(y+x_1)(y+x_2)(y+x_3)....(y+x_7)=\frac{(y+x_8)}{y+x_0}$ and clearly $\frac{(y+x_8)}{y+x_0}$ is not an integer while the other side is. since $y+x_8$ is not divisible by $(y+x_0)$ as their difference is only $1$.

Can we expand this argument for other partitions like 4-5 partion?

This problem is from my Putnam book: Putnam and Beyond

1

There are 1 best solutions below

2
On BEST ANSWER

Assume we can partition the set of $9$ consecutive positive integers into two disjoint subsets with equal product. By the Pigeonhole Principle, one of the two disjoint subsets has atleast $5$ elements. The minimum product of the subset with atleast $5$ elements has product $\geqslant y(y+1)(y+2)(y+3)(y+4)$. It then follows that: $$y(y+1)(y+2)(y+3)(y+4) \leqslant (y+5)(y+6)(y+7)(y+8)$$ Now, we know that the product of the nine consecutive positive integers is a square, and is divisible by $7$. Thus, it has to be divisible by $7^2$ forcing $y+8 \geqslant 14 \implies y \geqslant 6$. You can simply check that the above inequality does not hold when $y=6$, and thus will also not hold for any $y \geqslant 6$. This gives a contradiction, that proves the required claim.