# Combinations problem, 2 variables

${}^xC_4-{}^yC_4=425$; find $x+y$

I can’t figure out if this is just a guess or check or if there is an efficient way to solve this, any help would be greatly appreciated.

• By computer, the solution is $x=12, y=8$ so $x+y=20$. – B. Mehta Dec 22 '17 at 0:03
• @B.Mehta yeah that's the answer in the key I do believe that's correct – Nick Brown Dec 22 '17 at 0:13

Closely related to Michael's approach: There's a curious fact that the product of four consecutive integers is always one less than a square - in particular $x(x-1)(x-2)(x-3) = (x^2 -3x+1)^2-1$, so we can write down that $$\binom{x}{4} - \binom{y}{4} = 425 \iff(x^2 -3x+1)^2-(y^2-3y+1)^2=10200.$$ This factors using the difference of squares, giving $$(x^2- y^2-3x+3y)(x^2+y^2-3x-3y+2)=10200.$$ However, the expression $t^2 - 3t + 1$ is always odd for any integer $t$, so both parentheses above are the sum or difference of odd integers, hence must both be even. So, we are searching only for pairs of even divisors of $10200$, (that is, divisors of $2550 = 10200/4$) of which there are only $12$, I've shown the divisors of $2550$ here: $$(1,2550),(2,1275),(3,850),(5,510),(6,425),(10,255),(15,170),(17,150),(25,102),(30,85),(34,75),(50,51)$$

Each of these gives a possibility for the tuple $(x^2-3x+1, y^2-3y+1)$ which could work, and it only remains to check which of these are in fact expressible in that form: $$(2551,2549),(1277,1273),(853,847),(515,505),(431,419),(265,245),(185,155),(167,133),(127,77),(115,55),(109,41),(101,1)$$

Staring at $x^2 - 3x + 1$ for a while, you may notice it is one less than twice a triangle number, in particular $(x^2 - 3x + 1) + 1 = (x-1)(x-2) = 2T_{x-2}$, and it is not hard to prove that $n$ is triangular $\iff$ $8n+1$ is a square. So, some integer $n$ is expressible in the form $x^2 - 3x + 1$ $\iff$ $4(n+1) + 1 = 4n+5$ is a square.

Applying $4n+5$ to the possibilities above (and starting from the end because $x^2 - 3x+1$ should space out more for higher $x$, so $(2551, 2549)$ is unlikely to both work), we notice $(109, 41)$ works, giving $x=12$, $y=8$.

• Very elegant solution, but I'm a bit lost on the part towards the end, what is it exactly that you are defining as n? And then what do you mean by 8n+1 is a square? – Nick Brown Dec 26 '17 at 18:08

The hint:

$$x(x-1)(x-2)(x-3)-y(y-1)(y-2)(y-3)=$$ $$=(x-y)(x+y-3)(x^2+y^2-3x-3y+2)=24\cdot425$$ and number of cases.

• I did manage to get that far, but as you can't solve for a single variable to set up a table, I'm still stuck there. – Nick Brown Dec 22 '17 at 0:12
• @Nick Brown The numbers of divisors of $2^3\cdot3\cdot5^2\cdot17$ is not so big. – Michael Rozenberg Dec 22 '17 at 0:20
• @NickBrown Now theoretically the problem is reduced to a large (but finite) number of computations. Since $x, y$ are integers, $(x-y), (x+y-3), (x^2+y^2-3x-3y+2)$ are integers too, and they have to multiply to $24 \cdot 425$. Thus it is possible that $(x-y)=1$, $(x+y-3)=24$, and $(x^2+y^2-3x-3y+2)=425$. Or it is possible that $(x-y)=4, (x+y-3)=6$, and $(x^2+y^2-3x-3y+2)=425$. I will be many cases, but finitely many. And you can probably find some tricks to greatly reduce the ammount of work. – Ovi Dec 22 '17 at 0:20
• @MichaelRozenberg How did you factor $x(x-1)(x-2)(x-3)-y(y-1)(y-2)(y-3)$? I can see that $y$ is a root of $f(x)=x(x-1)(x-2)(x-3)-y(y-1)(y-2)(y-3)$, but then is still much work to factor $(x+y-3)(x^2+y^2-3x-3y+2)$? Did you notice that $x=3-y$ is a root also? – Ovi Dec 22 '17 at 0:23
• @Ovi It must be the factor $x-y$. After this we get a symmetric polynomial and after substitution $x+y=2u$ and $xy=v^2$ we can get this factoring. – Michael Rozenberg Dec 22 '17 at 0:28