The answer is 10.

**
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.

Argh. For some reason I thought you were asking for the minimum value of $k$ rather than the minimum number of dishes. :( Anyway, nice question. My approach was to look at a circle with 5 points on it. Each of the dishes could then be represented as a triangle with 3 of these points as vertices. By drawing all of the 10 possible triangles we have each pair ordering 3 common dishes, so $n \le 10, k \le 3$ . Clearly $k \ne 1$ , and it's clear "by symmetry" that $k \ne 2$ , (need to be more formal here, of course).

Brian Charlesworth
- 4 years, 6 months ago

It is probably worth noting that this minimal construction is where the $10$ sets of three elements corresponding to the guests that order each of the $10$ dishes are precisely the collection of all subsets of size $3$ of a set of size $5$ ; it is then clear that every two guests belong to precisely $3$ such triples (just pick one of the other three guests to make up a triple). This shows that $n=10$ , $k=3$ is fine, without the need to write it all down!

Mark Hennings
- 4 years, 6 months ago

Nice way to present the information using a incidence matrix .

How about D1-123, D2-234, D3-345, D4-451, D5-512? That's only 5 dishes for 5 people, each dish shared by k=3 people.

Krishnan Gangadhar
- 4 years, 6 months ago

Log in to reply

Unfortunately, your construction doesn't satisfy the given conditions. Note that it's not "shared by k=3 people", but that it's "every pair of people ordered k common dishes".

What are the common dishes ordered by pairs 1-2 and 1-4?

That would've been a better construction. But in my construction I've hidden a secret message for brilliant members to decode. Can you figure it out?

Alan Yan
- 4 years, 6 months ago

Consider 5 people are $P=(p_1,p_2,p_3,p_4,p_5)$

Consider there are $n$ dishes such as $D=(d_1,d_2,d_3,.........,d_n)$ .

So,there is a mapping between $f: P \rightarrow D$ where $f(p_i)=d_j$ for some $i,j$ .Now we will consider the lines by which $p_i's,d_j's$ are connected.According to the question each dish $d_i$ is exactly ordered by $3$ people.So from each dish there will be $3$ edges which will connected to $P$ side.So,total no of lines/edges $3n$ .

Now each pair $p_i,p_j$ has $k$ dishes in common.Let $p_i$ ordered $d_1$ i.e. $f(p_i)=d_1$ and also $p_j$ ordered $d_1$ i.e. $f(p_j)=d_1$ .Each common dish will shares $2$ edges.So for $k$ common dishes there will be $2k$ edges.Total number of pairs

${10 \choose 2}=10$ .Total edges $10 \times 2 k=20 k$ .

Consider a pair $p_i,p_j$ both of them order a common dish $d_1$ .So an edge is counted from $p_i$ to $d_1$ and another an edge $p_j$ to $d_1$ .Again consider another pair $p_i,p_k$ both of them orders a common dish $d_1$ (Total three persons ordered dish $d_1$ ).So an edge is counted from $p_i$ to $d_1$ and another edge is counted from $p_k$ to $d_1$ ..So, in counting the edge $p_i$ to $d_1$ is counted twice.This will be counted for every edges.So, $3n$ edges are counted extra.

$20k-3n=3n \\ \implies 6n=20k \\ \implies 3n=10k$ .

If minimal $k=1$ then minimal $n=10$

1 Helpful
0 Interesting
0 Brilliant
0 Confused

×

Problem Loading...

Note Loading...

Set Loading...

Suppose there are $n$ dishes. Consider a $n \times 5$ table where the rows represent the dishes and the columns represent the people. In cell $(i,j)$ , place a $1$ if person $j$ ordered dish $i$ and place a zero otherwise. We will double count $\mathcal{M}$ , the number of pairs of $1$ in the same row. Since each row has $3$ ones, $\mathcal{M} = n \binom{3}{2}$ . Since every pair of people ordered $k$ common dishes, $\mathcal{M} = k \binom{5}{2}$ . So $n \binom{3}{2} = k \binom{5}{2} \implies 3n = 10k.$ Since $n,k$ are both positive integers, the minimal value would be $\boxed{n = 10}, k = 3$ . A construction is as shown: $\begin{pmatrix} 1 & 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}$