4
$\begingroup$

essential diagram for question

Original Question: Students sit at their desks in three rows of eight. Felix, the class pet, must be passed to each student exactly once, starting with Alex in one corner and finishing with Bryn in the opposite corner. Each student can pass only to the immediate neighbour left, right, in front or behind. One possible path is shown. How many different paths can Felix take from Alex to Bryn?

So what confuses me about this question is typically this style of "how many paths" gives a more limited direction, e.g. only right and up towards the target. However, in this question, the students can pass left, right, in front, and behind. So the traditional method I usually use for these type of questions of counts on points wouldn't work (finding sum of number of ways to each point)? Or at least I think it doesn't work.

$\endgroup$
2
  • $\begingroup$ In the OEIS, the closest I can find is this, which requires that it starts at Alex, but doesn't require that it ends at Bryn, or this where Bryn is in the top left corner instead of top right. It's possible that your sequence is there, but in that case I completely missed it. $\endgroup$
    – Arthur
    Commented Apr 12, 2023 at 11:08
  • $\begingroup$ See this post. $\endgroup$
    – 138 Aspen
    Commented Apr 12, 2023 at 11:34

1 Answer 1

7
$\begingroup$

The answer is $2^{c-2}$ where $c$ is the number of columns. The trick is to notice the distribution of unconnected columns on the top and bottom row.

enter image description here

They are also visible in the middle row.

$\endgroup$
5
  • $\begingroup$ I don't understand. For $r=3$ rows, $2^{r-2}=2$ but there are obviously more than $2$ paths $\endgroup$
    – Taladris
    Commented Apr 12, 2023 at 11:48
  • 1
    $\begingroup$ There are only three rows. Do you mean unconnected columns? $\endgroup$ Commented Apr 12, 2023 at 11:49
  • $\begingroup$ I swapped rows and columns. I will correct it. $\endgroup$ Commented Apr 12, 2023 at 11:49
  • 1
    $\begingroup$ @Taladris If you want to start in the bottom left and end in the top right, and go through all points in the meantime, there are only two paths through a $3\times 3$ grid. $\endgroup$
    – Arthur
    Commented Apr 12, 2023 at 12:01
  • $\begingroup$ @Arthur: when I commented, $r$ was the number of rows. $\endgroup$
    – Taladris
    Commented Apr 12, 2023 at 13:53

You must log in to answer this question.

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