Given n people, each of whom can make m friends among them. Write a function to tell whether it's true for any n and m.
Analysis:
First of all, n should be larger or equal to m+1.
Divide n people into k = [n/(m+1)] groups. Any person makes friend with the rest of the group, so that all people in these k groups have m friends.
Let's take a look at the p = n%(m+1) people not in these k groups. Let's call them W. They can make p-1 friends with each other in W, and totally they need r = (m-(p-1))*p more friend to satisfy the requirement.
Where can those r people come from? Suppose a group A is among k groups. If m == 0, obviously the requirement is satisfied. So we can assume m > 0 and A has at least 2 people. Suppose A1 and A2 are 2 people from A. Let them break up and make new friends in W, which contributes 2 friends to W. So, if the number r is odd, it's impossible to satisfy the requirement.
What if r is an even number? The answer is YES. Let's prove that.
r = (m-(p-1))*p = p*(m+1-p) <= p*(m+1)
For the group A, if all people break up, they can totally contribute p*(m+1) friends to group W, which is larger or equal to any r. That means, if we repeat the breaking-up process described above, we will finally get all people in group A and W to have m friends.
Actually, r = (m-(p-1))*p = m*p -(p-1)*p, since (p-1)*p is even, r is even if and only if m*p is even.
If m is odd, p = n%(m+1) is even if and only if n is even. That means, n*m is even if and only if m*p is even.
Finally, we come up with a very simple condition: it's true only if n*m is even.
