Solve one - get one free.

I. Crazy bank

I have not a penny in my pocket and the only money available to me is $500, deposited in a crazy bank with some very strange rules:

a. There is no interest on money deposited.
b. There are no charges for withdrawal, but one can only draw exactly $300,- no overdraft and no other amounts allowed.
c. There is only one specific amount of money one can deposit - $198 to be exact, happily enough no charges for this .

Using only those operations, what is the biggest amount I can rescue from this bank?

II. Shift a token.

On a ruler, marked from 0 to 147 cm, a token is placed on one of the marked places.
You can move this token any time:
either 100cm to the right or 47 cm to the left.
Prove that after 147 permissible moves the token is at its starting point.


If I were you I would start with the token story first.

I. Crazy Bank.

The greatest common divisor of 300 and 198 is 6, so only multiples of 6 can be rescued. The Euclidean algorithm with a side accounting allows us to see how this can be accomplished:

300 =   1 * 300  +  0 * 198   
198 =   0 * 300  +  1 * 198
102 =   1 * 300  -  1 * 198  Each row is the second preceding row minus
 96 =  -1 * 300  +  2 * 198  the applicable quotient times the first preceding row,
  6 =   2 * 300  -  3 * 198  and therefore represents the remainder.
  0 = -33 * 300  + 50 * 198

The $500 on deposit is 2 more than a multiple of 6, so $498 can be rescued. In fact 498 is 83 * 6, and from the above we see that that is 83 * (2*300 - 3*198), so 83*2 = 166 withdrawals combined with 83*3 = 249 deposits would result in the required net retrieval. However, this is not the minimum, as we see that 33 withdrawals exactly balance 50 deposits, so we can subtract four times each of these without going into negative territory: 166 - 33*4 = 34 withdrawals, and 249 - 50*4 = 49 deposits will also do the trick, leaving $2 in the account, having rescued $498. The order of deposits and withdrawals doesn't matter, so whenever there's over $300 in the account, withdraw that amount; otherwise you have at least $200 in your hand and can therefore make a $198 deposit.

The 34+49=83 transactions look like this:

Tran Dep Draw Bal        Tran Dep Draw Bal
   1     300  200          43     300   50
   2 128      398          44 128      248
   3     300   98          45 128      446
   4 128      296          46     300  146
   5 128      494          47 128      344
   6     300  194          48     300   44
   7 128      392          49 128      242
   8     300   92          50 128      440
   9 128      290          51     300  140
  10 128      488          52 128      338
  11     300  188          53     300   38
  12 128      386          54 128      236
  13     300   86          55 128      434
  14 128      284          56     300  134
  15 128      482          57 128      332
  16     300  182          58     300   32
  17 128      380          59 128      230
  18     300   80          60 128      428
  19 128      278          61     300  128
  20 128      476          62 128      326
  21     300  176          63     300   26
  22 128      374          64 128      224
  23     300   74          65 128      422
  24 128      272          66     300  122
  25 128      470          67 128      320
  26     300  170          68     300   20
  27 128      368          69 128      218
  28     300   68          70 128      416
  29 128      266          71     300  116
  30 128      464          72 128      314
  31     300  164          73     300   14
  32 128      362          74 128      212
  33     300   62          75 128      410
  34 128      260          76     300  110
  35 128      458          77 128      308
  36     300  158          78     300    8
  37 128      356          79 128      206
  38     300   56          80 128      404
  39 128      254          81     300  104
  40 128      452          82 128      302
  41     300  152          83     300    2
  42 128      350

II. Shift a Token.

Adding 100 and subtracting 47 are congruent mod 147, so we need consider only adding 100 mod 147. After 147 moves, all possible positions will have been gone through, in fact only once each, since 147 and 47 (or 100) are relatively prime. The only exception is that if you start on 0 you might end up at 147 and vice versa, since these are equivalent positions mod 147, as in:

147  100  53  6  106  59  12  112  65  18  118  71  24  124  77  30  130  83
36  136  89  42  142  95  48  1  101  54  7  107  60  13  113  66  19  119  72
25  125  78  31  131  84  37  137  90  43  143  96  49  2  102  55  8  108  61
14  114  67  20  120  73  26  126  79  32  132  85  38  138  91  44  144  97
50  3  103  56  9  109  62  15  115  68  21  121  74  27  127  80  33  133  86
39  139  92  45  145  98  51  4  104  57  10  110  63  16  116  69  22  122
75  28  128  81  34  134  87  40  140  93  46  146  99  52  5  105  58  11
111  64  17  117  70  23  123  76  29  129  82  35  135  88  41  141  94  47
0

In fact, this sequence repeated infinitely, lists the possible moves at any given point, given that 0 and 147 are considered interchangeable, and constitutes another proof of the proposition presented.  The other numbers are not interchangeable, and so repeat each 147 moves.

Posted by Charlie on 2011-02-02 14:40:24