It is fun going over all these nice, old problems.
Quote:
Originally Posted by ThePerfectHacker  I found this nice problem as an excercise in a math book. We can solve this by induction. |
Hey TPH,
I think we can do this only using PHP, without induction(it is in fact akin to galactus solution)
In the group of n people, The different possible handshakes for each person is
0,1,2,3....,(n-1).
Claim:
We note that
both 0 and n-1 together are not possible.
Proof:
Since handshake is symmetric, if there is a person with 0 handshake then nobody could have shook hands with this guy. Hence no one in the room would have shook hands with everyone. This implies "n-1" not possible.
However if "n-1" case has happened, then some body shook hands with everyone and therefore everybody would have shaken non-zero hands. So 0 is not possible!
That means "n-1" handshake choices for "n" people.
Apply PHP and wrap it up.
I think this argument is nice since it uses only PHP. We proved this result in graph theory using PHP itself!