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.