**Solution**- Let the sequence be . For each position let be the length of the longest increasing subsequence starting with . Let be the length of the longest decreasing subsequence starting with . If and then there are only at most distinct pairs . Thus we have and for some . This is impossible, for if then and if then . Hence either some or .

**Solution**- Fix a person . Then has either 3 friends or 3 enemies. Assume the former. If a couple of friends of are friends of each other then we have 3 mutual friends. Otherwise, 's 3 friends are mutual enemies.