Martu wants to build a set of cards with the following properties: • Each card has a positive integer on it. • The number on each card is equal to one of $5$ possible numbers. • If any two cards are taken and added together, it is always possible to find two other cards in the set such that the sum is the same. Determine the fewest number of cards Martu's set can have and give an example for that number.
Problem
Source:
Tags: contests, combinatorics
CT17
18.06.2022 22:19
Solved with v4913, DottedCaculator, and CyclicISLscelesTrapezoid I am assuming all $5$ numbers have to appear among Martu's cards, as otherwise the problem would make no sense. Let the $5$ possible numbers be $a_1 < a_2 < a_3 < a_4 < a_5$. By the third condition on the pair $(a_4,a_5)$, Martu must have a second copy of both $a_4$ and $a_5$. But by the third condition again on $(a_5,a_5)$, Martu must have two more copies of $a_5$. By the exact same argument with $a_1$ and $a_2$, Martu must have at least $4$ copies of $a_1$ and $2$ copies of $a_2$. This totals to a lower bound of $4 + 2 + 1 + 2 + 4 = 13$ cards. But this is sufficient with the construction $\{1,1,1,1,2,2,3,4,4,5,5,5,5\}$.
lian_the_noob12
24.04.2023 13:35
CT17 wrote: Solved with v4913, DottedCaculator, and CyclicISLscelesTrapezoid I am assuming all $5$ numbers have to appear among Martu's cards, as otherwise the problem would make no sense. Let the $5$ possible numbers be $a_1 < a_2 < a_3 < a_4 < a_5$. By the third condition on the pair $(a_4,a_5)$, Martu must have a second copy of both $a_4$ and $a_5$. But by the third condition again on $(a_5,a_5)$, Martu must have two more copies of $a_5$. By the exact same argument with $a_1$ and $a_2$, Martu must have at least $4$ copies of $a_1$ and $2$ copies of $a_2$. This totals to a lower bound of $4 + 2 + 1 + 2 + 4 = 13$ cards. But this is sufficient with the construction $\{1,1,1,1,2,2,3,4,4,5,5,5,5\}$. Pro :0