1. Pathways
  2. Graphs, Networks and Algorithms
  3. Who's who?

Who's who?

Finger people

We can represent a group of friends by drawing a graph.
Each node represents a person.
An edge joins two nodes if and only if those two people are friends.

Here is a graph showing a group of friends.
Can you work out who's who using the clues below?

 
 

  1. Alan has 3 friends, Barney, Charlie, and Daniel.
  2. Barney and Ed are both friends with Charlie.
  3. Ed is Frank's only friend.



Here is a second network of friends.
Again, use the clues below to figure out who's who.

  

  1. Bella and Ciara are friends
  2. Emily and Ciara are not friends
  3. Bella is Fiona's only friend
  4. Anna has more friends than anyone else
  5. Daphne has three friends
  6. Gill and Daphne are not friends
  7. Emily has two friends


Once you've solved the two puzzles, here are some questions to consider:

Did each problem have a unique solution?
Were there any clues you didn't need to use?

If you label each node with the number of friends the person has, and add together all the numbers, what can you say about the answer? Can you explain why?

Can you design a puzzle with five friends, where some people have more than two friends, with a unique solution?

 

Comments

Submitted by Anonymous on Mon, 06/20/2016 - 01:38

In the top circle there is Alan, and to the left of him there is Daniel. That pathway stops. Then adjoining on the right from Alan there is Charlie, and to the left of Charlie there is Barney: who is also below Alan. To the next rights of Charlie there is Ed, who is next to Frank. That pathway stops there.

Submitted by Aristea on Mon, 06/20/2016 - 02:08

The node furthest to the left there is FIONA, who has only one friend; BELLA, which she is joined to by one line. Below and adjoining BELLA there is GILL; the only hint we have about him is that he is not friends with Daphne. To the right of Gill there is ANNA, who has the most friends, hence, the most lines coming from her node. To the right of Bella and across from Anna there is CIARA, and below Ciara there is Daphne. Below Daphne and Anna there is Emily. That is the whole friendship chain.

I obtained the answer by listing the information which was known and putting those people in the friendship chain first, then using the Guess and Check strategy to put the other people in. I also regularly looked back at the list of things I already knew, such as who's friends with who and who's not, to make sure I wasn't doing the wrong thing and potentially destroying the friendship chain.

Submitted by Aristea on Mon, 06/20/2016 - 02:18

If you label each node with the number of friends the person has, and add together all the numbers, what can you say about the answer? Can you explain why?

When all the numbers are added together, the sum is 20. This occurs because the nodes are in triangle patterns, and triangles have three sides (lines, in this case). There are seven nodes, and 7 * 3 = 21. You can see the shape on the far left is not a complete triangle, so we subtract one off our answer. This leaves us with 20.
Hence, 20.

Submitted by Taylah Zahner on Wed, 06/22/2016 - 00:21

GOT IT COMPLETED!

Submitted by bilva on Thu, 07/28/2016 - 09:27

I solved the first problem by using the information to form my own friendship chain.The second one seemed to be harder and i was not able to answer it.I showed it to my teacher and tried explaining it to him and in the process I unexpectedly got the answer.

Submitted by Lily on Sun, 02/05/2017 - 13:12

This is hard!! :)
but I like it!

Submitted by 555 on Mon, 03/13/2017 - 11:31

In the top circle there is Alan, and to the left of him there is Daniel. That pathway stops. Then adjoining on the right from Alan there is Charlie, and to the left of Charlie there is Barney: who is also below Alan. To the next rights of Charlie there is Ed, who is next to Frank. That pathway stops there.

Submitted by Anonymous on Wed, 04/12/2017 - 06:27

Please make more of these types of problems.