9
$\begingroup$

Here is a hexagonal tiling, borrowed from Wikipedia.

hexagonal tiling

I start in any hexagon on the left hand side. I end at any hexagon on the right hand side. I can only travel to the right, not up, down or backwards.

In how many ways can this be done?

$\endgroup$
  • $\begingroup$ bonus question: if the grid is extended to $2k$ columns in total, what is the sum of the $2k^{th}$ column? $\endgroup$ – JonMark Perry Oct 30 '18 at 12:44
16
$\begingroup$

The answer is

74280

Method

Every cell in the first column can be reached 1 way.
Other cells can be reached as many different ways, as the sum of their two left neighbours, giving:
enter image description here
The sum of the numbers in the last column is the answer to the question posted.

$\endgroup$
  • $\begingroup$ I think I might give this the tick for the presentation aspect and the right answer. The bottom row is A001700. $\endgroup$ – JonMark Perry Oct 30 '18 at 12:49
  • 5
    $\begingroup$ @JonMarkPerry, actually it isn't. The sequences start to differ from the 2*12=24th column, when the diagonal hits the top/bottom. $\endgroup$ – elias Oct 30 '18 at 13:06
4
$\begingroup$

The correct answer might be:

73392?

Reasoning:

Well, I made a Pascal's Triangle-like chart with alternating 11 and 12 columns, and 14 rows, where each number was the sum of the two numbers northwest and northeast of it. I added all of the numbers on the bottom row. It's quite likely I messed up some addition, though.

$\endgroup$
  • $\begingroup$ The method seems to be correct, but I'm afraid your calculation is flawed indeed. $\endgroup$ – elias Oct 30 '18 at 12:22
  • $\begingroup$ @elias yeah, I thought that would be the case. $\endgroup$ – Excited Raichu Oct 30 '18 at 12:22
  • $\begingroup$ Also I'm sure you meant northwest and southwest instead of northeast. $\endgroup$ – elias Oct 30 '18 at 12:24
  • 1
    $\begingroup$ @elias I did the chart vertically instead of horizontally like the question asked (same result, and easier for me to draw), so for me it was northeast. I see how this could cause a bit of confusion though. $\endgroup$ – Excited Raichu Oct 30 '18 at 12:27
0
$\begingroup$

Answer:

$83,746$

Method:

Consider the first 2 columns of this diagram. There are 11 starting positions, and 12 destinations. Each starting position can go to one of 2 destinations, so the number of possible paths is equal to $11 \cdot 2 = 22$.

Now, consider columns 2 and 3 of the diagram. There are 12 starting positions, and 11 destinations. 10 of the starting positions have 2 possible destinations, and 2 of them only have 1 possible destination (the top and bottom ones). This means the total number of possible paths is $(10 \cdot 2) + 2 = 22$.

If we now consider the first 3 columns, it can be seen that each of the internal starting positions has 4 possible paths, and the top and bottom ones have 3. Therefore, in total, there are $(9 \cdot 4) + (2 \cdot 3) = 36 + 6 = 42$ possible paths across the first 3 columns.

In the initial consideration, the inner hexes were each finished on twice, and the outer ones once. Therefore, a second way to work out the number of paths in the third consideration, would be to edit the calculation for consideration 2 to be $((10 \cdot 2) \cdot 2) + (2 \cdot 1) = 40 + 2 = 42$.

Next, considering the first 4 columns, each of the paths already determined for the first 3, has 2 more possible destinations, so the number of paths would total $42 \cdot 2 = 84$.
Using these values, I can determine a formula for calculating the number of paths, where n increases by 1 for every repeating pair of columns.
$\Sigma_n = ((\Sigma_{n-1} - n) \cdot 4) + 2n$

Therefore, we can step through this calculation to determine the results of:
$\Sigma_1 = 22$
$\Sigma_2 = 84$
$\Sigma_3 = 330$
$\Sigma_4 = 1312$
$\Sigma_5 = 5238$
$\Sigma_6 = 20,940$
$\Sigma_7 = 83,746$
As there are 7 pairs of columns in the above image, (if my formula is correct), I believe there to be $83,746$ possible paths.

Bonus Question:

$\Sigma_n = ((\Sigma_{n-1} - n) \cdot 4) + 2n$ where $n=2k$

$\endgroup$
  • 3
    $\begingroup$ I'm pretty sure @NudgeNudge 's earlier answer of 90112 is an upper bound for the answer. $\endgroup$ – Excited Raichu Oct 30 '18 at 12:19
  • $\begingroup$ @ExcitedRaichu you're right, I think I had an unnecessary factor of n $\endgroup$ – AHKieran Oct 30 '18 at 12:47

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.