3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I'm not seeing anything puzzling about this. The store can sell any amount of pencils larger than 100, so the minimum number of pencils on display is 101. The pencils must be sold in boxes, so there must be at least 1 box (of 101 pencils) on display. I suspect you're missing some constraints? $\endgroup$ Apr 12 at 15:31
  • 1
    $\begingroup$ If they sell size 101, 102,103..201, they can sell any amount >100. But that is a lot of boxes, and a lot of pencils on display. There are far better solutions. $\endgroup$
    – Retudin
    Apr 12 at 15:38
  • 1
    $\begingroup$ But to be able to sell "any" amount would require an infinite number of pencils. It's not possible to have a finite number that is greater than every number above 100. If the shop has a finite stock, it simply cannot sell "any larger amount of pencils". $\endgroup$ Apr 12 at 15:43
  • 1
    $\begingroup$ @NuclearHoagie question states the shop has one of each size box on display, but the hidden assumption is that in addition to the display boxes (that are not normally for sale) the shop has an unlimited stock of each size of box in the stock room. $\endgroup$
    – Steve
    Apr 12 at 16:19
  • 1
    $\begingroup$ @Mohirl the "hidden" assumption was so obvious to me that I only realised there was another possible interpretation when the comment preceding mine made the opposing assumption. Perhaps people making the other assumption are less familiar with the common and obvious (to me, and presumably to puzzle setter) scenario of a shop which has a single example of each item for sale "on display" with all of the actual sales made from stock which is not "on display"? The puzzle also relies on many other unstated assumptions e.g. boxes cannot be split, shop can't sell a negative number of some boxes, etc. $\endgroup$
    – Steve
    Apr 13 at 14:12
2
$\begingroup$

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;
        }
     }
  }
$\endgroup$
3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Question 1 is indeed very related to the other one; your answer was what I had in mind (maybe I should have only asked question 2) $\endgroup$
    – Retudin
    Apr 12 at 15:58
  • $\begingroup$ @Retudin Yes, sorry, I misinterpreted q2 at first. I've updated now to a better (but probably not optimal) answer. $\endgroup$
    – hexomino
    Apr 12 at 16:02
  • $\begingroup$ Could you add any reasoning how you came to this answer? (and why you expect it not to be optimal) $\endgroup$
    – Retudin
    Apr 12 at 18:17
  • $\begingroup$ @Retudin I've just found a better answer, so will update. $\endgroup$
    – hexomino
    Apr 12 at 18:20
  • $\begingroup$ @Retudin The reason I don't think it's optimal yet is because I came to it too easily. I've tried a little harder and obtained a lower value but I still think I can stretch it more. Additionally I haven't even tried adding more boxes yet so there might be something there. $\endgroup$
    – hexomino
    Apr 12 at 18:23
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.