Brilliant's Mathematical Contest!

Logic Level 5

In a Mathematics Contest conducted by Brilliant, only the following facts are known to its staff:

The number of problems asked in the contest was ${n \geq 4}$ .
Each problem was solved by exactly four contestants.
For each pair of problems, there is exactly one contestant who solved both the problems.

Assuming that the number of contestants is greater than or equal to ${4n}$ , help the staff find the minimum value of ${n}$ for which there always exists a contestant who solved all the problems.

Image Credit: MissiouriState.edu .

The answer is 14.

1 solution

Eshan Balachandar
Sep 4, 2015

It's clear that if a contestant solves 5 questions, he must have solved all questions

So, in the limiting case, he must solve 4 questions. Now all the questions he has solved have a connecting contestant with all the other questions. These connecting contestants must also solve 4 questions each in the limiting case.

A question that he has done will be done by 3 other contestants as well. They each connect it to 3 other questions each. So 4+3+3+3 is the limiting case. For 14 questions or more, it is not possible for there to be a common link between all questions unless someone has answered 5 questions or more.

Also, if someone has solved 5 questions, he must be the only one to have solved more than one question :)

What? Can you explain this -

"It's clear that if a contestant solves 5 questions, he must have solved all questions (by rule 3)" ?

Satyajit Mohanty - 5 years, 9 months ago

Its a good time it take 4 min to do

Rakshit Joshi - 5 years, 7 months ago

If a person solves a questions with a > 4 then for all the pairs between the a questions solved there will be a person who solved them. Now , taking into account this it would mean that taking any of the n-a questions that remain it should have with all these a questions different people who have solved them , therefore implying that there must be more than 4 different persons for that question thing which therefore implies that it doesn't suit in the limit of 4 persons per question anyways.

A A - 5 years, 1 month ago

Let us assume A solves 5 questions and there are more than 5 questions. The sixth question has to be solved by 4 contestants B,C,D,E.

Each of the first 5 questions must have a contestant common with question 6. (rule3) But none of B,C,D,E can solve 2 questions out of the first 5 since A has already done them. This is not possible. The only possibility is if A himself has also done the 6th question while B,C,D have done only the 6th question. This can be extended to all the other questions.

Eshan Balachandar - 5 years, 9 months ago

In response to @Eshan Balachandar it was asked "minimum value of n for which there always exists a contestant who solved all the problems." so in your solution there is no contestant who has solved all the questions as all of them has solved only 4 problem..?? could you please explain..i'm not able to get it :/

Ƨarthi Nayak - 5 years, 7 months ago

Is it just me or is this solution solving a question other than the one asked?

Tina Sobo - 4 years, 7 months ago

Does anyone have a link/website that has more problems with the same type as this problem? I need more :)

Arctic Wolf - 3 years, 11 months ago

if we denote the questions by q1,q2,q3,.......,qn. let E1,E2,E3,.....,En be the number of students who solved questions q1,q2,...qn. we are given n(qi)=4(number of students who solved question qi) for each i. we are also given that n(qi intersection qj)=1 for each pair of questions qi,qj. we need to find the largest n such that n(q1 intersection q2 ........intersection qn)>=1 this is a set theory problem, can someone tell how to proceed from here.

Srikanth Tupurani - 2 years, 3 months ago

this approach wont work in this problem.

Srikanth Tupurani - 2 years, 3 months ago

Brilliant's Mathematical Contest!

Image Credit: MissiouriState.edu .

The answer is 14.

1 solution

0 pending reports