# Finding the numbers that are non-attainable and partitioning.

I have been working through some past math competition problems and have had difficulty in solving some of the ones on number theory. Examples include:

1) If we need 27 cents can we make it using 5 cents and 8 cents?

2) Given 1. How many ways can you make it from 20 cents, 10 cents and 5 cent coins? 3) How may ways are there of making 4 (using addition) with numbers (non-negative) less than 4? 4) What is the highest non-attainable number when adding numbers from 6,9 and 20? I was able to solve these problems with the use of trial and error however, this seemed highly inefficient due to the great number of such questions in the competitions. So, I was wondering whether there is a formula that would allow me to quickly solve them. Help would be appreciated, Thank you :) ## 5 Answers Note: Here are two different answers of number 2). Both of them could be interesting when looking for a systematic approach. The first one provides a more general approach, the second one is presumably more efficient when fast calculation is needed. In both cases it is helpful to observe that finding solutions in non-negative integers of \begin{align*} 5p+10q+20r=100 \end{align*} is equivalent to finding solutions of non-negative integers of \begin{align*} p+2q+4r=20 \end{align*} So, in the following we are looking for the number of partitions of20$with elements from$\{1,2,4\}$. First approach: Generating Functions We develop a formula for the number of partitions of$n$with elements from$\{1,2,4\}$. Question$2$is answered by applying the formula to$n=20$. Zero or more$1's can be algebraically described as \begin{align*} z^0+z^1+z^2+z^3+\cdots\tag{1} \end{align*} with the power ofz$in (1) indicating the number of$1$'s. Zero or more$2's can be algebraically described as \begin{align*} z^0+z^2+z^4+z^6+\cdots\tag{2} \end{align*} with the power ofz$in (2) indicating the number of used$2$'s in the partition. The number of partitions of$n$with elements from$\{1,2,4\}$can thereby described as the coefficients of$z^n$in the generating function$F(z)with \begin{align*} F(z)&=\left(1+z+z^2+z^3+\cdots\right)\left(1+z^2+z^4+z^6+\cdots\right)\left(1+z^4+z^8+z^{12}+\cdots\right)\\ &=\frac{1}{1-z}\cdot\frac{1}{1-z^2}\cdot\frac{1}{1-z^4}\\ &=\left(\frac{1}{1-z}\right)\left(\frac{1}{1-z}\cdot\frac{1}{1+z}\right)\left(\frac{1}{1-z}\cdot\frac{1}{1+z}\cdot\frac{1}{1-iz}\cdot\frac{1}{1+iz}\right)\\ &=\frac{1}{(1-z)^3}\cdot\frac{1}{(1+z)^2}\cdot\frac{1}{1-iz}\cdot\frac{1}{1+iz} \end{align*} The coefficient ofz^n$of the generating function$F(z)$contains the information of the number of wanted partitions. The following calculation is more or less straightforward. We use partial fraction decomposition of$F(z)$and develop each term as power series and finally extract the coefficient of$z^n. Using partial fraction decomposition we obtain \begin{align*} F(z)&=\frac{9}{32}\frac{1}{1-z}+\frac{1}{4}\frac{1}{(1-z)^2}+\frac{1}{8}\frac{1}{(1-z)^3}+\frac{5}{32}\frac{1}{1+z}\\ &\qquad+\frac{1}{16}\frac{1}{(1+z)^2}+\frac{1-i}{16}\frac{1}{1-iz}+\frac{1+i}{16}\frac{1}{1+iz}\\ &=\frac{9}{32}\sum_{k=0}^{\infty}z^k+\frac{1}{4}\sum_{k=0}^{\infty}\binom{-2}{k}(-z)^k +\frac{1}{8}\sum_{k=0}^{\infty}\binom{-3}{k}(-z)^k+\frac{5}{32}\sum_{k=0}^{\infty}(-z)^k\\ &\qquad+\frac{1}{16}\sum_{k=0}^{\infty}\binom{-2}{k}z^k+\frac{1-i}{16}\sum_{k=0}^{\infty}(iz)^k +\frac{1+i}{16}\sum_{k=0}^{\infty}(-iz)^k\tag{3}\\ \end{align*} Since\binom{-n}{k}=\binom{n+k-1}{k}(-1)^kwe observe \begin{align*} \binom{-2}{k}&=\binom{k+1}{k}(-1)^k=(-1)^k(k+1)\\ \binom{-3}{k}&=\binom{k+2}{k}(-1)^k=(-1)^k\frac{(k+2)(k+1)}{2} \end{align*} In the following we use the coefficient of operator[z^n]$to denote the coefficient$a_n$in$A(z)=\sum_{k=0}^{\infty}a_kz^k$. $$[z^n]A(z)=[z^n]\sum_{k=0}^{\infty}a_kz^k=a_n$$ Now we are ready to extract the coefficient of$[z^n]$from the generating function$F(z)in (3) \begin{align*} [z^n]F(z)&=\frac{9}{32}+\frac{1}{4}\binom{-2}{n}(-1)^n+\frac{1}{8}\binom{-3}{n}(-1)^n+\frac{5}{32}(-1)^n\\ &\qquad+\frac{1}{16}\binom{-2}{n}+\frac{1-i}{16}i^n+\frac{1+i}{16}(-i)^n\\ &=\frac{9}{32}+\frac{1}{4}(n+1)+\frac{1}{16}(n+2)(n+1)+\frac{5}{32}(-1)^n\\ &\qquad+\frac{1}{16}(-1)^n(n+1)+\frac{1-i}{16}i^n+\frac{1+i}{16}(-i)^n\\ &=\ldots\\ &= \begin{cases} \frac{1}{16}\left(n^2+6n+7-2(-1)^{\frac{n+1}{2}}\right)\qquad \qquad& n \text{ odd}\\ \frac{1}{16}\left(n^2+8n+14+2(-1)^{\frac{n}{2}}\right)\qquad \qquad& n \text{ even} \end{cases} \end{align*} Finally we obtain forn=20$$$[z^{20}]F(z)=\frac{1}{16}\left(20^2+8\cdot 20+14+2(-1)^{\frac{20}{2}}\right)=\frac{576}{16}=36$$  Second approach: Iteratively from$\{1,2\}$to$\{1,2,4\}$This is an elementary approach by first obtaining a formula$a_n$which contains the number of partitions with elements from$\{1,2\}$. Once we have found$a_n$we use it as basis to find a formula for the number of partitions with elements of the extended set$\{1,2,4\}$. In order to find$a_n$we use the Ansatz: $$n=2p+r\qquad\qquad r=0,1$$ We see that$n-r=2p$is even and the number of possible summands$2$of a partition of$n=2p+r$is$0,1,2,\ldots,p. Therefore we obtain \begin{align*} a_n=p+1=\frac{n-r}{2}+1=\left\lfloor\frac{n}{2}\right\rfloor+1 \end{align*} We observe \begin{align*} r= \begin{cases} 1&\qquad n\text{ odd}\\ 0&\qquad n\text{ even} \end{cases} \end{align*} So,r=\frac{1-(-1)^n}{2}$and we obtain this way the number$a_n$of partitions of$n$containing elements from$\{1,2\}\begin{align*} a_n&=\frac{n-r}{2}+1=\frac{2n+3+(-1)^n}{4}\tag{4} \end{align*} In order to determine the numberc_n$equal the number of partitions of the extended set$\{1,2,4\}we use a similar approach as before. We start with $$n=4p+r\qquad\qquad r=0,1,2,3$$ We get \begin{align*} c_n=a_n+a_{n-4}+a_{n-8}+\ldots+a_{n-4p}\qquad\qquad n\geq 1 \end{align*} Settingn=20$we obtain using formula$a_nof (4) \begin{align*} c_{20}&=a_{20}+a_{16}+a_{12}+a_8+a_4+a_0\\ &=\frac{44}{4}+\frac{36}{4}+\frac{28}{4}+\frac{20}{4}+\frac{12}{4}+\frac{4}{4}\\ &=11+9+7+5+3+1\\ &=36 \end{align*} Note: We calculatedc_n$without deriving a closed formula for it. But, we could also derive one from $$c_n=\sum_{j=0}^{p}a_{n-4j}$$ and the formula for$a_n$of (4) by considering the different values of$r=0,1,2,3$. Begin with an intuitive approach: 27 Plus 8 equals 35 35 is a multiple of 5. 27 times 8 ends in five, which is also a multiple of 5. The purpose of turning over numbers is to help the mind to see alternatives. Then you can understand what lies beneath equations. For the first question, see the artilce on the coin problem. You will need the notion of a gcd and other tools from elementary number theory. The third question is answered by the partition function. We have$p(4)=5$. If you want the summands less than$4, then we have \begin{align*} 4 & = 1+1+1+1,\\ & =1+1+2,\\ & =1+3,\\ & = 2+2. \end{align*} There is a general formula forp(n)$and an asymptotic formula, namely $$p(n) \sim \frac {1} {4n\sqrt3} \exp\left({\pi \sqrt {\frac{2n}{3}}}\right) \mbox { as } n\rightarrow \infty.$$ Some of the following answers are non-formulaic. Luckily, they are one-liners. 1. If we need$27¢$, can we make it using$5¢$and$8¢$coins? The$8¢$pieces must number from$0$to$3$, so the second digit must be$\{0,8,6,4,5,3,1,9\}$which is not$7$, so no. 1. How many ways can you make$\$1$ from $20¢$, $10¢$ and $5¢$ coins?

