2
$\begingroup$

In a pizza shop they are offering $3$-toppings pizza with $10$ choices of toppings. A friend has decided that two of the three toppings on the pizza must be what they want but I don't know which two he has fixed.

Let $k$ be the minimum number of $3$-toppings pizza we have to order so that we can guarantee the friend gets what he wants.

We have to prove that $k=17$.

I tried doing it with pigeonhole principle.

Suppose $2$ of the toppings of the pizza is fixed then we can choose the $3rd$ one from remaining $8$ in $8$ ways. We can make those $8$ pizzas as one pigeonhole.

I am not getting how to partition the remaining into pigeonholes.

$\endgroup$
2
  • $\begingroup$ Are you assuming he chose 2 distinct toppings? $\endgroup$
    – DanielV
    Dec 18, 2021 at 5:02
  • $\begingroup$ @DanielV yes I am assuming distinct choices. $\endgroup$
    – User56
    Dec 18, 2021 at 5:03

2 Answers 2

Reset to default
3
$\begingroup$

Each topping can be found on at least $5$ pizzas. Because if we have only $4$ pizzas with topping $x$, then these $4$ pizzas contain $4\times 3=12$ toppings where $4$ are topping $x$, so there are only $12-4=8$ other toppings remaining and not $9$.

If we count all topping on our pizzas we bought we have therefore at least $50$ toppings, so we have at least $50/3=16+2/3$ pizzas.

Inspired by RobPratt's linked to ljcr.dmgordon.org:

If we have nine toppings we arrange the numbers 1 to 9 in a square. The horizontal rows, vertical rows and diagonals in $12$ groups of numbers, where each pair is contained in exactly one group:

If we augment the square

1 2 3
4 5 6
7 8 9

to an infinite grid

     . . . . . . . . . . . .
     . . . . . . . . . . . .
     . . . . . . . . . . . .  
 ... 1 2 3 1 2 3 1 2 3 1 2 3 ... 
 ... 4 5 6 4 5 6 4 5 6 4 5 6 ... 
 ... 7 8 9 7 8 9 7 8 9 7 8 9 ... 
 ... 1 2 3 1 2 3 1 2 3 1 2 3 ... 
 ... 4 5 6 4 5 6 4 5 6 4 5 6 ... 
 ... 7 8 9 7 8 9 7 8 9 7 8 9 ... 
 ... 1 2 3 1 2 3 1 2 3 1 2 3 ... 
 ... 4 5 6 4 5 6 4 5 6 4 5 6 ... 
 ... 7 8 9 7 8 9 7 8 9 7 8 9 ...  
     . . . . . . . . . . . .
     . . . . . . . . . . . .
     . . . . . . . . . . . .

and draw all vertical, horizontal and diagonal lines, and choose for example 1 the for each of its neighbor 2,....,8 we can find a line that contains 1 and this neighbor.

enter image description here

Similar holds if we choose a another number. These lines partition the numbers in 12 groups:

  1-2-3
  4-5-6
  7-8-9
  
  1 2 3
  | | |
  4 5 6
  | | |
  7 8 9
   
   (3)1 2 3
     \ \ \ 
      4 5 6
       \ \ \
      7 8 9(7)
       
      1 2 3(1)
       / / /
      4 5 6
     / / /
   (9)7 8 9

This gives raise to the following topping $12$ combination:

  1 2 3
  4 5 6
  7 8 9
  1 4 7
  2 5 8
  3 6 9
  1 5 9
  2 6 7
  3 4 8
  1 6 8 
  2 4 9 
  3 5 7

Topping 10 is stille not on a pizza, so we combine it with all the other 9 toppings

  1  2 10
  3  4 10
  5  6 10
  7  8 10
  1  9 10

In the last group one topping is reused which was already combined with 10 to get three toppings for this pizza.

Now we have $12+5=17$ pizzas that contain all pairs of toppings. We already showed that this is the minimum of pizzas we need.

So you have to order $17$ pizzas.

$\endgroup$
1
  • $\begingroup$ In fact the $12$-pizza sub-combination used in your proof has a special name – the Hesse configuration. $\endgroup$
    – Parcly Taxel
    Dec 18, 2021 at 18:33
3
$\begingroup$

You are looking for a $(10,3,2)$ covering design. That is, you want a collection of $3$-subsets of a $10$-set that together cover all $2$-subsets. The minimum is known to be 17.

You can derive a lower bound of $15$ by noting that there are $\binom{10}{2}=45$ pairs to cover and each $3$-subset covers $\binom{3}{2}=3$ of them.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .