During an examination

Logic Level 2

During an examination, 60 students had to answer 3 questions. After the examination, it's shown that for any two students, there is always at least 1 question which both students could solve.

Are the statements below true or false, using the given information?

a. There exists 1 question which at least 40 students could solve.

b. If there is a question which no students could solve, there must be another question which all students could solve.

A is false but B is true A is true but B is false Both are False Both are True

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Tin Le
Nov 1, 2020

Assume the three questions are X , Y X, Y and Z Z .

Without loss of generality, assume that no students can solve X X .

If no students can solve Y Y either then according to the given information, all students must have solved Z Z , and vice versa. This means that B B is true.

If all students can solve both Y Y and Z Z then B B is obviously true.

If there is one student who can solve only one question, assume it's Y Y . According to the information, all other students must have solved Y Y , and vice versa. This means that B B is also true.

Therefore, B B must be t r u e \boxed{true} .


If there is one student who can solve only 1 question, it's already proved that all other students must have solved it too (meaning all 60 students solve that problem). Therefore, A is true.

Examine another scenario where every student solved at least 2 questions.

Let:

  • The number of students who can solve Z and Y but not X be x x

  • The number of students who can solve X and Z but not Y be y y

  • The number of students who can solve X and Y but not Z be z z

  • The number of students who can solve all questions be t t

( x , y , z , t N x,y,z,t \in \N )

According to the information given, x + y + z + t = 60 x+y+z+t=60

Assume that the statement A A is false. Then, x + y + t < 40 , x + z + t < 40 x+y+t < 40, x+z+t < 40 and y + z + t < 40 y+z+t < 40

Examine the sum of those 3 inequalities:

( x + z + t ) + ( x + y + t ) + ( y + z + t ) < 40 + 40 + 40 2 ( x + y + z + t ) + t < 120 t < 0 (x+z+t) + (x+y+t) + (y+z+t) < 40 + 40 + 40 \Leftrightarrow 2(x+y+z+t) + t <120 \Leftrightarrow t < 0

This is clearly a contradiction, as t N t \in \N .

Therefore, the statement A A must be t r u e \boxed{true} .


Then, both statements are true .

For the proof of statement A you assume that every student solves at least 2 problems, which is not given.

Adrian Klaeger - 7 months, 1 week ago

Log in to reply

You should read the proof for statement B:

Assume that there is one student who can only solve 1 problem, then according to the information, all other students must have solve that problem too. Then 60 students solve that problem, which makes statement A true.

Tin Le - 7 months, 1 week ago
Adrian Klaeger
Nov 2, 2020

The assumption tells us that everyone has solved at least one question, since you cannot have a common solution with someone who has no solutions.

If there is someone who solved only one question, then everyone else must also have solved that question, since this is the only way to have a common solution with that student. In this scenario there is therefore a question that everyone has solved, which fulfills both statements.

The other scenario to examine is the one where everyone has solved at least 2 questions. With 60 students this gives at least 120 total solutions, which means the most-solved question cannot have fewer than 120/3 solutions and therefore the first statement is fulfilled. If one question has no solutions then the other two were solved by everyone in this scenario, which fulfills the second statement.

Since both statements are fulfilled in all possible scenarios, they are both true.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...