For what $~K~$ does $~n~$ exist for all $~n\ge k~$ if $~n=6X+10Y+25Z~$ where $~n~$ and $~k~$ are natural numbers?

Question

Problem statement:

You should notice that for some $~n~$, $~c_n = 0~$ (ie. there are some amounts we cannot make with these three coins). However, starting from some integer $~k~$, $~c_n > 0~$ for all $~n ≥ k~$. Find the minimal such $~k~$, and prove directly (without just showing the series from the generating function $~c(x)~$) that for all $~n ≥ k~$, it is possible to make $~n~$ cents from a combination of $~6, ~~10,~$ and $~25 ~$ cent coins..

This is based on the making change problem but with the penny and nickle replaced by a $~6~$ cent coin.

Attempts at solving:

I rearranged the problem to say "for what $~k~$ does $~n~$ always exist when $~n\ge k~$ and $~n=6X+10Y+25Z~$?" I believe that the answer here is $~40~$ but I have no idea why, and I have no way to prove that all $~n\ge 40~$ exist. The number seems to have no connection to any traits of $~6,~~10,~$ and $~25~$.

Answer 1

It turns out that any even number larger than or equal to $16$ can be obtained from having coin values of $6$ and $10$. I'll leave this for you to show.

So now we need to find the smallest odd number $m$ such that any odd number larger than or equal to $m$ can be represented as a nonnegative linear combination of $6, 10, \text{and } 25$. Note that the representation of $m$ must have an odd number of $25$'s in it. This means that $m-25$ is an even number that can be obtained from $6, 10, \text{and } 25$ value coins.

This tells us that if $m$ is the smallest odd number such that any odd number larger than or equal to $m$ can be represented, then $m-25$ must be the smallest even number such that every even number larger than or equal $m-25$ can be represented.

By our first paragraph, we know that the smallest such even number is $16$. Therefore $m=41$ which gives us $k=40$ like you claimed.

Answer 2

This is the Forbenius coin problem with 3 coins which is surprisingly more complicated than with 2. https://en.wikipedia.org/wiki/Coin_problem#n_=_3

But... okay. With the $6$ and $10$ we can get any even number that is two times any number we can get with $3$ and $5$ and the solution to the Forbenius coin problem with $2$ coins tells us that is. $3*5 -3-5 = 7$ is the largest number we can't get with $3$ and $5$. So $14$ is the largest even number we can't get with $6$ and $10$ and we can get every even number $16$ or higher with just the $6$ and $10$.

If we add $25$ to an even number we can get an odd number so we can get any number greater or equal to $16+25= 41$. (In $n \ge 41$ is even we use the $6$ and $10$ to get it. If $n$ is odd we use the $6$ and $10$ to get $n-25$.) But is it the lowest? Obviously we can get lower even numbers ($16$ and above) but what of lower odds. Can we get $39$?

Well, no... $39$ is odd and $25$ is our only odd value so we must use it to get an odd number and $39 < 50$ so we can only use it once. That means we must get $14$ with just the $6$ and the $10$ and we can't do that.

So... we can't get $39$. We can get every even number greater or equal to $16$. We can get any odd number greater or equal to $41$. Therefore... we can get every number equal or greater than $40$.

=====

Not really helpful but that wikipedia page tells us the largest number we can't get is $\ge \sqrt{3(6*10*25)} - 6-10-25 \approx 26.08$. That doesn't help us much but it's an interesting bound. And $39 \ge 27$. ... meh.....