Help me with Combinatorics

Can you please help me with this problem?

There are $n$ persons which live on a planet. It is known that their planet has $6$ languages and each of the $n$ persons knows every language. It is also known that any two people communicate with just one of the six languages. What is the minimum value of $n$ such that there always exists a trio which mutually communicates with each other in the same language?

#Combinatorics #MathProblem #Math

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Check out Ramsey numbers. See also here.

In the case where there are 2 languages, the number $R(m,n)$ is the smallest positive integer $N$ such that if among $N$ people, any two people communicate with exactly one of the two languages, then one of the following must happen:

you can find $m$ people who communicate in language 1, or
you can find $n$ people who communicate in language 2.

The simplest non-trivial case is $R(3, 3) = 6$ . It's also known that $R(3,4) = 9$ and $R(4,4) = 18$ . But in general, not much is known except a rather weak upper bound.

For 3 languages, we have $R(3,3,3) = 17$ . Even less is known in the general case.

For 4 languages, the case of $R(3,3,3,3)$ is open as far as I know. What you're asking for is $R(3,3,3,3,3,3)$ which I doubt is anywhere close to being known.

C Lim - 7 years, 8 months ago

that should be 5

Kshitij Khandelwal - 7 years, 8 months ago

Generalizing the problem a bit, assuming that there are $m$ different languages it can be shown quite straightforwardly (using a trick, called Local Lemma) that for all $n < \frac{m^2}{12}+3$ there exists a language assignment such that no trio is formed. Hence necessarily we have to consider $n \geq \frac{m^2}{12}+3$ , that is $n\geq 6$ in this case.

Abhishek Sinha - 7 years, 8 months ago

I doubt your answer n = 6. Here, below is a list to show why I think you are wrong. Let the 6 people of the planet be represented by 6 integers from 1 to 6 and the six languages be represented by first 6 alphabets of English. Each item below represents the language a particular pair speaks.

['a', 1, 2]

['a', 2, 4]

['a', 4, 5]

['b', 1, 3]

['b', 2, 5]

['b', 4, 6]

['c', 1, 4]

['c', 2, 6]

['c', 5, 6]

['d', 1, 5]

['d', 3, 4]

['e', 1, 6]

['e', 3, 5]

['f', 2, 3]

['f', 3, 6]

In the above example are provided all the pairs of the population possible and in which language they talk with each other. For a trio that speaks the same language, at least three of the persons must communicate with each other using the same language which is not so.

Lokesh Sharma - 7 years, 8 months ago

I didn't say $n=6$ . I said $n \geq 6$ .

Abhishek Sinha - 7 years, 8 months ago

@Abhishek Sinha – Opps! I didn't quite see that. I thought you meant that it's true for any n in $n \geq 6$ .

Lokesh Sharma - 7 years, 8 months ago

Isn't $( 1, 2, 4 )$ a trio that speaks $'a'$ in your example?

Christopher Johnson - 7 years, 8 months ago

@Christopher Johnson – No because 1-4 communicates in language.

Rushi Rokad - 7 years, 8 months ago

@Christopher Johnson – No, because 1-4 communicate in language $'c'$ .

Lokesh Sharma - 7 years, 8 months ago

@Lokesh Sharma – Gotcha. I somehow missed the "mutual" part.

Christopher Johnson - 7 years, 8 months ago

Assuming I understand the problem correctly, given $n$ people, there are ${n \choose 2}$ couplings of people who speak a single language with each other. Since there are $6$ languages, the first $n$ for which ${n \choose 2} > 6$ should be the answer. ${4 \choose 2} = 6$ and ${5 \choose 2} = 10$ , so $5$ .

Perhaps it's supposed to be a bit of a surprise that it can be 5 people when there's 6 languages?

Christopher Johnson - 7 years, 8 months ago

I do not understand what you are trying to say, and I think that you misunderstood the question. You are supposed to find 3 people who pairwise communicate in the same language, and not show that the number of pairs of people is more than 6.

For example, in a group of 5 people, labelled $p_1, p_2, p_3, p_4, p_5$ , if the pairs $p_i, p_{i+1}$ communicate in the English language, and pairs $p_{i}, p_{i+2}$ communicate in the Chinese language, then you cannot find 3 people, such that each pair communicates in the exact same language. Hence, $n > 5$ .

Calvin Lin Staff - 7 years, 8 months ago

I believe what Calvin meant is: If Tom speaks english to Susan and Tom speaks english to Bob, we don't nessecarily have that Susan speaks english to Bob.

Ton de Moree - 7 years, 8 months ago

@Ton de Moree – Yeah, the "mutual" part didn't fully register the first time I read the question. I was just looking for two pairs of people who speak the same language and have a common member (a "chain" instead of a "triangle," so to speak).

Christopher Johnson - 7 years, 8 months ago

hey! i m new in this.... i wil be back after a day!

Abdul Saboor Khan - 7 years, 7 months ago

I thought designing an algorithm that does the job to find the right answer but couldn't do it due to one problem. The algorithm does the following things step by step.

For a given $n$ , it randomly divides all the possible pairs into $6$ sets. Each set include all those pairs that speak the same language.
Secondly, it looks into every set one at a time.
In every set it looks for a trio. A trio is like this $(a, b)$ , $(b,c)$ , $(a, c)$ . The presence of a trio provide evidence that a trio exists.
It runs this process this process a thousand or million times and returns the number of times such a trio is found or not. Even if a single time there is not a trio found, it discard the number and turns to another higher value of $n$ and repeats the whole process once again.

The problem I am facing is in third step in which it searches a trio. Need some help figuring out an algorithm that takes a set and returns True if there is a trio formed.

Lokesh Sharma - 7 years, 8 months ago

I was going to write a bunch of advice here, but it struck me that this problem would be ideal for a Brilliant contest! "Find the lowest $N$ you can for $R(3,3,3,3,3,3)$ ." It's apparently an open problem and quite hard. Plus, since we could submit just our data (arrangement of pairs into languages), it would be programming language agnostic, and a daily leaderboard could be computed. Something for the Brilliant folks to consider.

Christopher Johnson - 7 years, 8 months ago

I agree. The complexity of problem is tremendously high, making it hard to solve using customary methods. This makes it optimal for a challenge.

Lokesh Sharma - 7 years, 8 months ago

What is love?

Gautam Singhania - 7 years, 8 months ago

No point asking it here.

Lokesh Sharma - 7 years, 8 months ago

Baby don't hurt me, baby don't hurt me... no more... But seriously, why did you post this irrelevant comment?

Daniel Liu - 7 years, 8 months ago

It means nothing to a tennis player. That's as far as I can help.

Dan Krol Staff - 7 years, 8 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$