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 :)
 A: 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 for $p(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. 
$$
A: 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.
A: 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$.
A: Some of the following answers are non-formulaic. Luckily, they are one-liners.


*

*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.


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


*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.


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