Python Example in Discrete Math

Here's a little problem that's easy to solve exactly once you know the trick, but which is also instructive to look at with a simple Python program:

Someone gives you something that's (at least conceptually) infinitely divisible, like a liquid or fine powder. Then, you give half of it back to them. Then, they give half of what you gave them back to you. Then, you give them half of that... and so on forever. Assuming you could do this exchange for ever, how much accumulated 'stuff' would you have at the end?

This problem can be solved exactly, and the answer is 2/3 of the original amount --not, as you might initially guess, 1/2. The solution is fairly easy if you do it using binary fractional notation:

1. The infinite sum is: 1 - 1/2 + 1/4 - 1/8 + 1/16 - 1/32 + ...
   
   
2. Group pairs of terms and reduce: (1 - 1/2) + (1/4 - 1/8) + (1/16 - 1/32) + ... = 1/2 + 1/8 + 1/32 + ...
   
   
3. In binary notation, this is: x = b0.10101010...
   
   
4. 2x = b1.01010101... (Multiplication by 2 shifts one place to the left)
   
   
5. 3x = 2x + x = b1.11111111... = 2. To see this:
   
   
   1. Let y = b1.11111111...
      
      
   2. 2y = b11.11111111...
      
      
   3. y = 2y - y = b10.00000000.... = 2.
   
   
6. x = 2 / 3.

Here's a simple Python program that lets you play with this problem. It takes 2 arguments on the command line: (1) the initial amount of 'stuff', and (2) the number of iterations (exchanges) to perform. It prints out the amount of 'stuff' you have, your friend has, and the amount exchanged at each iteration, and then makes a simple WxPython plot of the amounts over time:

> discrete.py 10 35
i     A               B               C
----- --------------- --------------- ---------------
0     0.00000000      10.00000000    
1     10.00000000     0.00000000      10.00000000    
2     5.00000000      5.00000000      5.00000000     
3     7.50000000      2.50000000      2.50000000     
4     6.25000000      3.75000000      1.25000000     
5     6.87500000      3.12500000      0.62500000     
6     6.56250000      3.43750000      0.31250000     
7     6.71875000      3.28125000      0.15625000     
8     6.64062500      3.35937500      0.07812500     
9     6.67968750      3.32031250      0.03906250     
10    6.66015625      3.33984375      0.01953125     
11    6.66992188      3.33007812      0.00976562     
12    6.66503906      3.33496094      0.00488281     
13    6.66748047      3.33251953      0.00244141     
14    6.66625977      3.33374023      0.00122070     
15    6.66687012      3.33312988      0.00061035     
16    6.66656494      3.33343506      0.00030518     
17    6.66671753      3.33328247      0.00015259     
18    6.66664124      3.33335876      0.00007629     
19    6.66667938      3.33332062      0.00003815     
20    6.66666031      3.33333969      0.00001907     
21    6.66666985      3.33333015      0.00000954     
22    6.66666508      3.33333492      0.00000477     
23    6.66666746      3.33333254      0.00000238     
24    6.66666627      3.33333373      0.00000119     
25    6.66666687      3.33333313      0.00000060     
26    6.66666657      3.33333343      0.00000030     
27    6.66666672      3.33333328      0.00000015     
28    6.66666664      3.33333336      0.00000007     
29    6.66666668      3.33333332      0.00000004     
30    6.66666666      3.33333334      0.00000002     
31    6.66666667      3.33333333      0.00000001     
32    6.66666667      3.33333333      0.00000000     
33    6.66666667      3.33333333      0.00000000     
34    6.66666667      3.33333333      0.00000000     
35    6.66666667      3.33333333      0.00000000     

As you can see, the amounts quickly converge on 2/3 and 1/3 of the original. To get a plot, you will also need plots.py, NumPy, and WxPython installed on your system. If you don't have NumPy or WxPython, you can uncomment the program exit before the graphics are used.

Exercise for the reader: Modify the attached program to accept another command line value which allows you to set the exchange percentage at a value different from 50%. See what effect different percentages have on the final distribution.