In the land of Heptanomisma, four different coins and three different banknotes are used, and their denominations are seven different natural numbers. The denomination of the smallest banknote is greater than the sum of the denominations of the four different coins. A tourist has exactly one coin of each denomination and exactly one banknote of each denomination, but he cannot afford the book on numismatics he wishes to buy. However, the mathematically inclined shopkeeper offers to sell the book to the tourist at a price of his choosing, provided that he can pay this price in more than one way. (The tourist can pay a price in more than one way if there are two different subsets of his coins and notes, the denominations of which both add up to this price.) (a) Prove that the tourist can purchase the book if the denomination of each banknote is smaller than $49$. (b) Show that the tourist may have to leave the shop empty-handed if the denomination of the largest banknote is $49$.
Problem
Source: BxMO 2018, Problem 2
Tags: BxMO, Benelux, combinatorics
29.04.2018 04:14
Very similar to IMO 1972-1. a) The same way of proof as IMO 1972-1. b) 49, 33, 17; 8, 4, 2, 1.
29.04.2018 22:16
I'm not quite sure I see connection to IMO 1972-1. However, your example in (b) does not satisfy the conditions of the problem since 17+33=50=49+1. (In fact, it is possible to show that there is a unique choice of coins and notes in (b) that forces the tourist to leave the shop empty-handed. This requires a bit more work than the problem as it was set.)
30.04.2018 06:15
Oh, my mistake, sorry.
27.10.2020 10:24
[Posting just for completeness] $\mathcal{A)}$ Name banknotes $B_1 >B_2>B_3$ and coins $C_1 >C_2 >C_3 >C_4$ s.t $\sum_{i=1}^{4} C_i <B_3$ Consider all the ways of paying using at most $2$ and at least $1$ banknotes. The minimum of price is $B_3$ and maximum is $B_1+B_2+\sum_{i=1}^{4}C_i \leq B_1+B_2+B_3-1$. So there are at most $B_1+B_2+B_3-1 -B_3 +1 = B_1+B_2 \leq 48+47 = 95$ The number of ways doing this is $2^4$ choices for coins and $6$ choices for banknotes so in total $ 6 \times 16 = 96$ By PhP since $96 >95$ there is a number with two ways of paying. $\mathcal{B)}$ choose $\{ 3,6,12,24,47,48,49 \}$