24
$\begingroup$

Some maths to usher in the New Year!

Find distinct integers $a,b,c,d,e,f,g,h$ such that $$\color{purple}{\binom ab+\binom bc}+\color{blue}{\binom cd}+\color{green}{\binom de+\binom ef}+\color{orange}{\binom fg+\binom gh}=\color{red}{2018}$$ and where $a>b>c>d>e>f>g>h\ge 0$, and one of the binomial coefficients is $$\color{red}{\binom {20}{18}}$$

Alternatively, in summation form:

Find distinct integers $x_1, x_2, \cdots, x_8$ such that $$\color{orange}{\sum_{n=1}^7}\color{orange}{\binom {x_n}{x_{n+1}}}=\color{red}{2018}$$ and where $x_n>x_{n+1}\ge0$ and, for one particular value of $n$, $$\color{green}{\binom {x_n}{x_{n+1}}}=\color{red}{\binom {20}{18}}$$ Happy New Year!

$\endgroup$
7
  • 2
    $\begingroup$ I think you should colour in the title like the one you did for Xmas :) $\endgroup$
    – TheSimpliFire
    Dec 31, 2017 at 16:23
  • $\begingroup$ @TheSimpliFire - Thanks for noticing! There is a 150-character limit on the title though :) $\endgroup$ Dec 31, 2017 at 16:27
  • 1
    $\begingroup$ +1 for adding colors on Matstackexchange...Heppy new year to you $\endgroup$ Dec 31, 2017 at 16:41
  • 2
    $\begingroup$ There are solutions where you can "null out" some of the terms by allowing the $x_n$ to increase, like $\binom{24}{23}+\binom{23}{20}+\color{red}{\binom{20}{18}}+\binom{18}{33}+\binom{33}{1}+\binom{1}{2}+\binom{2}{3}$. There are infinitely many such solutions; just take this one and change the $3$ to anything larger not already used. $\endgroup$
    – 2'5 9'2
    Jan 1, 2018 at 8:39
  • 1
    $\begingroup$ There are also solutions where one term is very large (too large), and then later negative terms cancel it out. Like $\binom{24}{20}+\color{red}{\binom{20}{18}}+\binom{18}{-8798}+\binom{-8798}{1}+\binom{1}{2}+\binom{2}{3}+\binom{3}{4}$. As with my last comment, there are infinitely many of these. $\endgroup$
    – 2'5 9'2
    Jan 1, 2018 at 8:45

2 Answers 2

11
$\begingroup$

One solution is $$ {20\choose 18} + {18\choose 15}+{15\choose 12}+{12\choose 8}+{8\choose 5}+{5\choose 4}+{4\choose 4}=2018. $$ I found this using a greedy algorithm: $x_1=20$, $x_2=18$, and for $n\geq 3$, $$ x_n=\min\left\{k\geq x_{n-1}/2:\sum_{i=1}^{n-2}{x_i\choose x_{i+1}} + {x_{n-1}\choose k}\leq 2018\right\}. $$

If we prefer distinct integers, we can replace ${4\choose 4}$ with ${4\choose 0}$.

$\endgroup$
2
  • $\begingroup$ Very nice! (+1) This is similar to my solution, except that the last two terms $\binom 51$ and $\binom 10$. The question should be modified to specify that the $x_n$'s are distinct. I'd be interested to see if there are other solutions, as $\binom {20}{18}$ is not necessarily the first term. $\endgroup$ Dec 31, 2017 at 16:49
  • $\begingroup$ There are so many degrees of freedom that it seems hard to believe there wouldn't be many solutions. For instance, one could just take $21\choose 20$ or $22\choose 20$ as the first term, $20\choose 18$ as the second, and then run the greedy algorithm again. $\endgroup$ Dec 31, 2017 at 16:54
10
$\begingroup$

A brute-force search finds the following 12 all-distinct-number solutions (in six nearly-identical pairs):

$$ \color{red}{\binom{20}{18}}+\binom{18}{15}+\binom{15}{12}+\binom{12}{8}+\binom{8}{5}+\binom{5}{4}+\binom{4}{0} \\ \color{red}{\binom{20}{18}}+\binom{18}{15}+\binom{15}{12}+\binom{12}{8}+\binom{8}{5}+\binom{5}{1}+\binom{1}{0} \\ \binom{23}{22}+\binom{22}{20}+\color{red}{\binom{20}{18}}+\binom{18}{17}+\binom{17}{15}+\binom{15}{11}+\binom{11}{9} \\ \binom{23}{22}+\binom{22}{20}+\color{red}{\binom{20}{18}}+\binom{18}{17}+\binom{17}{15}+\binom{15}{11}+\binom{11}{2} \\ \binom{23}{22}+\binom{22}{20}+\color{red}{\binom{20}{18}}+\binom{18}{16}+\binom{16}{14}+\binom{14}{13}+\binom{13}{8} \\ \binom{23}{22}+\binom{22}{20}+\color{red}{\binom{20}{18}}+\binom{18}{16}+\binom{16}{14}+\binom{14}{13}+\binom{13}{5} \\ \binom{23}{21}+\binom{21}{20}+\color{red}{\binom{20}{18}}+\binom{18}{16}+\binom{16}{13}+\binom{13}{9}+\binom{9}{5} \\ \binom{23}{21}+\binom{21}{20}+\color{red}{\binom{20}{18}}+\binom{18}{16}+\binom{16}{13}+\binom{13}{9}+\binom{9}{4} \\ \binom{25}{23}+\binom{23}{22}+\binom{22}{20}+\color{red}{\binom{20}{18}}+\binom{18}{15}+\binom{15}{3}+\binom{3}{1} \\ \binom{25}{23}+\binom{23}{22}+\binom{22}{20}+\color{red}{\binom{20}{18}}+\binom{18}{15}+\binom{15}{3}+\binom{3}{2} \\ \binom{25}{23}+\binom{23}{22}+\binom{22}{20}+\color{red}{\binom{20}{18}}+\binom{18}{16}+\binom{16}{14}+\binom{14}{4} \\ \binom{25}{23}+\binom{23}{22}+\binom{22}{20}+\color{red}{\binom{20}{18}}+\binom{18}{16}+\binom{16}{14}+\binom{14}{10} $$

These are all the solutions that contain $\binom{20}{18}$, assuming that the integers are strictly decreasing. The key is to observe that this is a finite problem: if $x_i = 20$ and $x_{i+1} = 18$, then $x_{i-1}$ (if it exists) can be at most $23$, since $\binom{24}{20} > 2018$, $x_{i-2}$ can similarly be at most $25$, $x_{i-3}$ at most $27$, and so on, so we can find all the solutions if we consider binomial coefficients $\binom nk$ with $k < n < 40$ or so.

$\endgroup$
3
  • $\begingroup$ Very nice solution! (+1). So there are at least 12 possible combinations. Or 6 pairs, considering the symmetry of the last term. Would be nice if $\binom {20}{18}$ is shown in red. $\endgroup$ Jan 1, 2018 at 5:17
  • $\begingroup$ It's shown in red now! And, unless I've made a coding mistake, these are all the possible combinations if we assume a strictly decreasing sequence of integers. $\endgroup$ Jan 1, 2018 at 7:52
  • $\begingroup$ Very nice pattern! $\endgroup$ Jan 1, 2018 at 13:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .