0

Ok so we have coins with values 1,2 and 3. I was told that the minimum number of coins we need to create number $x$ is this:

$\lfloor {x\over 3 }\rfloor+\lfloor {x\mod3\over 2 }\rfloor +((x\mod3)\mod 2)$

but i simply can't find a way to prove it. I have induction in my mind but i am not sure, and i also tried proof by contradiction , but it got me nowhere...

So any ideas how to prove this?

Mario Zelic
  • 319
  • 1
    The $\lfloor x/3\rfloor$ term is the number of 3¢ coins. The number of additional coins needed is $0$ if $x$ is a multiple of $3$, and $1$ otherwise, so you just need to show that the remaining terms are equal to $1$ when $x\not\equiv 0\pmod3$ and $0$ when $x\equiv 0\pmod3$. This can be done in three cases, since the remaining terms only depend on the value of $x\pmod3$. – Mike Earnest Jun 08 '18 at 19:47

2 Answers2

1

To understand it, I would write down each term for $x$ from $1$ through $6$ and see what they give you. It is applying the greedy algorithm, so the first term is how many $3$s you.

You can prove it by induction once you do $1$ through $6$ by hand. Then if you want to make up $n$, you make up $n-6$ and add two $3$s. As the last two terms recur every $6$ you are there.

Ross Millikan
  • 374,822
1

You could start by showing that $$\left\lfloor {x\bmod3\over 2 }\right\rfloor +((x\bmod3)\bmod 2) =\begin{cases} 0 & x \equiv 0 \pmod 3,\\ 1 & x \not\equiv 0 \pmod 3. \end{cases} $$ The expression $x\bmod 3$ has only three possible values, and you need merely work out the result for each one.

Now consider the maximum amount you can make with $n$ coins, given that the largest coin has value $3.$ It should be easy to show that the number of coins required to make a total value of $x$ is at least $x/3.$ Now consider that the number of coins must be an integer, and the number becomes at least $\lceil x/3 \rceil.$ But by considering each of the three cases for $x\bmod 3,$ you can exhibit how the total $x$ can be made with only $\lceil x/3 \rceil$ coins.

Now show that $\lceil x/3 \rceil$ is equal to the given formula in each of the three cases.

If you want to more rigorous, you can do the proof first for $0,$ $1,$ and $2$, use these as the base case; the inductive assumption is that $x,$ $x+1,$ and $x+2$ all satisfy the formula, and the inductive step is to show that in all three cases you can substitute $x+1$ for $x.$

What I find puzzling is why someone would come up with such an excessively complicated formula in the first place.

David K
  • 98,388