Because of the regular intervals of the coins, this is a path problem where O = $20¢$, X = $10¢$ and V = $5¢$:

$0$1.00
| O   O   O   O   O    |
| X X X X X X X X X X  |
| VVVVVVVVVVVVVVVVVVVV |


Order does not matter, so moves are either right or down. Because one cannot always exit the top row, assume that there are only $n = 5$ junctions and multiply by 2 for the extra options on the bottom row. There is 1 path terminating on the top row, $\binom{n}{1} = n$ paths terminating on the middle row, and $2 \cdot \binom{n+1}{2} = n(n+1)$ terminating on the bottom row. $f(n) = 1 + 2 n + n^2 = (n+1)^2$, so $f(5) = 36$

From the bottom row up, there are $n = 10$ junctions, so rather than an undercount which may be multiplied into compliance, the overcount, $\binom{n/2}{n/2-2} = \dfrac{n}{2} \left(\dfrac{n}{2}-1\right)$, must be subtracted yielding $f(n) =1 + n + \left(\dfrac{n}{2}\right)^2$ for even $n$.

1. How may ways are there of making 4 (using addition) with numbers (non-negative) less than 4?

As both positive rationals and irrationals have infinite ways to add to 4, I'm assuming natural numbers: Simplest approach: $1+1+1+1 = 2+1+1 = 2+2 = 3+1 = 4$; 4 ways.

