Question

John has n acquaintances. He wants to meet 3 of them every day of 2018 for coffee at his home. What is the smallest value of n such that he can do this without calling the same set of three people more than once during 2018? Note that a person can come on multiple days, but never more than once with the same 2 other people. For the above n, we want to make a statement like “There is some acquaintance of John who came over at least m times”. What is the value of m given by the Pigeonhole principle?

Answer 1

Out of n acquaintences he has to choose any 3 for 365 days, ensuring that the same set of 3 people never repeat and visit again;

Thus, we have to find the least value of n such that nC3 >= 365

We start with a trial number 15;
15C3 = 15*14*13 *12! / 12! * 3! = 15*14*13/6 = 455 which is > 365

Then we check for n= 14
14C3 = 14*13*12*11! / 11! * 3! = 14*13*2= 364 < 365;

So for n= 14, there can be 364 triads possible and on 365th day, repitition will take place;

So the least number of acquiantances is = n = 15;

Total number of visitors = 365 * 3 = 1095

Total unique number of people = 15;

So number of viists of each person = 1095/ 15 = 73;

Thus, there is some acquiantance who came over at least 73 times;