Maths Olympiad Prep

Library / /64 of 155

Combinatorics Difficulty 5.8 AIME, harder Prove it Saudi Arabia

We put four numbers 1,2,3,41, 2, 3, 4 around a circle in order. One starts at the number 11 and every step, he moves to an adjacent number on either side. How many ways he can move such that the sum of the numbers he visits in his path (including the starting number) is equal to 2121?

Solution

Let ai,bi,ci,dia_{i}, b_{i}, c_{i}, d_{i} be the number of paths that end by 1,2,3,41, 2, 3, 4 respectively and have the sum equal to ii. These paths all start from 11. So it is easy to check that
a1=1, b1=c1=d1=0, a2=b2=c2=d2=0a3=0, b3=1, c3=d3=0, a4=1, b4=c4=d4=0 \begin{aligned} & a_{1}=1,\ b_{1}=c_{1}=d_{1}=0,\ a_{2}=b_{2}=c_{2}=d_{2}=0 \\ & a_{3}=0,\ b_{3}=1,\ c_{3}=d_{3}=0,\ a_{4}=1,\ b_{4}=c_{4}=d_{4}=0 \end{aligned}
We can visit 11 from 22 or 44, visit 22 from 11 or 33, visit 33 from 22 or 44, visit 44 from 33 or 11 then we have the following relations
{an=bn1+dn1bn=an2+cn2cn=bn3+dn3dn=cn4+an4 \left\{ \begin{array}{l} a_{n}=b_{n-1}+d_{n-1} \\ b_{n}=a_{n-2}+c_{n-2} \\ c_{n}=b_{n-3}+d_{n-3} \\ d_{n}=c_{n-4}+a_{n-4} \end{array} \right.
We have to calculate a21+b21+c21+d21a_{21}+b_{21}+c_{21}+d_{21}. Denote un=an+cnu_{n}=a_{n}+c_{n} and vn=bn+dnv_{n}=b_{n}+d_{n} for n1n \geq 1 then we come to another relation
{un=vn1+vn3vn=un2+un4 \left\{ \begin{array}{l} u_{n}=v_{n-1}+v_{n-3} \\ v_{n}=u_{n-2}+u_{n-4} \end{array} \right.
We also have u1=1, u2=0, u3=0, u4=1u_{1}=1,\ u_{2}=0,\ u_{3}=0,\ u_{4}=1 and v1=0, v2=0, v3=1, v4=0v_{1}=0,\ v_{2}=0,\ v_{3}=1,\ v_{4}=0. Then vn=vn3+2vn5+vn7v_{n}=v_{n-3}+2v_{n-5}+v_{n-7} and un=un3+2un5+un7u_{n}=u_{n-3}+2u_{n-5}+u_{n-7}.

By putting sn=un+vns_{n}=u_{n}+v_{n}, we get
sn=sn3+2sn5+sn7 s_{n}=s_{n-3}+2s_{n-5}+s_{n-7}
with s1=1, s2=0, s3=1, s4=1, s5=1, s6=3, s7=1s_{1}=1,\ s_{2}=0,\ s_{3}=1,\ s_{4}=1,\ s_{5}=1,\ s_{6}=3,\ s_{7}=1. By direct calculation, we have
s8=4, s9=5, s10=4, s11=11s12=8, s13=15, s14=22, s15=20s16=42, s17=42, s18=61, s19=94s20=97, s21=167 \begin{aligned} & s_{8}=4,\ s_{9}=5,\ s_{10}=4,\ s_{11}=11 \\ & s_{12}=8,\ s_{13}=15,\ s_{14}=22,\ s_{15}=20 \\ & s_{16}=42,\ s_{17}=42,\ s_{18}=61,\ s_{19}=94 \\ & s_{20}=97,\ s_{21}=167 \end{aligned}
Therefore, we have 167167 paths such that the sum of numbers on these paths is equal to 2121.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.