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.
Best Answer
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
to an infinite grid
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.
Similar holds if we choose a another number. These lines partition the numbers in 12 groups:
This gives raise to the following topping $12$ combination:
Topping 10 is stille not on a pizza, so we combine it with all the other 9 toppings
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.