ATM logic puzzle

Factual Questions
1

I’ll start by saying I believe this particular puzzle is not possible to solve, but it would be nice if I had proof it’s not possible, so here we go:

Say you’ve been given an ATM card and its PIN. You have to go up to a particular ATM and start using it to withdraw money from the associated account. You’re told the account has some unknown-to-you value X between a known minimum and maximum number of dollars in it, inclusive, The max possible balance will be at least 1000 more than the minimum. The balance is an integer amount, no cents. Your goal is to draw down the account to whatever that minimum you were told was, but no further.

The ATM has only one function, and that’s to attempt withdrawals in the exact amount you enter on the screen, whole dollars only. You can’t check the balance, and you can’t deposit money back into it. You punch in an amount you want, and if the account has at least that much left in it, the ATM dispenses the money into your greedy hands and the hidden account balance is reduced by that amount. If the account doesn’t have enough, it will tell you so, and there’s no penalty for attempting to take too much except the ATM will beep at you annoyingly and the withdrawal fails. There’s no limit to how many times you try withdrawals, but at some point you have to declare yourself done and stop using the ATM.

If you end up drawing down the account to any other balance besides the minimum you were told, you’ve failed the test, and you shouldn’t have started withdrawing in the first place.

I know a solution for when the minimum=0 and the maximum is any whole number greater than 0. I’ll leave that as an exercise for the reader. Oh here, I’ll spoiler it for you:

Start with the largest even power of 2 less than or equal to the max, and attempt that withdrawal. Then divide your withdrawal amount by 2 again and again until your last attempt at 1, and after that you’ll have emptied the account. Or do it backwards. Or just withdraw 1 each time until you get told there’s no more money left, but that might take a while, though. I’m sure there are more solutions.

Is there a solution for some other exact minimum where it’s greater than 0? Is there a general solution for any minimum over zero? (Min <= X <= Max; Max-Min >= 1000)

If it helps any, I would particularly like a solution for minimum=10, max=100000, but any other numbers would be interesting.

2

So, the account has an undisclosed amount but up to $100000

And the challenge is “withdraw until there is exactly $10 left”

And there is no balance-checking available?
I certainly don’t see it, but I rarely see this kind of thing until I’m told. :slight_smile:

3

In other words, you’re told that the amount in the ATM might be as low as $10, and it might be as high as $100,000 , but you’re not told what the amount is. And you have to withdraw it down to exactly $10, or you lose. In that case, I don’t think there is a solution: Any attempted withdrawal greater than $100,000 is guaranteed to fail, so it won’t tell you anything. Any attempted withdrawal from $10 to $100,000 might just happen to be the exact amount in the machine, drawing it down to $0, and so you lose. And for any attempted withdrawal from $1 to $10, the machine might already have only $10 in it, and so you lose.

In other words, no matter what amount your first attempted withdrawal is, there’s always some chance that you’ll lose.

Now, there’s also a possibility of winning, and so there’s some strategy that maximizes your chances, but that’s a lot more complicated to find.

4

Unless I’m missing something, this problem is equivalent to “Guess a number between 10 and 100,000”.

I don’t see how that can be solvable.

5

I agree with Chronos. I see no solution when the minimum is greater than 0. When the minimum is 0, then essentially any strategy will work as long as your final try is $1 and you get a “Sorry can’t give it two you” response.

6

I wonder if, in context, that ability to improve the chances would prove significant or not - assuming that close doesn’t count…

I mean, doesn’t this question amount to “I’m thinking of a number, guess what it is” ?

7

I feel like there could be a solvable puzzle here, if I was given enough information to use my failures as indirect evidence of the current balance.

8

Thanks, Chronos, I suspected from the start it was something like what you laid out so clearly, but I couldn’t see it. I also had the thought that maybe, because there was such a nice clear binary solution for X=0 that somehow it could be adapted for a more general case, but you nailed it and the answer is no, it can’t, and you pretty much proved it in more formal terms.

And on preview, a lot more responses. Thanks, everybody. I’m satisfied there is no solution, and the only winning move is not to play. :slight_smile:

9

It is clear, to those who see such things clearly, that no strategy is certain to succeed.
But … Assuming all permitted starting balances are equally likely, you may seek to maximize your success chance.

If the minimum is $1 and the maximum is some even number, say $100; then attempt withdrawals of $99, $97, $95, etc., quitting after the first success. This will win whenever the starting balance was an even number. Equivalently, but slower, withdraw $2 each time (after an initial $1 initial withdrawal) until you’re refused.

If the minimum is $10 and the maximum is $100; attempt withdrawals of $90, $79, $68, $57, $46, $35, $24, $13, $2 and succeed 9 times out of 91. (Equivalently, but slower, withdraw $11 each time, after an initial $2 withdrawal.) Use a similar pattern when the maximum is $100,000; begin with $99,990, subtract $11 before each try; and succeed 9.0918% of the time. I think.

10

The maximum given is the maximum that might be in the account altogether, not the maximum one-time withdrawal.

11

We know that max >= 1000 x min which makes the problem impossible. Even if I know the max is $10,000 all I know is the min is less than or equal to $1000. So what if I knew what the max was. If I may be so bold to hijack the puzzle: figure out how much is in the account by making withdrawls in a way such that the account does not get below 0.1% of the original amount.

I don’t know if that is solvable or not

12

I don’t think it’s necessarily slower. For every high number where the large-withdrawal is faster, there’s a mirror for a low starting number where the small-withdrawal is faster.

The first says “Is the number $99? $97? $95?” and the second says “Is the starting number $2? $4? $6?”

Perhaps you’re saying the latter is slower because it requires a negative response to confirm the correct guess, versus a positive response doing the same but one withdrawal earlier?

13

No, OP specified that Max >= 1000 + Min.

14

Oops; let me attempt recovery. :slight_smile:
Refusal is quick, whereas it takes time to remove the banknotes in little batches. :stuck_out_tongue: (Not to mention the practical risk of “Machine is now out of $1 bills.” :cool: )

15

And now I’m wondering if the OP misunderstood some detail of the puzzle, because it’s so trivial as stated. Maybe there’s some other piece of information we’re supposed to have? Maybe you’re allowed to withdraw any amount, so long as you don’t go below the minimum, and if you win you gain whatever you’ve withdrawn, and are trying to maximize your expected value?

16

As stated, it wasn’t trivial to me, and it wasn’t trivial to any of the people I asked in person before turning to the Dope. No, my problem source was pretty emphatic on hitting that minimum exactly, no more, no less. I just didn’t see how it boiled down to “guess this number” in so many words.