2
$\begingroup$

A certain chain store sells chocolate bars in packets of 17 and 9 only. Clearly, you could not get 8 or 25 bars. Find all quantities of bars that you cannot buy.

$\endgroup$
  • 4
    $\begingroup$ this is clearly an ad for chocolate. I'll be back. $\endgroup$ – Timmerz Nov 8 '14 at 12:55
9
$\begingroup$

We can make $17 \times 8 = 136$ and any number above this by replacing a $17$ with $2 \times 9$, to increment the number by $1$. By the time we run out of $17$s to replace ($9 \times 16$), we continue with $17 \times 8 + 9 = 145$ and repeat the trick, until we arrive at $9 \times 17$, at which point we swap that with $17 \times 9$ and start replacing $17$s again.

Looking at the numbers below $136$, we can make any number $n \times 17$ and

  1. the following $n$ integers by replacement of $17$ with $2 \times 9$,
  2. anything $m\times9$ above this e.g.
    $17$ gives us $18$ by replacement and $26$, $35$, $44$, $53$, $62$, $71$, $80$, $89$, $98$, $107$, $116$, $125$, $134$ by addition of $9$s

Adding all of these we find that the highest number we cannot make is

$127$

and there are

$63$

possible numbers below this.

The ones we cannot form are:

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 19, 20, 21, 22, 23, 24, 25, 28, 29, 30, 31, 32, 33, 37, 38, 39, 40, 41, 42, 46, 47, 48, 49, 50, 55, 56, 57, 58, 59, 64, 65, 66, 67, 73, 74, 75, 76, 82, 83, 84, 91, 92, 93, 100, 101, 109, 110, 118, 127

$\endgroup$
  • $\begingroup$ so what quantities can you not buy :p $\endgroup$ – d'alar'cop Nov 8 '14 at 10:35
  • $\begingroup$ I know the question is not answered - I had a PEBKAC error and posted before I had finished writing. Finishing it now. $\endgroup$ – frodoskywalker Nov 8 '14 at 10:37
  • $\begingroup$ +1 anyway of course. It's essentially solved. nice job :) $\endgroup$ – d'alar'cop Nov 8 '14 at 10:39
  • $\begingroup$ I can't find a simple argument why these numbers below 128 cannot be gotten and all others can. Or do I miss this? $\endgroup$ – miracle173 Nov 8 '14 at 12:26
  • $\begingroup$ @miracle You can get 1) Any multiple of 9, 2) Any multiple of 17 (call it $n*17$) and 3) the next $n$ numbers after (2). Once (2) and (3) start to overlap, you can form all higher numbers. $\endgroup$ – frodoskywalker Nov 8 '14 at 12:54
2
$\begingroup$

The numbers we can make are of the form $m \times 9 + n \times 17 \,| \, m, n \in \mathbb{Z}_{\ge0}$.

As we can see (and as has been said before), the largest number we can't make is $127$.

