There are $100$ cards with numbers from $1$ to $100$ on the table.Andriy and Nick took the same number of cards in a way such that the following condition holds:if Andriy has a card with a number $n$ then Nick has a card with a number $2n+2$.What is the maximal number of cards that could be taken by the two guys?
Problem
Source: Ukrainian National Math Olympiad 4th round
Tags: combinatorics unsolved, combinatorics
nicetry007
20.10.2014 18:24
Form mutually exclusive chains like $1\rightarrow 4 \rightarrow 10 \rightarrow 22 \rightarrow 46 \rightarrow 94$ $2\rightarrow 6 \rightarrow 14 \rightarrow 30 \rightarrow 62$ $3\rightarrow 8 \rightarrow 18 \rightarrow 38 \rightarrow 78$ $5\rightarrow 12 \rightarrow 26 \rightarrow 54$ $7\rightarrow 16 \rightarrow 34 \rightarrow 70$ $9\rightarrow 20 \rightarrow 42 \rightarrow 86$ $11\rightarrow 24 \rightarrow 50$ $13\rightarrow 28 \rightarrow 58$ $\vdots$ $21\rightarrow 44 \rightarrow 90$ $23\rightarrow 48 \rightarrow 98$ $25\rightarrow 52$ $27\rightarrow 56$ $\vdots$ $47\rightarrow 96$ $49\rightarrow 100$ $51$ $53$ $\vdots$ $97$ $99$ It is clear that the maximum number is 66. Subtract 1 element for every chain of odd length. Hence, it is = 100 - 2 - 7 - 25 = 66$
MillenniumFalcon
23.10.2014 14:14
Nick has max 100 -> corresponds to 49. The following arrangement: Total of 52 cards. NIck:{100, 98, ... 50} Andriy:{49, 48, ... 24} Within [1, 23], we can take a total of 12 cards Nick:{22, 20, ... 12} Andriy:{10, 9, ... 5} Within [1,4] we can take a total of 2 cards Nick:{4} Andriy:{1}. So, total of 66 cards. However saying : "This is the max possible arrangement because if I remove anything from one subset, I cannot add more pairs of numbers to other subsets." is completely unrigorous and Nicetry007's solution is very good, in contrast