0
$\begingroup$

${}^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.

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

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Nick Brown Dec 26 '17 at 18:08
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Nick Brown Dec 22 '17 at 0:12
  • 1
    $\begingroup$ @Nick Brown The numbers of divisors of $2^3\cdot3\cdot5^2\cdot17$ is not so big. $\endgroup$ – Michael Rozenberg Dec 22 '17 at 0:20
  • 1
    $\begingroup$ @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. $\endgroup$ – Ovi Dec 22 '17 at 0:20
  • $\begingroup$ @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? $\endgroup$ – Ovi Dec 22 '17 at 0:23
  • $\begingroup$ @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. $\endgroup$ – Michael Rozenberg Dec 22 '17 at 0: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.