Not selling 100 pencils

Question

A shop sells pencils only in boxes of fixed size.
It cannot sell 100 pencils.
It can sell any larger amount of pencils.

It has one of each size box on display.

question 1: What is the minimum amount of boxes it may have on display?
question 2: What is the minimum amount of pencils it may have on display?

example: If the shop would sell boxes with 5,8, 28 and 100 pencils, it would have 4 boxes / 141 pencils on display. In that case it would be able to sell any amount >100, but it could also sell 100 so it is not a valid solution.

Answer 1

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;
        }
     }
  }

Answer 2

Minimum amount of boxes on display

The answer is three which can be achieved, for example, by selling pencils in boxes of size either 3, 98 or 103.

We know from this recent question that two is not achievable because if the number of pencils of fixed size were equal to relatively prime $p$ and $q$, then we would need $$pq-p-q = 100 \Rightarrow (p-1)(q-1) = 101$$ which has no solutions for $p$, $q$ relatively prime.

I haven't found a proven minimum for question 2 yet but the lowest I've gotten so far is

56 pencils

With display box sizes of

17, 18 and 21

Answer 3

If the store is a stationery or office supply shop, then the following possibilities are valid for the number of boxes and the number of pencils they contain. (The $b$s represent the boxes and the numbers represent the corresponding numbers of pencils.)

$b_1=5 \times 2^0$

$b_1‹b_2 \le5\times2^1$

$b_2‹b_3\le5\times2^2$

$b_3‹b_4\le5\times2^3$

$b_4‹b_5\le5\times2^4$

Realistically speaking, the number of boxes and the pencils they contain is as shown above.