BdMO National Secondary (Higher Secondary) 2011/7

[Moon]

Problem 7:
Consider a group of $n > 1$ people. Any two people of this group are related by mutual friendship or mutual enmity. Any friend of a friend and any enemy of an enemy is a friend. If $A$ and $B$ are friends/enemies then we count it as $1$ friendship/enmity. It is observed that the number of friendships and number of enmities are equal in the group. Find all possible values of $n$.

[FahimFerdous]

I've solved it in a strange way. I'm not sure that I completely solved it. Please tell me if I'm wrong. And there are easier solutions. Please someone give me an easier one. Here's my solution:

There are n people in the group. Suppose that one of them is Mr. A. Now, we suppose that Mr. A has (x-1) friends. So, he must have (n-x) enemies. Now, the (n-x) people who are Mr. A's enemies are enemies of Mr. A's friends' too. Again, those people are friends among themselves. And the 'x' people including Mr. A are friends among themselves too.
So, the relation 'enmity' is in effect only among these 'x' and (n-x) people. Hence, the number of 'enmity' is x(n-x)=xn-x^2.
Now, we can say that, as there are n people in the group then the number of total relationships is n(n-1)/2. As 'friendships' and 'enmities' are equal, that means that ENMITY=TOTAL RELATIONSHIP/2.
So, x(n-x)=n(n-1)/4.
From this equation we can get that,
n=(n-2x)^2
or, n-2x=n^1/2
Now, from here I don't know if my logic is correct or not. My logic is, as n and x must be integers then (n-2x) is an integer too. Then the square root of n must be an integer. Which means that n must be a PERFECT SQUARE. Now, we've to think that, if we use any square number instead of n, then is x gonna be an integer? Cause if for some square numbers x is not an integer, then those numbers can't be the value of n. So, if n is a square then the square root of n must be an integer. And if n^1/2 is an integer, then (n-2x) is also an integer. Hence, x is an integer too. So, for every square number it's true. So the values of n can only be square numbers.

Is my solution correct? I have doubt on my solution. It's quite complicated. :-s

[Mehfuj Zahir]

Your solution is right.for more easy thinking Let $n=x+y$ where all the members of $x$ are friend to each other.And also all the members of $y$ friend to each other.So any members of $x$ is enemy with any members of $y$.
We have also that the number of friendship and enmity is equal.
$\displaystyle \binom {x}{2}+\binom {y}{2}=xy$
$\Longleftrightarrow x(x-1)+y(y-1)=2xy$
$\Longleftrightarrow x^2-x+y^2-y=2xy$
$\Longleftrightarrow x^2+y^2-2xy=x+y$
$\Longleftrightarrow (x-y)^2=n$
So any perfect square should be the ans.

[Avik Roy]

Fahim, your strange proof is correct.
However, you should note one thing here (though I'm sure you are just good enough at recognizing it). For the completeness of the proof, you should also prove that friend of enemy and enemy of friend is an enemy. It seems trivial, but necessary.

[FahimFerdous]

Thanks, Mehfuz vaia (I think you're senior to me )

Thanks, Avik da, actually it was so obvious that I didn't mention it. But you're right, to complete the proof I've to mention it.

[rakeen]

7. Here we’ll take each man as a point(shown in the figure). And the green lines as friendship and red lines as enemy. So adding all the points to make all sorts of possible lines we get C(n,2) lines. Analyzing two or three case we can find that total lines have to be an even number.

So, C(n,2) = 2k [k is element of N]

Solving that we can find that n has to be 4n or 4n+1 to make the desired result

[Mehfuj Zahir]

your proposition is not right.you can not say that analysis will always right.You need mathematical logic.The right answer was given before,Please check them

[sakib.creza]

x(C)2+y(C)2=xy

WHY? HOW?

[Phlembac Adib Hasan]

x(C)2+y(C)2=xy

WHY? HOW?

$\text{LHS=Total Number of Friendships}$
$\text{RHS=Total Number of Enmities}$

@Mehfuj vai, I think your solution is incomplete. You didn't show that all the squares satisfy the conditions.