3
$\begingroup$

So I have an hexagon and I start at point 1 and I can only move right or left, I need to find the formula to reach the same point within n steps, Assuming I have an odd number of steps allowed, I can't ever return to the point.
But assuming I have even steps, I'm not sure how do I even think about it, I divided by two because I can go from 1>>2 or from 1>>6 so it's easier to just look at it as if i started with 1 step right.
This means that if the sequence is $ a_n $and I took a step right now i have $ a_{n-1}$ steps to come back. how do I go on from here?

$\endgroup$
3
  • 2
    $\begingroup$ Try working with the number of ways to reach each of the six points after $n$ steps (so six variables) - there is a left-right symmetry which will help. Sometimes it is easier to make a problem look more complicated before simplifying. This way you record and control all the data. $\endgroup$ – Mark Bennet Jan 19 at 10:12
  • 2
    $\begingroup$ Since you have made the realisation that you need an even number of steps, you can also think about moving around the hexagon two steps at a time though. This reduces your problem to moving around a triangle, where you may choose not to move at each 'double-step'. You have to take care however, since there are two ways to choose not to move. $\endgroup$ – GossipM Jan 19 at 10:38
  • $\begingroup$ Thank you for the guidance, I realize the mistake was going to $ a_{n-1} $ instead of $a_{n-2} but does it not complicate it even more? Im not sure if i can solve a polynomial of higher degree if i have to take another sub-sequence for it $\endgroup$ – Danny Blozrov Jan 19 at 16:07
4
$\begingroup$

Another approach:

While the situation is simple enough to describe it the way you did, I think the context of a walk on a graph naturally arises here: your graph is the (undirected) $6$-cycle. Let $A$ be its adjacency matrix, finding the number of ways to start from a given point $i$ and end at $i$ in $n$ steps is just the number of paths with length $n$ from $i$ to $i$. That number is given by computing $B = A^n$ and looking at $b_{ii}$.

Here $A$ is known: $$A=\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 \end{bmatrix}$$

$A$ is diagonalisable, making it possible to find a "simple" closed form for $A^n$. In the end, the result you are looking for is: $$\frac{1}{6}\left (2(1+(-1)^n) + 2^n + (-2)^n \right)$$

However, as you noticed that for odd $n$, the result is always $0$, you can spare yourself some work and look directly at $A^2$ and find that the formula is $\frac{2^n + 2}{3}$ for even $n$.

$\endgroup$
2
  • $\begingroup$ Thank you for the explanation, unfortunately I haven't learnt matrix diagonalisation so I didn't really catch how you got that part. As for the matrix itself you just took all the combinations where there is a 0 in between two steps? $\endgroup$ – Danny Blozrov Jan 19 at 14:40
  • $\begingroup$ OK. As regards how $A$ is obtained, it is the adjacency matrix of the 6-cycle. Put simply, $a_{ij}$ is the number of ways to go from node $i$ to node $j$. You can check that this matrix indeed describes the hexagon you mentioned. If you haven't learned diagonalisation, the basic idea is to decompose $A = PDP^{-1}$ with $P$ an invertible matrix and $D$ a diagonal matrix (making it much easier to find the $n$-th power of $A$). If you have not learned about it, then, a more traditional combinatorial approach is probably what is expected here. $\endgroup$ – Bill O'Haran Jan 19 at 18:14
2
$\begingroup$

I think I have a solution (although not a closed-form) for the general $N$-gon. Suppose we write out our sequence of moves as a list of $n$ letters, either $L$ or $R$ (for left and right). We want to count the number of possible lists of length $n$ where the number of $L$ exceeds the number of $R$ by a multiple of $N$.

This is done by choosing $k$ of these steps to be $L$ moves, such that the difference between $k$ and $n-k$ is an integer multiple of $N$. Hence, the total number of moves is $$\sum_{k\in S}\binom{n}{k}$$ where $S=\{0\leq k\leq n:n-2k\in N\mathbb{Z}\}$, which we can rewrite as $$k=\frac{n+mN}{2}$$ for all integers $|m|\leq n/N$. A closed form for this sum would clearly be desired however.

$\endgroup$
2
  • $\begingroup$ mind explaining how you got the sum part? I understood that the amount of total steps has to be equal to 0(modN) but when you chose K steps to the left out of all n steps in total ,how did you come up with $n-2k $ ? didn't we just over complicate it with all the new variables? $\endgroup$ – Danny Blozrov Jan 19 at 16:09
  • $\begingroup$ Apologies, I made a small typo which I've correct. What I mean is that the difference between $k$ and $n-k$ needs to be an integer multiple of $N$. Furthermore, even though we introduced this variable $k$, the set $S$ is determined quite easily given any $n$ and $N$, and hence the number of steps can be calculated. $\endgroup$ – GossipM Jan 20 at 8:27

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.