I have $n = 1234a + 56b + 7c$.
Is there a way to check if a triplet $(a,b,c)$ exists, such that all three are non-negative?
Asked
Active
Viewed 84 times
2
-
1What is the constraint, if any, on $n$? – Joffan Jun 14 '16 at 18:07
-
3See the coin problem. – Arthur Jun 14 '16 at 18:07
-
n < 10^10 as given – Sayan Ghosh Jun 14 '16 at 18:07
-
@Arthur can you explain how to relate the coin problem to this – Sayan Ghosh Jun 14 '16 at 18:09
-
2You can ignore $b$ - do you see why? – Joffan Jun 14 '16 at 18:09
-
certainly $n<1234$ must be a multiple of $7$... – gt6989b Jun 14 '16 at 18:09
-
@Joffan no, can u please explain – Sayan Ghosh Jun 14 '16 at 18:09
-
$56=8\times 7$ so just increase $c$ by $8\times b$ and set $b=0$ – Joffan Jun 14 '16 at 18:10
-
@gt6989b 1359257 = 1234x1101 + 56 x 11 + 7x1 here 1101 is not a multiple of 7 – Sayan Ghosh Jun 14 '16 at 18:14
-
3You can relate the coin problem to this by saying "I have coins worth $1234$, $56$ and $7$. What values can I make from that?" Note that $a, b, c$ in this interpretation tells you how many you have of each coin. – Arthur Jun 14 '16 at 18:34
-
@SayanGhosh this $n > 1234$... – gt6989b Jun 14 '16 at 20:47
1 Answers
3
Essentially, as Arthur mentions in the comments, this is a version of the Coin problem, finding out which values $n$ can be achieved using coins of value $1234, 56,$ and $7$.
The coin of value $56$ (and hence the variable $b$) does not change which values of $n$ are possible, as any value of $b$ can also be achieved by modifying the value of $c$ (since $7 \mid 56$). This simplifies the analysis to a two coin problem for which the answer is well-described in the wikipedia article.
However to go through the process, it's apparent that only multiples of $7$ are possible for $n<1234$. Above that, since $1234 \equiv 2 \bmod 7$, values of $n \equiv k \in \{0,2\} \bmod 7$ are possible up to $2468$, which then opens up $n\equiv 4 \bmod 7$, etc until $6\times 1234 = 7404$ fills the last gap of $n \equiv 5 \bmod 7$. The $6$ values prior to that are also achievable, of course, so the largest number for which there is no non-negative $(a,b,c)$ combination possible is $n=7404-7 = 7397$.
-
If the constant $56$ in the problem were replaced with some other number roughly the same size but not divisible by $7$ - say, $65$ - then this would mean the variable $a$ could be disregarded since any multiple of $1234$ could easily be comprised of a suitable combination of the two smaller constants. – Joffan Jun 14 '16 at 21:21