1i didn't understand how the answer is 6,plz make me understand
In an international meeting of n≥3 participants, 14 languages are spoken. We know that:
- Any 3 participants speak a common language.
- No language is spoken more that by the half of the participants.
What is the least value of n ?
-
UP 0 DOWN 0 0 15
15 Answers
1
341I think n = 8. Bit of a clumsy proof though
Obviously n>5.
Now represent the participants by dots, so as to form the vertices of a polygon. When we form a triangle using three vertices, we can label it by an li for one of the 14 languages spoken.
If n = 6, we have 6C3 = 20 triangles. Since each language can have up to three speakers, every triangle has to be labelled by a distinct index. But we have only 14 indices available
The same reasoning excludes n = 7.
For n =8, we can have up to 4 speakers per language. Now we have 56 triangles. Suppose you label the vertices 1,2,..,8, then we find fourteen quadrilaterals that have not more than 1 edge common as below:
1 2 3 4
1 2 5 6
1 2 7 8
3 4 5 6
3 4 7 8
5 6 7 8
1 3 6 8
1 3 5 7
2 4 5 7
2 4 6 8
1 4 5 8
1 4 6 7
2 3 5 8
2 3 6 7
Each of these 14 quadrilaterals has four triangles which are not shared with any other triangle (since no two quadrilaterals share more than one edge). Thus the 56 triangles are partitioned into 14 groups of four such that each group has 4 vertices.
Label each of these 14 groups by Q1 , Q2,....Q14. In each Qi all the four triangles are assigned li
Its now easy to see that we have met the conditions as
(1) every triangle has been labelled and hence any three speakers have a language in common
(2) All the triangles that are labelled by the same index are formed from the four vertices of a quadrilateral, so that each language is spoken by exactly four speakers.
And so the minimum number of participants is 8
[I am sure there is a more elegant way of presenting this. So I would like to see a simpler solution]
341Is my post invisible? I think I have clearly explained why it cannot be 6.
Anyway the OP is either in Moscow or enroute to India, so lets wait for his verdict.
39actually this can even be solved like dis:
an odd `n` leaves no lower n in particular
now if n is even ,
say n=2l , then we can see dat every language can remove atmost lC3 trios.
so required condition is 14x lC3≥2lC3
its possible for only l>3
and hence smallest possible n=8
39i have a geometrical method too, but just checking if its in anyway different from wat u suggested above
39and in btw, prophet sir ,
what took u so long? and wat made u dig up such an old one?
1cartman wrote
"and in btw, prophet sir ,
what took u so long? and wat made u dig up such an old one? "
hey please give some respect to senior members of this forum
341dont worry, we know each other well and he did not mean to be insulting :D.
It resurfaced after Madhurima's post and I was just trying to figure why it was 6, realized it cant be 6 and investigated what was the minimum value of n. Just a random event
39and if u r free
try out the generalisation of this question , its interesting
341I didnt understand the sentence about odd n. But the rest is plain enough. Nice!