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?
On
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.
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.