Spelling Beehive

[hross]

In the diagram below, how many unique paths are there that spell the word "KAYAK"?

*You may begin at any K and end at any K

*You may only pass from one letter to a letter in an adjacent hexagon

*Since KAYAK is a palindrome, each path has a corresponding path moving in the opposite direction -- count these as two separate paths!

*Each path must contain 5 different hexagons -- so, for example, you cannot use the same letter "A" twice in one spelling

[bonanova]

Looks like

  Reveal hidden contents

180 unique paths.

because

  Reveal hidden contents

The central K accesses 6 As.
Each of those As accesses 3 Ys.

Two of the Ys access 2 As each of which access 2 final Ks. (4 Paths)
One of the Ys accesses 2 As that each access 2 final Ks and one A that accesses 3 final Ks. (7 paths)
So the 3 Ys combined have 4+7+4 = 15 exit paths.

The central K thus has 6x15 = 90 unique exit paths.
Each path can be traversed in reverse order.

 

[CaptainEd]

I think we need to add some more, namely the paths that start and end in the outer layer. I can't give a spoiler using my iPhone, so I leave the answer as an exercise to the reader.

[phaze]

Dont forget the paths that start in the centre get to y and then come back

 

Edit: forgot you cant use that "K" Twice :Doh

Edited May 9, 2016 by phaze

[bonanova]

  On 5/8/2016 at 2:59 AM, CaptainEd said:

I think we need to add some more, namely the paths that start and end in the outer layer. I can't give a spoiler using my iPhone, so I leave the answer as an exercise to the reader.

Expand  

Good catch. It couldn't have been that easy.

The additional paths number

  Reveal hidden contents

120

because

  Reveal hidden contents

The additional paths begin and end on an outer K, including reversals.
Thus we only need count paths originating from the outside Ks.
Of the 24 outer Ks six lie, one each, on the center of the edges.
Call them Special Ks (with a nod to my one-time fave cereal.)
Call the others Ordinary Ks.

Paths from Special Ks reach their four nearest neighbors on each side.
Paths from Ordinary Ks reach their two nearest neighbors on each side.

So there are 120 outer-to-outer-K paths:

Originating on Special Ks: 6 x 8 = 48
Originating on Ordinary Ks: 18 x 4 = 72

Total paths = 180 + 120 = 300

 

[hross]

With your reasoning on the additional paths

  Reveal hidden contents

I like the idea of separating the Special Ks from the Ordinary Ks, but I don't think that all Ordinary Ks are created equal.

 

[CaptainEd]

Finally, got to my laptop, where I can use spoilers

Additional paths:

  Reveal hidden contents

Counting paths that don't get to the center K:
Let's call the cells on an outer edge
X Y Z Y X
There are
6 X, 12 Y, 6 Z
Starting with an X we can reach another K in the outer layer using 6 different paths

From a Y, 12 paths

From a Z, 6 paths

So the paths that don't go to the center are
6 x 6 + 6 x 12 + 12 x 6
=180

 

So, yes, Z are Special K, but as hross says, X and Y are different from each other.

 

Edited May 10, 2016 by CaptainEd

[hross]

I got different numbers for additional paths:

  Reveal hidden contents

Using CaptainEd's naming system, I also saw 6 of X, 12 of Y, and 6 of Z.

But when I counted the paths from each of these starting points to another K on the edge, I got

X = 4

Y = 9

Z = 12

Does this check out?

[CaptainEd]

Oops, I was double counting A's occasionally, and i have no idea how I missed all the paths from Zs. Now I buy your numbers, hross. As Bonanova said, it couldn't be that easy...

[Logophobic]

Counting paths on Y instead of K:

  Reveal hidden contents

There are 21 paths on each corner Y and 11 paths on each edge Y for a total of 192 paths. Since each path can be traversed in either direction, this gives 384 kayaks.

This agrees with the previous count of 180 including the central K, plus 204 excluding the central K.

 

[Buddyboy3000]

I agree with Logophobic. Finding the additional paths of KAYAK, you have 6 different patterns that can happen. Two are on the sides, and four are at the corners. In total, there are 102 different ones, doubled to get 204 paths. The patterns are different shapes that KAYAK can make on the edges. It is not really the mathematical way, but it works the same way.