1. What is the highest non-attainable number when adding numbers from 6,9 and 20?

Given some natural number $n$, $2 \cdot 6 = 12$ and $9+6 = 15$, so every $6 + 3n$ is attainable. Similarly, $26 + 3n$ and $46 + 3n$ are attainable. The highest unattainable number is $43$.

The fundamental question at work here is "what is the (typed) value of unity". Each of the solution results in $Z$ units of some $\Omega$ "coin" which is valued at $\pi$, the same as the original coins. I use $\alpha_n$ to denote the value of the original coins and $x_n$ to denote the number of coins.

$$\begin{eqnarray} \Omega &=& \left(\sum_{n=1}^{k-1} \frac{\alpha_nx_n}{Z}\right) + \frac{\alpha_k\left(Z-\sum_{n=1}^{k-1}x_n\right)}{Z} && \\ &=& \alpha_k - \frac{\sum_{n=1}^{k-1} (\alpha_k-\alpha_n)x_n}{Z}\\ \frac{1}{Z} &=& \frac{\alpha_k - \Omega}{\sum_{n=1}^{k-1} (\alpha_k-\alpha_n)x_n}\\ Z &=& \sum_{n=1}^{k-1} x_n + \frac{\pi-\sum_{n=1}^{k-1} \alpha_nx_n}{\alpha_k} \\ \Omega Z &= \pi \end{eqnarray}$$

A good starting point is to note that $Z * \frac{1}{Z} = 1$

### Exercise 1

$$\begin{eqnarray} \Omega &=& 5a/Z + 8(Z-a)/Z && \\ &=& 8 - \frac{3a}{Z}\\ \frac{1}{Z} &=& \frac{8 - \Omega}{3a}\\ Z &=& a + (27-5a)/8 \\ \Omega Z &=& 27\\ 1 <= &\Omega& <= 27 &&\\ 0<=&a&<= 5 &&\\ 0<=&Z-a&<= 3 &&\\ 1<=&Z&<= 8 && \end{eqnarray}$$

Here the key is to use modulo arithmetic to solve for $Z = a + b$. I start with $Z * \frac{1}{Z} = 1$ and simplify to get:

$$\begin{eqnarray} \frac{8 - \Omega}{3a}\frac{8a + 27-5a}{8} &=& 1 \\ (8 - \Omega)(3a + 27) &=& 24a \\ (24 - 3\Omega)a-24a &=& 27(8 -\Omega) \\ (27-3a)\Omega &=& 216 \end{eqnarray}$$

### Exercise 2

The trick here is to partition the problem:

$$\Omega_k = \frac{Z_1\Omega_1+\alpha_k\left(Z_k-Z_1\right)}{Z_k}$$

### Exercise 3

$$\begin{eqnarray} \Omega &=& a/Z + 2b/Z + 3(Z-(a+b))/Z && \\ &=& 3 - \frac{2a + b}{Z}\\ \frac{1}{Z} &=& \frac{3 - \Omega}{2a + b}\\ Z &=& a + b + (4-a-2b)/3 \\ \Omega Z &=& 4\\ 1 <= &\Omega& < 4 &&\\ 0<=&a&<= 4 &&\\ 0<=&b&<= 2 &&\\ a+b+c-Z&=&0 \\ 1<=&Z&<= 4 && \end{eqnarray}$$

Here the key is that $\Omega Z = 4$, with $Z \in \{1,2,3,4\}$ so $\Omega \in \{4.0, 2.0, 1.\overline{3},1.0 \}$, taking into account the constraints each choice of $Z$ places on $a, b, \text{ and } c$.

### Exercise 4

I'm not sure that this question belongs in the same category. The question requires two numbers $a$ and $b$, one odd and one even. Assuming $b>a$, if the gcd of the numbers is 1, then a sequence of length $b+1$ exists made from expressions starting at $a*(b)+b*(0)$ and ending at $a*(0)+b*(q)$, where $0\le q \le a$ is chosen to keep the sum between $a*(b-1)+1$ and $a*b$. Each value must be unique, so this makes the extreme upper limit $a*(b-1)-1$. If $a*(b-1)-1 \equiv 0 \text{ mod } b$, then the value is $a*(b-2)-1$.