This is a problem on Kostub Deshmukh's business card (co-founder of math.chat). The premise of math chat is to do math with friends, and the problem is in that spirit.
I will let the business card speak for itself:
If you are having problems with the image, the problem in text:
In a group of 9 mathematicians, each speaks at most 3 languages, and each pair of mathematicians share a language.
Show that at least 5 mathematicians speak the same language.
Note: I haven't solved it myself yet. Perhaps Kostub will post a solution in the comments sometime.
I will let the business card speak for itself:
If you are having problems with the image, the problem in text:
In a group of 9 mathematicians, each speaks at most 3 languages, and each pair of mathematicians share a language.
Show that at least 5 mathematicians speak the same language.
Note: I haven't solved it myself yet. Perhaps Kostub will post a solution in the comments sometime.
One way is to draw tree graph and demonstrate. Hard to do it here it appears. Writing some explanation but cant write the whole thing in much detail with all cases:
ReplyDeleteLet's call them M1, M2, ... M9. Now each M:
a) shares a language with each of the others
b) can at most speak 3 languages (say L1, L2, L3).
Case 1:
If M1 spoke only L1 all would have to speak that given (a). Which means we have 9 M's speaking a language.
Case 2:
If M1 spoke only L1, L2 then from amongst the other 8, there has to be at least a set of 4 (half of 8) that speak one of L1, L2 which means that set with M1 combined is 5 mathematicians.
Case 3:
If M1 spoke L1, L2 and L3, then the only possible distribution of number of elements in the 3 sets for the remaining 8 mathematicians is (2,3,3) that is say M2, M3 speak L1, M4, M5, M6 speak L2 and M7, M8, M9 speak L3. Any other distribution will get a set of 4 elements and so that will make it 5 with M1.
Given above, for M2 to speak with the 6 Ms of the other 2 sets (M4 to M9), M2 cannot use L2 or L3 as that language set has max of 4 already from M1's distribution. So M2 has to speak two new languages L4, L5. The distribution of num elements for M2's 6 peers for (L1, L4, L5) has to be either (1,2,3) or (0,3,3). Of this (1,2,3) distribution is pointless as it means the first distribution for M1 is compromised with redundancy (ie one shares 2 languages with M1). Taking (0,3,3) distribution and work forward. However you want to leverage this to get the L2, L3 members to be able to intercommunicate. Example: L4: M2, M4, M5, M7 and L5: M2, M6, M8, M9.
Similarly for M3 next can be L6: M3, M4, M8, M9 and L7: M3, M5, M6, M7.
At this point all are speaking 3 languages already. Yet there is still language commonality pending between M5, M8 and M5,M9
Thanks, looks promising! I will need to read through the last paragraphs more carefully, with some drawings...
Delete[Spoiler alert]
ReplyDeleteSuppose not.
Each person speaks exactly 3 languages, otherwise 8/2=4 he speaks some language common to at least 4 of his friends. This also shows (1) each language is spoken by 3 or 4 people, (2) each person speaks 2 languages spoken by 4 and one spoken by 3.
Focus on languages spoken by 4 only. Double counting: 2*9=18, not divisible by 4, contradiction.
Q.E.D.
This look right.
Delete