|
Smart? (pg. 11)
|
View this Thread in Original format
| Resnick |
sry i didnt read other answers to this question
but is it (A*B) - (A+B)?? |
|
|
| Flyboy217 |
| quote: | Originally posted by Resnick
sry i didnt read other answers to this question
but is it (A*B) - (A+B)?? |
Yes, that's exactly correct :). It's easy to find by just experimenting with small numbers. Now the trick is proving it.
DigiNut, I think it's actually easier to think of it without specifically using modular arithmetic. Basically, think about a value after which you know ALL values can be achieved, and work your way back. If you have some value x*A + y*B, then what does taking away one A and adding a B do to your value? You can obviously achieve all prices P where P%A = 0 and P%B = 0. How do you achieve the rest?
To be honest, my proof is inelegant... but it's still neat to figure out.
I'll explain more later. I'm currently making a mix :gsmile: |
|
|
| DigiNut |
| quote: | Originally posted by Flyboy217
DigiNut, I think it's actually easier to think of it without specifically using modular arithmetic. Basically, think about a value after which you know ALL values can be achieved, and work your way back. If you have some value x*A + y*B, then what does taking away one A and adding a B do to your value? You can obviously achieve all prices P where P%A = 0 and P%B = 0. How do you achieve the rest? |
Ok, here's one way of looking at it:
If you take A*B, you know that you have a number that's divisible by BOTH A and B (that is, P%A=0 and P%B=0 like you said). If A and B are relatively prime, you know the following things:
- (A+B)%A = B, and (A+B)%B = A. Therefore (A+B)%A > 0, and (A+B)%B > 0. (1)
- If you subtract A from (A*B), you cause the result to be indivisible by B (with a remainder of A). (2)
- If you again subtract B from this total, you cause it to be indivisible by A (with a remainder of B). (3)
- You know that the result after step (2) will not suddenly become divisible by B again after step (3), because of lemma (1).
- (A*B) - A - B = (A*B) - (A+B)
- Therefore, this number is guaranteed to be indivisible by both A and B.
Now, I know that (A*B) - (A+B) can be written as (A-1)(B-1) - 1. So the first value where you CAN make ANY price is (A-1)(B-1). I'm sure there's a way to prove that when you have (B-1) A's and (A-1) B's already, that you can generate prices in increments of exactly 1, but I haven't worked out exactly how yet.
Actually, that last part seems intuitive, but I'm just not sure how to spell it out... |
|
|
| Flyboy217 |
| quote: | Originally posted by DigiNut
Ok, here's one way of looking at it:
If you take A*B, you know that you have a number that's divisible by BOTH A and B (that is, P%A=0 and P%B=0 like you said). If A and B are relatively prime, you know the following things:
- (A+B)%A = B, and (A+B)%B = A. Therefore (A+B)%A > 0, and (A+B)%B > 0. (1)
- If you subtract A from (A*B), you cause the result to be indivisible by B (with a remainder of A). (2)
- If you again subtract B from this total, you cause it to be indivisible by A (with a remainder of B). (3)
- You know that the result after step (2) will not suddenly become divisible by B again after step (3), because of lemma (1).
- (A*B) - A - B = (A*B) - (A+B)
- Therefore, this number is guaranteed to be indivisible by both A and B.
Now, I know that (A*B) - (A+B) can be written as (A-1)(B-1) - 1. So the first value where you CAN make ANY price is (A-1)(B-1). I'm sure there's a way to prove that when you have (B-1) A's and (A-1) B's already, that you can generate prices in increments of exactly 1, but I haven't worked out exactly how yet.
Actually, that last part seems intuitive, but I'm just not sure how to spell it out... |
First, some notation: A%x=0 is properly written as A = 0 (mod x), read "A is congruent to zero, modulo x". (Actually, the congruency sign properly has three bars, not two...)
It's true that AB-A-B is indivisible by both A and B. This can be proven by noting that AB=0 mod A and mod B, and therefore only numbers different from AB by a multiple of A are congruent to 0 mod A (and similarly for B).
What's important is that AB-A-B is not a positive linear combination of A and B though. I'll write up an explanation when I get a chance. You're thinking along the right lines though... |
|
|
| Flyboy217 |
Okay. This is the ugliest, dirtiest proof I've ever written. If you don't follow it, props to you for not being f*ed in the head...
------
Call a price "attainable" if you can purchase an item of that price with exact change.
Using 0 of coin B and as many of coin A as we need, We can attain all prices C where C = 0 (mod A) (i.e., all multiples of A) starting with C = 0*B.
Using 1 of coin B and as many of coin A as we need, we can attain all prices C = xA + B. I.e., we can attain all prices C where C = B (mod A) starting with C = 1*B.
Using at most y of coin B, we can attain all prices C where C = {0*B, 1*B, ..., y*B} mod A.
Note that n*B mod A are distinct for all 0 <= n <= A-1. Thus, we can attain all prices greater than or equal to C = (A-1)B that have the same congruency as (A-1)B mod A.
Hence, (A-1)(B)-A is not attainable (since (A-1)B = (A-1)B-A (mod A) and (A-1)B is the smallest price congruent to (A-1)B mod A that is attainable). However, (A-1)B-A+1 is attainable, because it is congruent to a value other than (A-1) mod A, all other congruencies have been satisfied, and it is greater than (A-2)B (which was the last satsified congruency).
Therefore, (A-1)B - A + 1 = (A-1)(B-1) is the smallest value for which all prices greater than or equal to it can be satisfied.
-
||
- |
|
|
| Resnick |
| ^^ why prove something, when you can just write a program in c to do it for you :D |
|
|
| Flyboy217 |
| quote: | Originally posted by Resnick
^^ why prove something, when you can just write a program in c to do it for you :D |
Amazing! A program that solves for ALL the integers? I want it! |
|
|
| DigiNut |
| quote: | Originally posted by Flyboy217
Amazing! A program that solves for ALL the integers? I want it! |
code:
#include
void main() {
int a, b;
scanf("%d %d", &a, &b);
printf("%d", (a-1)*(b-1) - 1);
return;
}
:D |
|
|
| drizzt81 |
| quote: | Originally posted by DigiNut
code:
#include
void main() {
int a, b;
scanf("%d %d", &a, &b);
printf("%d", (a-1)*(b-1) - 1);
return;
}
:D |
\
that will fail as soon as a or b are >2^32 on x86 or 2^64 on 64 bit machines.. or 2^128 on 128 bit machines.. well you get my idea, there are integers much bigger than 2^n for n in [0,infinity) |
|
|
| DigiNut |
| quote: | Originally posted by drizzt81
\
that will fail as soon as a or b are >2^32 on x86 or 2^64 on 64 bit machines.. or 2^128 on 128 bit machines.. well you get my idea, there are integers much bigger than 2^n for n in [0,infinity) |
Oh bloody hell, I didn't realize we were getting technical here. :p
Fine, just set up two linked lists to perform the multiplication, then it will only fail when it runs out of memory. :p Sure, that's not infinite, but I'd be willing to bet that you'd spend the rest of your life typing in a set of numbers that would cause it to run out of memory. :p |
|
|
| Flyboy217 |
| quote: | Originally posted by DigiNut
Oh bloody hell, I didn't realize we were getting technical here. :p
Fine, just set up two linked lists to perform the multiplication, then it will only fail when it runs out of memory. :p Sure, that's not infinite, but I'd be willing to bet that you'd spend the rest of your life typing in a set of numbers that would cause it to run out of memory. :p |
Hmm... somehow I think he's just trying to point out that any machine must fail when trying to validate an infinite number of inputs. Then again, computers are currently crucial in solving the four-color theorem, so I wont bash them too much.
It also brings up an interesting point from cognitive science about why humans can seemingly use reasoning that seems to be outside of the bounds of Turing machines... |
|
|
| DigiNut |
| quote: | Originally posted by Flyboy217
Then again, computers are currently crucial in solving the four-color theorem, so I wont bash them too much. |
I know we've gotten off-topic, but what is that? |
|
|
|
|
