announced : 1/23/02
max points: 4
max solutions accepted : 20 (status : Closed as of 2/4/02)
no of correct solutions till now : 5

Statement :
In the group of 6 people, each pair
of people consists of two friends or two enemies
show that there are either three mutual friends
or three mutual enemies in the group.

Restatement:
In such a setting, if there is no friend triangle then there is an enemy triangle.

Clarifications :
Given six people A,B,C,D,E,F there are 15 pairs (how?) of the kind AB, DF, BC ,...etc. Each of these 15 pairs is either and enemy pair or a friend pair. So there are totally 2^15 = 32,768 ways the friendships could be among the people A,B,C,D,E,F . You have to show that no mater whatever way (out of these 32,768) the friendships are, you can find a group of three people (say A,B,C) such that all of them are friends of each other (i.e. AB,BC,AC are all friends relations) or there is a group of three people (say A,C,E) such that all of them are enemies of each other
(i.e. AC, AE, CE are all enemy pairs).

Example:
Let's say AB, BC, CD, AD, DE, EF, AF, BE, CF are friendly pairs and rest of the six pairs are all enemies.
Then in this setting are there any three people who are all mutually friends. the ans is NO. but then there are
3 people A,C and E who are all mutually enemies.

Hints:
Not yet.

Given n points in a plane, a line which passes through exactly any two of these, is called a simple-line. Prove that if these points are not colinear, then there exists a simple-line.

Restatement : If there is no simple-line then all the points are colinear.
Clarification : Colinear set of points is those which fall on the same straight line.

Hint : A little bit of geometry would help. e.g. Notion of distance of a point from a line.
Well-ordering property of section 3.2 might help and proof by contradiction in section 3.1 also might help.

Statement
Given the set of following premises, determine whether each of the conclusion which
follow are true or not. Prove your answer.

 If I have a cold then I also have fever. If I have fever then I
   need medicine to get well. If the weather is bad I get a cold.
  To get medicine I need to visit the doctor. To visit the doctor I
  need to use public transport. If the weather is bad there is no
  public transport. If I am not well then I cannot attend classes.

  Conclusion: 1. If the weather is bad I cannot attend classes.
              2. If I have fever then I cannot get well.

clarifications/comments:
Make no other assumptions. Write clean proofs.
For falsifying a conclusion you need to come up with
a set of situation which is consistent with  premises
and falsifies the conclusion (i.e. truth assignment)

Given, (3^n-3)/2 coins all but one of them have the same weight. The odd one can be heavier or lighter than the rest. Show that one can find out this fake coin and decide whether it is heavier or lighter, using n weighings on the equi-arm balance.

clarifications:
You can place group of coins in left as well as right pan of the balance. And the balance can give you three possible answers: left is heavier, both equal, right is heavier.

The following hints might help:
1> Try and work out the cases n = 2 i.e. 3 coins and 2 weighings and n=3 i.e. 12 coins and 3 weighings.
2> Use proof by induction for the general case.
3> Additinally if you can prove one of these, it might help in proving the main problem:
    a> If it is known whether the odd coin is heavy or light,  in n weighings the odd coin can be found out among 3^n coins.
    b> If you are given an extra Normal coin then, in n wieghings the odd coin can be found out among (3^n-1)/2 coins.

Only genuine self-solved answers please. If I doubt that you have copied it from somewhere I may ask you some additional questions to verify, if you have solved it yourself or not.

Matchstick Game:
Given n matchsticks on the table. Two persons A and B play the following game. A starts the game.
1> A cannot pick all the matchsticks in the first chance.
2> If a in previous turn the opponent picks x sticks, then the player playing next can lift any number from 1 to 2x of sticks.
3> The person who picks the last stick wins.

Problem:
Assume A and B are intelligent enough. Prove A wins if and only if n is not a fibonacci number.

Alternatively, write a program, where computer(your program) is player A and user is player B. User inputs the initial number of matchsticks. If it is not a fibonacci number, the computer beats the user, if it is a fibonacci number
then computer can simple give up saying " hey, it is a fibonacci number I have to start with so even if I win it will be due to your mistakes, so I give you this game." Or if you want you can make computer play and try to possibly win even in unfavorable case. You can write the program inany language you prefer. You should submit the code as well as executable by email.