A currency called a mathik has only 1, 3, and 6 mathik bills. How many ways can one pay 300 mathiks?

Question

I have an idea on how to solve it, but there are too many ways for substitution. Do I use recursion?
For avoidance of doubt, paying 297 1-mathik bills and then a 3-mathik one is the same as paying a 3-mathik bill and then 297 1-mathik bills.

Answer 1

The fact that there are only the three denominations $1,$ $3,$ and $6,$ where $1$ divides $3$ and $3$ divides $6,$ helps keep things less complicated than they might have been.

To avoid counting the same way of paying the bill twice, you could pay the six-mathik bills first, then the three-mathik bills, then the one-mathik bills.

You could solve the problem by recursion. I'd recommend only dealing with total debts that are divisible by $6,$ and keeping track not only of how many ways you can pay each with just six-, three-, and one-mathik bills but also how many ways you can pay using just three-mathik and one-mathik bills.

The number of ways you can pay $6(n+1)$ mathiks then is the number of ways you can pay the first $6$ mathiks with a six-mathik bill and the remaining $6n$ mathiks using any combination of bills, plus the number of ways you can pay the first $6$ mathiks with $2$ three-mathik bills and the remaining $6n$ mathiks using any combination of three-mathik and one-mathik bills, plus one way in which you pay the entire debt with $6(n+1)$ one-mathik bills.

---

Here's another approach:

The greatest number of six-mathik bills one can use when paying $300$ matiks is $50$ bills. There is only one way to pay the bill while using $50$ six-mathik bills. $$50\times6=300.$$

You can also pay using exactly $49$ six-mathik bills and some other bills. There are exactly three ways to do this: \begin{align} 49 \times 6 + 2\times3 = 300,\\ 49 \times 6 + 1\times3 + 3\times1= 300,\\ 49 \times 6 + 6\times1 = 300.\\ \end{align}

There are exactly five ways to pay while using exactly $48$ six-mathik bills: \begin{align} 48\times 6 + 4\times3 = 300,\\ 48\times 6 + 3\times3 + 3\times1= 300,\\ 48\times 6 + 2\times3 + 6\times1= 300,\\ 48\times 6 + 1\times3 + 9\times1= 300,\\ 48\times 6 + 12\times1 = 300.\\ \end{align}

Do you see a pattern? Can you find the answer now?

Answer 2

You have the following possible partitions

$300=\underbrace{\underbrace{1+1+1}_3+\underbrace{1+1+1}_3}_6+\underbrace{\underbrace{1+1+1}_3+\underbrace{1+1+1}_3}_6+\underbrace{1+1+1}_3+1+1+...+1=$

You can regroup any packet of three bills of $1\,\mathtt{mathik}$ into bills of $3\,\mathtt{mathiks}$ and you can make at most $100$ such packets.

But then you can also regroup two bills of $3\,\mathtt{mathiks}$ into bills of $6\,\mathtt{mathiks}$. From a partition that contains $n=(2k)$ or $n=(2k+1)$ bills of $3\,\mathtt{mathiks}$ you can make at most $p=k+1$ partitions.

So I will describe the partitions with the number of packets of $3$ we can make

$\begin{array}{r|l|l|l} n & \text{3 bills partitions} & p & \text{6 bills partitions*}\\ \hline 0 & 111111111111111111111111111111111111....1 & 1 & \text{-}\\ 1 & 3111111111111111111111111111111111....1 & 1 & \text{3}\\ 2 & 33111111111111111111111111111111....1 & 2 & \text{33, 6}\\ 3 & 333111111111111111111111111111....1 & 2 &\text{333, 63}\\ 4 & 3333111111111111111111111111....1 & 3 &\text{3333, 633, 66}\\ 5 & 33333111111111111111111111....1 & 3 &\text{33333, 6333, 663}\\ ...& ................................ & ...\\ 98 & 33333333....3111111 & 50\\ 99 & 33333333....33111 & 50\\ 100 & 33333333....333 & 51\\ \end{array}$

(*) I do not write the trailing $111...$ if any.

So we get $N=1+1+2+2+3+3+...+50+50+51=2(1+2+3+...+50)+51$

$N=2(\frac{50\times 51}{2})+51=51^2=2601$

Answer 3

The following holds:

• The number $ \color{blue}{j}$ of $6$ mathik bills we can use is $0\leq j \leq \frac{300}{6}=50$.

• Since then $300-6j$ mathiks are left, the number $\color{blue}{k}$ of $3$ mathik bills we can use is $$0\leq k\leq\frac{300-6j}{3}=100-2j$$

• The rest is left for $1$ mathik bills.

We conclude the number of possibilities is \begin{align*} \sum_{\color{blue}{j}=0}^{50}\sum_{\color{blue}{k}=0}^{100-2j}1&=\sum_{j=0}^{50}(101-2j)\\ &=51\cdot 101-2\cdot\frac{50\cdot 51}{2}\\ &=51^2\\ &=\color{blue}{2601} \end{align*}

Answer 4

The coefficient on $x^{300}$ in the following polynomial: $$ \left(\sum_{k=0}^{300}x^k\right) \left(\sum_{k=0}^{100}x^{3k}\right) \left(\sum_{k=0}^{50}x^{6k}\right) $$ which is $2601$ according to Maple.

Answer 5

If you look at the problem in general, that is, replace $300$ with $n$, you can let the number of ways be $a(n)$. By looking at the first few values of $a(n)$ you will see that each value repeats three times. That is, let $b(n)=a(3n)$, then $a(n)=b(\lfloor n/3\rfloor)$. By searching in OEIS, http://oeis.org/A002620 you will find that the sequence $b(n)$ is the sequence of quarter-squares with a different offset. See more details in the OEIS link. In your case the answer is $\lfloor(300/3+2)^2/4\rfloor=2601$.

Answer 6

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

In dealing with constraints, Iverson Brackets are quite useful . Namely,

\begin{align} &\bbox[#ffe,10px]{\ds{\sum_{a_{1} = 0}^{\infty} \sum_{a_{3} = 0}^{\infty}\sum_{a_{6} = 0}^{\infty} \bracks{a_{1} + 3a_{3} + 6a_{6} = 300}}} = \sum_{a_{6} = 0}^{\infty}\sum_{a_{3} = 0}^{\infty}\sum_{a_{1} = 0}^{\infty} \bracks{a_{1} = 300 - 3a_{3} + 6a_{6}} \\[5mm] = &\ \sum_{a_{6} = 0}^{\infty}\sum_{a_{3} = 0}^{\infty} \bracks{300 - 3a_{3} + 6a_{6} \geq 0} = \sum_{a_{6} = 0}^{\infty}\sum_{a_{3} = 0}^{\infty} \bracks{a_{3} \leq 100 - 2a_{6}} \\[5mm] = &\ \sum_{a_{6} = 0}^{\infty}\bracks{100 - 2a_{6} \geq 0} \sum_{a_{3} = 0}^{100 - 2a_{6}}1 = \sum_{a_{6} = 0}^{\infty}\bracks{a_{6} \leq 50}\pars{101 - 2a_{6}} = 101\sum_{a_{6} = 0}^{50}1 - 2\sum_{a_{6} = 0}^{50}a_{6} \\[5mm] = &\ 101 \times 51 - 2\,{50 \times 51 \over 2} = \bbx{2601} \end{align}