$$ \begin{array}{r|rr} \text{target} & m & n \\ \hline 0 & 0 & 0 \\ 1 & - & - \\ 2 & - & - \\ 3 & - & - \\ 4 & - & - \\ 5 & - & - \\ 6 & - & - \\ 7 & - & - \\ 8 & - & - \\ 9 & 1 & 0 \\ 10 & - & - \\ 11 & - & - \\ 12 & - & - \\ 13 & - & - \\ 14 & - & - \\ 15 & - & - \\ 16 & - & - \\ 17 & 0 & 1 \\ 18 & 2 & 0 \\ 19 & - & - \\ 20 & - & - \\ 21 & - & - \\ 22 & - & - \\ 23 & - & - \\ 24 & - & - \\ 25 & - & - \\ 26 & 1 & 1 \\ 27 & 3 & 0 \\ 28 & - & - \\ 29 & - & - \\ 30 & - & - \\ 31 & - & - \\ 32 & - & - \\ 33 & - & - \\ 34 & 0 & 2 \\ 35 & 2 & 1 \\ 36 & 4 & 0 \\ 37 & - & - \\ 38 & - & - \\ 39 & - & - \\ 40 & - & - \\ 41 & - & - \\ 42 & - & - \\ 43 & 1 & 2 \\ 44 & 3 & 1 \\ 45 & 5 & 0 \\ 46 & - & - \\ 47 & - & - \\ 48 & - & - \\ 49 & - & - \\ 50 & - & - \\ 51 & 0 & 3 \\ 52 & 2 & 2 \\ 53 & 4 & 1 \\ 54 & 6 & 0 \\ 55 & - & - \\ 56 & - & - \\ 57 & - & - \\ 58 & - & - \\ 59 & - & - \\ 60 & 1 & 3 \\ 61 & 3 & 2 \\ 62 & 5 & 1 \\ 63 & 7 & 0 \\ 64 & - & - \\ 65 & - & - \\ 66 & - & - \\ 67 & - & - \\ 68 & 0 & 4 \\ 69 & 2 & 3 \\ 70 & 4 & 2 \\ 71 & 6 & 1 \\ 72 & 8 & 0 \\ 73 & - & - \\ 74 & - & - \\ 75 & - & - \\ 76 & - & - \\ 77 & 1 & 4 \\ 78 & 3 & 3 \\ 79 & 5 & 2 \\ 80 & 7 & 1 \\ 81 & 9 & 0 \\ 82 & - & - \\ 83 & - & - \\ 84 & - & - \\ 85 & 0 & 5 \\ 86 & 2 & 4 \\ 87 & 4 & 3 \\ 88 & 6 & 2 \\ 89 & 8 & 1 \\ 90 & 10 & 0 \\ 91 & - & - \\ 92 & - & - \\ 93 & - & - \\ 94 & 1 & 5 \\ 95 & 3 & 4 \\ 96 & 5 & 3 \\ 97 & 7 & 2 \\ 98 & 9 & 1 \\ 99 & 11 & 0 \\ 100 & - & - \\ 101 & - & - \\ 102 & 0 & 6 \\ 103 & 2 & 5 \\ 104 & 4 & 4 \\ 105 & 6 & 3 \\ 106 & 8 & 2 \\ 107 & 10 & 1 \\ 108 & 12 & 0 \\ 109 & - & - \\ 110 & - & - \\ 111 & 1 & 6 \\ 112 & 3 & 5 \\ 113 & 5 & 4 \\ 114 & 7 & 3 \\ 115 & 9 & 2 \\ 116 & 11 & 1 \\ 117 & 13 & 0 \\ 118 & - & - \\ 119 & 0 & 7 \\ 120 & 2 & 6 \\ 121 & 4 & 5 \\ 122 & 6 & 4 \\ 123 & 8 & 3 \\ 124 & 10 & 2 \\ 125 & 12 & 1 \\ 126 & 14 & 0 \\ 127 & - & - \\ \hline 128 & 1 & 7 \\ 129 & 3 & 6 \\ 130 & 5 & 5 \\ 131 & 7 & 4 \\ 132 & 9 & 3 \\ 133 & 11 & 2 \\ 134 & 13 & 1 \\ 135 & 15 & 0 \\ 136 & 0 & 8 \\ 137 & 2 & 7 \\ 138 & 4 & 6 \\ 139 & 6 & 5 \\ 140 & 8 & 4 \\ 141 & 10 & 3 \\ 142 & 12 & 2 \\ 143 & 14 & 1 \\ 144 & 16 & 0 \\ 145 & 1 & 8 \\ 146 & 3 & 7 \\ 147 & 5 & 6 \\ 148 & 7 & 5 \\ 149 & 9 & 4 \\ 150 & 11 & 3 \\ 151 & 13 & 2 \\ 152 & 15 & 1 \\ 153 & 17 & 0 \\ 154 & 2 & 8 \\ 155 & 4 & 7 \\ 156 & 6 & 6 \\ 157 & 8 & 5 \\ 158 & 10 & 4 \\ 159 & 12 & 3 \\ 160 & 14 & 2 \\ 161 & 16 & 1 \\ 162 & 18 & 0 \\ 163 & 3 & 8 \\ 164 & 5 & 7 \\ 165 & 7 & 6 \\ 166 & 9 & 5 \\ 167 & 11 & 4 \\ 168 & 13 & 3 \\ 169 & 15 & 2 \\ 170 & 17 & 1 \\ 171 & 19 & 0 \\ \end{array} $$

$\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.