Subtraction

[radosr]

In the subtraction of one 3-digit number from another, Alice and Bob fill in the six digits in the following fashion: Alice chooses a number from 0 to 9, and Bob chooses where to enter it as a digit. They continue until all the blank digits are filled. Some numbers may appear more than once, leading zeroes are permitted as well. Alice is trying to maximize the difference, while Bob is trying to minimize it. If both players play their best, what is the difference?

 

[AlexandreH]

Is a negative difference used in Absolute value?

 

[pruse]

I thought about this for a bit but don't yet know the solution. One thing is clear: Alice can guarantee an outcome of at least 356, as follows.

Label the subtraction problem ABC-DEF.

Let Alice start by picking 5's until Bob either picks A or D to fill in. If he picks A first, then have Alice pick 0's from then on. In that case the worst possible outcome for Alice will be 500-055 = 445. If Bob fills in D first, then have Alice pick 9's from then on. In this case the worst possible outcome for Alice will be 955-599 = 356.

 

[euroazn]

@peterruse
That's the answer :P

 

[pruse]

Ha, really? Intuitively, it does seem to be, but I haven't found a solid reason why Alice can't do better.

 

[PerfectSeek]

Starting with 4 also yields 356 based on the same logic:

400 - 044 = 356 (or 944 - 499 = 445).

I think peterruse definitely had it. I'm not sure if this is the greatest proof, but we can say:

a) If Alice starts with any number less than 4, Bob will place that number in "A" immediately, and the best Alice can do is fill in B-F using zeroes. (eg starting with 3, 300 - 000 = 300)
b) If Alice starts with any number greater than 5, Bob will place that number in "D" immediately, the best Alice can do is fill in 9s for the rest. (eg starting with 6, 999-699 = 300)
c) So we must start with 4 or 5, both of which give us 356.

It looks like we will get symmetrical results for starting with the pairs (4,5), (3,6), (7,2), (8,1) (9,0).

Props to peter for the solution.

 

[enthusiast]

I believe the answer is 400.

PerfectSeek is on the right track with 4 or 5. If Alice would chose 4, then Bob should place 4 in A. 400 000. Difference is 400.

If Alice starts by picking 5. Bob has to pick D to maximize his chances. Alice then picks 9's. 999 599. Difference is 400.

As you can see if Bob picks A 1st when he gets 5, then Alice will pick all 0's. 500 000. Difference is 500. But this not the best solution for Bob, so he should never pick A for the 5 Alice picked.

 

[PerfectSeek]

Enthusiast - what happens if Alice chooses 4, and Bob populates E and F prior to A? Or, if Alice chooses 5, and Bob decide to populate B and C prior to D?

 

[enthusiast]

If Alice choses 5 and Bob populates E and F, then you get 500 055 OR 999 555. The difference would be 445 or 444 which is not good for Bob. So 400 wins here.

If Alice choses 4 and Bob populates E and F, then you get 500 044 OR 999 544. The difference would be 456 or 455 which is not good for Bob. So 400 wins here again.

 

[enthusiast]

If Alice chooses 5, and Bob decide to populate B and C prior to D then Alice would chose 4 as the 3rd digit. Hence we get 955 499 or 455 000 and difference is 456 or 455.

 

[PerfectSeek]

Nice, you're right and thanks for the explanation. I didn't realize that Alice benefited from changing from 4 to 5 (or vice versa). So if Alice chooses 4, and Bob populates EF first, alice will switch to 5, leaving us with 500 - 044 or 999 - 544.

 

[radosr]

400 is the correct answer. Great job, all of you!

 

[euroazn]

Yep, that was clever, I didn't consider that.