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$ Jan 19, 2021 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, 2021 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$ Jan 19, 2021 at 16:07

2 Answers 2

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$ Jan 19, 2021 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$ Jan 19, 2021 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$ Jan 19, 2021 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, 2021 at 8:27

You must log in to answer this question.

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