discrete math (induuction)

Question

At time 0, a particle resides at the point 0 on the real line. Within 1 second, it divides into 2 particles that fly in opposite directions and stop at distance 1 from the original particle. Within the next second, each of these particles again divides into 2 particles flying in opposite directions and stopping at distance 1 from the point of division, and so on. Whenever particles meet they annihilate (leaving nothing behind). How many particles will there be at time 2^11 − 1? Justify your answer. Hint: Derive a formula for the number/ locations of particles at time 2^n − 1 for arbitrary positive integer n, prove the formula using induction, and apply it when n = 11.

Answer 1

So, to start we can look at what happens for the first couple steps. At time t = 0 we have 1 particle. At time t = 1 we have 2 particles a distance of 2 away from each other (-1 and 1). At time t = 2, two particles meet at point 0 which means they are annihilated so we are just left with 2 points a distance of 4 away from each other (-2 and 2). Then at time t = 3 we get 4 points a distance of two from each other (-3, -1, 1, 3). At time t = 4 the inner most particles all meet with each other so there are only 2 particles left, a distance of 8 away from each other (-4, 4). At time t = 5 we get particles at -5, -3, 3, and 5, then at time t = 6 we get particles at -6, -2, 2, 6, at t = 7 we get particles at -7, -5, -3, -1, 1, 3, 5, and 7. Do you see a pattern?

It may have been a little overkill to do it up to t = 7. but if we didn't the pattern could have been 2, 4, 6, 8, 10, 12..., instead now we know it tends to go 2, 4, 8, and we assume next would be 16. So, we have the inductive hypothesis at t = 2^n - 1 there are 2^n particles. So, we know there is a pattern such that the farthest particles are exactly t steps away from 0, since they are never annihilated, and they move away by 1 position every time step. And 2 particles that are a distance of 2 away by the next time step become 2 new particles that are a distance of 4 away, and if every 2 particles are a distance at least 4 away then the number of points doubles. Therefore, we can do the following:

Base Case: n = 0: t = 2^0 - 1 = 0, there is 2^0 = 1 particle at position 0.

Inductive Hypothesis: For n = N then the number of particles at the time t = 2^n - 1 is 2^n.

Inductive Step: For n = N + 1 show that at time t = 2^n - 1 there are 2^n particles:

2^(N + 1) - 1 = 2^N - 1 + 2^N which means it is 2^N time steps past 2^N - 1, but since our induction hypothesis there are 2^N particles at 2^N - 1 which are all spaced 2 apart since in order to fit 2^N particles on the same parity positions they must be located every 2 spaces to fit them all. Now that means that at step t = 2^N there is only 2 particles spaced each a distance of 2^N away from 0, which then after 2^N - 1 more time steps each particle turn into 2^N particles all a distance of 2 from each other with the outermost particles being a distance equivalent to the time t = 2^(N + 1) - 1 away from position 0. With that all being said there are 2 sets of 2^N points which gives us 2*2^N = 2^(N + 1) which proves the induction hypothesis.

With that conclusion we can plug in n = 11 to get 2^11 = 2048 particles.

Please consider booking a tutoring session if you need more help!