$N$ non-negative integers whose sum is $100,$ the integer $3$ occurs more often than any other. What is the largest possible value of $N?$
-
Why not find a valid list and try to increase the number of integers in the list?
-
What are the sensible integers in the largest list?
-
… remember that you can use
$0$as well. -
… for example, having
$5$is not sensible because we can have$3,$$2$and$0$instead and have more integers. -
How about expressing the number of other sensible integers in terms of the number of
$3$s to find$N?$ -
Have you considered all of the constraints given?
-
Having numbers greater than
$3$in the list is not useful, since we can have more integers for the same value by splitting that number into some$3$s,$1$s and$0$s. A$2$can be converted into two$1$s and two$2$s can be converted into$3,1$and$0.$Since any two
$2$s can be converted to$3,1$and$0,$which doesn’t affect our quota of$1$s and$0$s (bounded by number of$3$s), the optimal solution will have at most one$2.$Although there is an optimal solution that uses$2$(see below), it is possible to reach optimum without$2$s. So for now, the only numbers we will consider are$0, 1,$and$3.$We also notice that we can exchange a
$3$and a$0$for 3$1$s. Hence our strategy is to maximize the number of$3$s such that we can fit as many$1$s without making the$1$s more common. We then add$0$s up to the number of$3$s. Let$t$be the number of$3$s which means we’ll have$100-3t$of$1$s and$t-1$of$0$s. In total, we’ll have$N=t+100-3t+t-1=100-t-1,$conditioned by$t>100-3t,$which gives$t=26$and$N=73.$The two solutions are 26
$3$s, 22$1$s, 25$0$s or 25$3$s, 1$2$, 23$1$s, 24$0$s.