16 students took part in a competition

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

12 users

TOPICS

No tags match your search

M

No tags match your search

M

16 students took part in a competition

G H J

Reveal topic tags

combinatorics solved

Probabilistic Method

double counting

L

G H BBookmark kLocked kLocked NReply

Source: China TST 1992, problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Jun 27, 2005, 10:11 AM • 2 Y

Y by Adventure10, Mango247

16 students took part in a competition. All problems were multiple choice style. Each problem had four choices. It was said that any two students had at most one answer in common, find the maximum number of problems.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

349 posts

#2 h Jul 6, 2005, 7:36 PM • 2 Y

Y by Adventure10, Mango247

Quote:

16 students took part in a competition. All problems were multiple choice style. Each problem had four choices. It was said that any two students had at most one answer in common, find the maximum number of problems.

A student is allowed to NOT answer a question (leave it blank as an answer), right?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

421 posts

zhaoli

#3 h Jul 26, 2005, 11:56 AM • 2 Y

Y by Adventure10, Mango247

Quote:

A student is allowed to NOT answer a question (leave it blank as an answer), right?

No, the answer to every problem has only four choices, blank is not permitted.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1160 posts

#4 h Jul 26, 2005, 2:41 PM • 3 Y

Y by Adventure10, Mango247, Hermione07

Suppose there are $m$ problems $P_1,P_2...,P_m$ for problem $P_i$ , suppose $a_i$ students answer first choice, $b_i$ secound choice, $c_i$ third choice and $d_i$ fourth choice. Since $a_i+b_i+c_i+d_i=16$ we have at least $4\binom{4}{2}=24$ pairs with an answer in common for each problem. Since there are $m$ problems there are at least $24m$ such pairs, but on the other hand there are at most $\binom{16}{2}=120$ such pairs. So we have that $m$ is at most $5$ . Now can equality hold? since for $m=5$ we need stronger conditions (namely for every problem every choice is selected by 4 students, and every pair has a common choice for some problem) I think such construction is possible since i dont fin any other constraint.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

827 posts

#5 h Jan 2, 2006, 3:39 PM • 7 Y

Y by Wizard_32, Pluto1708, Adventure10, ike.chen, Flint_Steel, Hermione07, Rijul saini

I think I found an example
$\begin{array}{|c|c|c|c|c|c|} \hline \text{student} & Q1 & Q2 & Q3 & Q4 & Q5 \\ \hline 1 & A & A & A & A & A \\ \hline 2 & A & B & B & B & B \\ \hline 3 & A & C & C & C & C \\ \hline 4 & A & D & D & D & D \\ \hline 5 & B & A & C & D & B \\ \hline 6 & B & C & A & B & D \\ \hline 7 & B & D & B & A & C \\ \hline 8 & B & B & D & C & A \\ \hline 9 & C & A & D & B & C \\ \hline 10 & C & D & A & C & B \\ \hline 11 & C & B & C & A & D \\ \hline 12 & C & C & B & D & A \\ \hline 13 & D & A & B & C & D \\ \hline 14 & D & B & A & D & C \\ \hline 15 & D & C & D & A & B \\ \hline 16 & D & D & C & B & A \\ \hline \end{array}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

827 posts

#6 h Jul 29, 2007, 9:57 PM • 3 Y

Y by Wizard_32, Adventure10, Rijul saini

Here's a way to motivate my construction (which I did by trial-and-error back then).

Consider the grid of 16 points $\mathbb{Z}_{4}\times \mathbb{Z}_{4}$ (a finite affine plane). Consider all families of 4 parallel lines (each passing through 4 points). There are 5 such families, each corresponding to a unique slope.

Each family of lines corresponds to one problem. For a given family, color the four lines with four different colors (corresponding to the 4 different multiple-choice answers). The 16 points correspond to the 16 questions.

This gives the desired construction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

827 posts

#7 h Jul 31, 2007, 6:13 PM • 2 Y

Y by Adventure10, Mango247

Oops, I meant $\mathbb{F}_{4}\times \mathbb{F}_{4}$ , where $\mathbb{F}_{4}$ is the field with 4 elements.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1036 posts

#8 h Dec 20, 2007, 5:50 AM • 2 Y

Y by Adventure10, Mango247

Sorry, but I don't quite understand what you mean. Would it be possible to draw a diagram?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

169 posts

#9 h Dec 22, 2007, 11:19 AM • 2 Y

Y by Adventure10, Mango247

@ Pascual: I have another way to prove that there cant be more than 5 questions. Suppose the Q1(question 1) was answered as option 'a' by p1 (participant 1),p2,p3 and p4 .(only: There cant be a p5 as all of them (p1 to p5) have to opt for different options of Q2 and it would not be possible by pigeon hole principle).
So 1 can have common options with {2,3,4}{5,6,7}{8,9,10}{11,12,13}{14,15,16}
Hence not more than 5 questions. But we need a construction to say this is surely possible and billzhao does it(I have not checked it but).

@billzhao: I only get the feel of your 4*4 affine plane construct, but not able to get the complete proof. Would you explain in detail? I feel this problem somehow connects with Kirkman schoolgirls problem, any idea? You created a example, can we enumerate the number of such possible constructs?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1454 posts

#11 h Apr 29, 2019, 4:37 PM • 2 Y

Y by Adventure10, Mango247

