We put four numbers 1,2,3,4 around a circle in order. One starts at the number 1 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 21?
Solution
Let ai,bi,ci,di be the number of paths that end by 1,2,3,4 respectively and have the sum equal to i. These paths all start from 1. 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 We can visit 1 from 2 or 4, visit 2 from 1 or 3, visit 3 from 2 or 4, visit 4 from 3 or 1 then we have the following relations ⎩⎨⎧an=bn−1+dn−1bn=an−2+cn−2cn=bn−3+dn−3dn=cn−4+an−4 We have to calculate a21+b21+c21+d21. Denote un=an+cn and vn=bn+dn for n≥1 then we come to another relation {un=vn−1+vn−3vn=un−2+un−4 We also have u1=1,u2=0,u3=0,u4=1 and v1=0,v2=0,v3=1,v4=0. Then vn=vn−3+2vn−5+vn−7 and un=un−3+2un−5+un−7.
By putting sn=un+vn, we get sn=sn−3+2sn−5+sn−7 with s1=1,s2=0,s3=1,s4=1,s5=1,s6=3,s7=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 Therefore, we have 167 paths such that the sum of numbers on these paths is equal to 21.
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.