I decided to let my computer solve it, and it found the following solution:
17, 18, 21, for a total of 56.
This is the same as hexomino's latest solution, who updated his post with this shortly before I posted this answer.
Assuming my program is correct, this is optimal.
To show this is indeed a solution:
100 is not possible:
We want to see if 100=17a+18b+21c has any solutions. Working modulo 3 we see that a=2 (mod 3) so we need 2 or 5 boxes of 17. Using 5 boxes leaves only 100-5*17=15 which is obviously not possible. Using 2 boxes leaves 100-2*17=66. Solving 66=18b+21c modulo 7 gives b=6 (mod 7) but obviously 6 boxes is too many.
Below are some ways to make 101-120. All larger numbers are possible by adding one or more boxes of 17 to these.
101 = 1*17 + 4*21
102 = 1*18 + 4*21
103 = 5*17 + 1*18
104 = 4*17 + 2*18
105 = 3*17 + 3*18
106 = 2*17 + 4*18
107 = 1*17 + 5*18
108 = 6*18
109 = 2*17 + 3*18 + 1*21
110 = 1*17 + 4*18 + 1*21
111 = 5*18 + 1*21
112 = 2*17 + 2*18 + 2*21
113 = 1*17 + 3*18 + 2*21
114 = 4*18 + 2*21
115 = 2*17 + 1*18 + 3*21
116 = 1*17 + 2*18 + 3*21
117 = 3*18 + 3*21
118 = 2*17 + + 4*21
119 = 1*17 + 1*18 + 4*21
120 = 2*18 + 4*21
The second-best solution has box sizes that are coprime:
13, 21, 23, for a total of 57.
Using 4 or 5 display boxes gives worse solutions:
6, 16, 27, 29, for a total of 80
9, 12, 15, 18, 47, for a total of 101
9, 12, 15, 21, 47, for a total of 104 if you don't want any box to be a multiple of another.
Note that if you could display more than one box of the same size, you would have better solutions for 4 or 5 display boxes, but obviously it does not beat using 3 boxes:
13, 13, 21, 23, for a total of 70
8, 8, 8, 27, 29 for a total of 80
Here is my program, which just does a straightforward search through all possibilities.
using System;
namespace TempProg
{
class PSEPencils
{
private const int N = 3; // number of boxes
private const int Goal = 100;
private static int _best = 200;
private static bool _noMultiples = true;
private static bool _noRepeat = true;
public static void Main()
{
int [] sizes = new int[N];
SearchSizes(sizes, 0, 0);
}
private static void SearchSizes(int[] sizes, int nextIndex, int sum)
{
if (nextIndex < sizes.Length)
{
int first = nextIndex == 0 ? 3 : sizes[nextIndex - 1] + (_noRepeat ? 1 : 0);
for (int i = first; i < _best; i++)
{
sizes[nextIndex] = i;
if(sum+i*(sizes.Length-nextIndex)<=_best)
SearchSizes(sizes, nextIndex + 1, sum+i);
}
}
else
{
if (IsValid(sizes))
{
foreach(int i in sizes) Console.Write(i+" ");
Console.WriteLine(": "+sum);
_best = sum;
}
}
}
private static bool IsValid(int[] sizes)
{
if (_noMultiples)
{
for (int i = 0; i < sizes.Length; i++)
{
for (int j = i + 1; j < sizes.Length; j++)
{
if (sizes[j] % sizes[i] == 0) return false;
}
}
}
int max = Goal + sizes[0] + 3;
bool[] found = new bool[max];
found[0] = true;
for (int i = 0; i < found.Length; i++)
{
for (int j = 0; j < sizes.Length; j++)
{
int prv = i - sizes[j];
if (prv >= 0 && found[prv])
{
found[i] = true;
break;
}
}
}
if (found[Goal]) return false;
for (int i = Goal + 1; i < found.Length; i++)
{
if (!found[i]) return false;
}
return true;
}
}
}