Maybe you remember that back in January 2003, I offered you an increasing function that met two criteria (click the problem archives to see it). This month, I will challenge you with another increasing function that meets two criteria...
Let f map positive integers to positive integers with the conditions:
Remove any two elements, say a and b, from A1776, and replace them with the single number ab+a+b to form set A1775.
Continue in this manner, until you have performed 1775 such operations, to form set A1, which contains a single element.
(Part A): There are 100 people in a ballroom. Every person knows at least 67 other people (and if I know you, then you know me). Prove that there is a set of four people in the room such that every two from the four know each other. (We will call such a set a "clique.")
(Part B): Two people in the room are Joe and Grace, who know each other. Is there a clique of four people which includes Joe and Grace?
(Part C): Oops, I miscounted. There are actually 101 people in the room, But it's still true that each knows at least 67 others. That can't make a difference, can it?