duke_nemmerle
Sep1-08, 10:55 PM
1. The problem statement, all variables and given/known data
Show, by induction, that for all whole number of Roubles greater than 7, the amount can be given without change by using only 3 rouble and 5 rouble notes.
2. Relevant equations
In other words for all n \in N, n > 7, there exist a, b \in N such that n = 5a + 3b
3. The attempt at a solution
This is true for n = 8
I'm wondering if I can't use strong induction. I've noticed that all of these n's appear to be writable with a \in \{0,1,2\} while letting b take on any value, and that when you express the integers greater than 7 in order the a's when thus constrained go 1, 0, 2, 1, 0, 2, etc and each time around the b increments by one for each repetition of a. So, I don't know if I can weasel something out of this like to go from n to n+1 means either going from 1 to 0, 0 to 2, or 2 to 1 in a with the associated incrementation, but I just get the feeling that this isn't the way to go. It seems I'm missing something easier.
Show, by induction, that for all whole number of Roubles greater than 7, the amount can be given without change by using only 3 rouble and 5 rouble notes.
2. Relevant equations
In other words for all n \in N, n > 7, there exist a, b \in N such that n = 5a + 3b
3. The attempt at a solution
This is true for n = 8
I'm wondering if I can't use strong induction. I've noticed that all of these n's appear to be writable with a \in \{0,1,2\} while letting b take on any value, and that when you express the integers greater than 7 in order the a's when thus constrained go 1, 0, 2, 1, 0, 2, etc and each time around the b increments by one for each repetition of a. So, I don't know if I can weasel something out of this like to go from n to n+1 means either going from 1 to 0, 0 to 2, or 2 to 1 in a with the associated incrementation, but I just get the feeling that this isn't the way to go. It seems I'm missing something easier.