I got a different answer from Keith for Puzzle 111 (although they both share the nice property of being a power of 4 :) )

**Puzzle 111.**

To make a database we just need to define a set for every node in the graph and a set map for every edge. John defined the action of \$$F\$$ on the single node

$F(\textrm{Person}) = \\{\textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan}\\}$

So to define a database, all that's left to do is define a function

$F(\textrm{BestFriend}): F(\textrm{Person}) \to F(\textrm{Person})$

There are four distinct options for each person's best friend (assuming that a person can be their own best friend), so there are \$$4^4 = 256\$$ possible maps, and thus 256 possible databases!

**Puzzle 112.**

With the new restriction that your best friend's best friend must be you, we now have to check all our 256 databases to see which ones satisfy:

$F(\textrm{BestFriend}) \circ F(\textrm{BestFriend}) = 1_{\\{\textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan}\\} }$

In other words the one for which \$$F(\textrm{BestFriend}) \$$ is its own inverse. There are several ways of doing this.

- No one is their own best friend. There are 3 of these maps corresponding to the 3 ways to pair up the four people.
- Two people are their own best friend. There are \$${4\choose 2} = 6 \$$ of these maps.
- Everyone is their own best friend. There are 1 of these maps (it is the identity map).

And so there are 10 possible databases built on \$$\mathcal{D}\$$.

**Puzzle 113.**

If you are your best friend's best friend's best friend, then either you are in a best friendship triangle or you are your own best friend. There are two ways of doing this:

- One person is their own best friend and the other three people map to each other in a triangular loop. There are 4 ways to choose which person is the odd person out and 2 ways to choose the ordering for the triangular loop. So a total of 8 types of these maps.
- Everyone is their own best friend. There is 1 of these maps.

So there are a total of 9 possible databases.