A more clear solution (indicating double-counting) is as follows. Suppose, there are $m$ tasks in the contest. Count the total number of triples of form $(C_i,C_j,Q_k)$ , where contestants $1\leq i <j\leq 16$ agreed on problem $k\in\{1,2,\dots,m\}$ . From the perspective of each pair, there is at most one such triple, hence, the number is upper bounded by $\binom{16}{2}$ . Now, from the perspective of any problem, if $x,y,z,t,$ are the number of people selected first choice, ..., fourth choice, then there is precisely $\binom{x}{2}+\binom{y}{2}+\binom{z}{2}+\binom{t}{2}$ pairs, agreed on problem $k$ . Using convexity of Binomial coefficients with Jensen's inequality, and the fact that $x+y+z+t=16$ , the total number of contestants, we get, $\binom{x}{2}+\binom{y}{2}+\binom{z}{2}+\binom{t}{2}\geq 24$ . This yields, $\binom{16}{2}\geq 24m$ , namely, $m\leq 5$ . An example of $m=5$ is easy to construct, and is provided above.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

797 posts

#12 h Mar 24, 2020, 11:45 AM • 1 Y

Y by Mango247

A very much similar solution to the one above.
Solution

This post has been edited 2 times. Last edited by Pluto04, Mar 24, 2020, 11:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1162 posts

#13 h Jul 4, 2022, 3:14 PM

Y by

Let the students be $S_1, S_2, \ldots, S_{16}$ and the questions be $Q_1, Q_2, \ldots, Q_n$ . Define $X$ as the number of triples $(S_i, S_j, Q_k)$ where $1 \le i < j \le 16$ such that $S_i$ and $S_j$ got the same answer for $Q_k$ .

Because any two students have at most one answer in common, we have $X \le 1 \cdot \binom{16}{2} = 120.$ Now, we find a lower bound for $X$ by analyzing each question individually. WLOG, pick $Q_1$ .

For $Q_1$ , suppose $a$ people answered "A", $b$ people answered "B", $c$ people answered "C", and $d$ people answered "D". Since $a+b+c+d = 16$ , Cauchy-Schwarz implies $\binom{a}{2} + \binom{b}{2} + \binom{c}{2} + \binom{d}{2} = \frac{a^2 + b^2 + c^2 + d^2 - (a+b+c+d)}{2}$ $\ge \frac{(a+b+c+d)^2}{8} - 8 = 24.$ Thus, there are at least $24$ triples of the form $(S_i, S_j, Q_1)$ . Now, symmetry implies $24n \le X \le 120 \implies n \le 5$ as required. $\blacksquare$

Remarks: Also see here and here.

This post has been edited 1 time. Last edited by ike.chen, Jul 4, 2022, 3:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

407 posts

alexanderhamilton124

#14 h Oct 11, 2024, 12:01 PM • 1 Y

Y by L13832

Consider the triplets $(\text{student}, \text{student}, \text{common answer})$ . We see that fixing the students, there are at most $\binom{16}{2}$ such triplets. See question 1 and each option.

Let $a$ be the number of students who pick the first option, $b$ the number who pick the second option, $c$ the number who pick the third option, and $d$ the number who pick the fourth option (note $a + b + c + d = 16$ ). Thus, the number of such triplets is given by:
$\binom{a}{2} + \binom{b}{2} + \binom{c}{2} + \binom{d}{2} = \frac{a^2 + b^2 + c^2 + d^2 - 16}{2}$ For the first question, since $a^2 + b^2 + c^2 + d^2 \geq 64$ by the Cauchy-Schwarz inequality, we have at least $24$ such triplets. Repeating this for the other questions, there are at least $24 \cdot q$ such triplets (where $q$ denotes the number of questions). Therefore,
$24q \leq \binom{16}{2} \implies q \leq 5.$ We see that there is a construction for $q = 5$ (mentioned above, not putting it here since it would take too much time to latex), so our answer is $\boxed{5}$

This post has been edited 1 time. Last edited by alexanderhamilton124, Oct 11, 2024, 5:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

161 posts

#15 h Jan 7, 2025, 11:04 AM

Y by

Ooo nice problem

For the bound, notice that every question creates atleast $4\cdot \binom 42=24$ common answers due to jensen, and since the maximum number of pairs of possible common answers is $\binom{16}2=120$ , we get a bound of $\frac{120}{24}=5$ , as desired.

Make the students to be elements in $\mathbb{Z}_4\times \mathbb{Z}_4$ in the plane and each question corresponds to the 5 family of parallel lines, each of which contains 4 lines which correspond to a certain option in the question, and each student chose the option from their respective family such that it lies on the line of that family. Its not so hard to see that this works

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1055 posts

#16 h Jan 14, 2025, 8:02 AM

Y by

Same as everything above, died on the construction though. I don't get the finite field approach above, is there any better method?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

88 posts

#17 h Jun 28, 2025, 2:15 PM

Y by

We claim that the answer is $\boxed{5}$ . We will only prove the bound, the construction is omitted for the sake of compactness.

Let there have been $k$ problems. We will count the number $N$ of ordered triples $(S_1, S_2, A)$ such that students $S_1$ and $S_2$ agreed on answer $A$ in two ways.

Picking the students first, we have $N \leq \binom{16}{2} = 120$ .

Fixing a problem and letting the students vary, we have

$N = \sum_{q = 1}^{16} \binom{f(1, q)}{2} + \binom{f(2, q)}{2} + \binom{f(3, q)}{2} + \binom{f(4, q)}{2}$
$\geq k \times \left [ \binom{4}{2} + \binom{4}{2} + \binom{4}{2} + \binom{4}{2} \right ] = 24k$ .
where $f(p, q)$ denotes the number of students who answered the $q^{\text{th}}$ question with the $p^{\text{th}}$ choice so that $\sum_{i = 1}^4 f(i, q) = 16$ for all $q$ , and the inequality follows from Jensen/smoothing.

This gives $24k \leq 120 \implies \boxed{k \leq 5}$ as desired.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a