Puzzles #3

[serpretetsky]

If you already know the answer without working it out, please don't post it. Let others work it out.


1. Reposted shamelessly right from spikedmath:

2. Reposted shamelessly from the AMATYC math exam OCT/NOV 2009:

In how many ways can six computers be networked so that each computer is directly connected to exactly two other computers, and all computers are connected directly or indirectly?

 

[oraldlight]

a lot of them!

 

[Wiseguy2001]

Zero, the image is made up of squares.

 

[serpretetsky]

Ok, sorry been a little busy. For the 2nd problem i started drawing out a few examples

I immediately realized something. If every node needs exactly two other computers to connect to, and every computer must be directly or indirectly connected then we have basically created a single giant loop that every computer must be included in.

Using this logic, I decided instead of thinking about 6 static points and the different combinations to interconnect them, it might be a little easier to think of 6 static connections in the shape of a hexagon (like the last example in my picture) and all of the different combinations of computers you can put at the endpoints of the hexagon.

Ofcourse we have to be sure to count rotations of the same combination as only one combination.

 

[serpretetsky]

Using my above logic, I decided to lock one of the nodes in place, so that I don't treat simple rotations of my nodes as different combinations.
Doing that, there are only 5 different possibilies for the next node, only 4 possibilites for the next... etc.

So my final answer is there are 5!, or 120, different ways to connect 6 computers so that each computer has exactly two connections and every computer is connected together directly or indirectly.