What is the analytical solution to a particle decay problem on a line?

[loom91]

This problem, set in the famous IIS entrance exam a few years back, has in the past few days defeated some execellent brains, including those of teachers and math wizes. The problem is simple in its statement:-

A particle is situated at the origin of a line. After a second, this particle decays into two particles of the same kind, one moving 1 unit to the right while the other moves 1 unit to the left. After another second, these two particles similarly decay. When two particles collide at a point, they annihilate each other. What number of particles will be left after 2^11 + 1 seconds of this?

Intuition suggests an answer of 4, and this can probably be checked by brute force using a computer model, though the model itself would be rather complicated. The question is how would one derive an analytical solution? Thanks, and I hope you enjoy this problem.

Molu

 

[CRGreathouse]

Work mod 2?

 

[0rthodontist]

A diagram helps for thinking about it:

                 o 0
                o o 1
               o   o 2
              o o o o 3
             o       o 4
            o o     o o 5
           o   o   o   o 6
          o o o o o o o o 7
         o               o 8
        o o             o o 9
       o   o           o   o 10
      o o o o         o o o o 11
     o       o       o       o 12
    o o     o o     o o     o o 13
   o   o   o   o   o   o   o   o 14
  o o o o o o o o o o o o o o o o 15

Now you have to show that the triangles repeat. That is, you show that if you have a triangle, distinguished by a bottom row of o's alternating with spaces, like

 T

for the rows from time 0 up until time 2^k-1, then the rows from time 0 up until time 2^(k+1)-1 follow

 T
T T

From this you can determine that the bottom row is all o's alternating with spaces at any time 2^k - 1, and then you can get your conclusion.

 

[loom91]

A diagram helps for thinking about it:

                 o 0
                o o 1
               o   o 2
              o o o o 3
             o       o 4
            o o     o o 5
           o   o   o   o 6
          o o o o o o o o 7
         o               o 8
        o o             o o 9
       o   o           o   o 10
      o o o o         o o o o 11
     o       o       o       o 12
    o o     o o     o o     o o 13
   o   o   o   o   o   o   o   o 14
  o o o o o o o o o o o o o o o o 15

That's an amazing diagram, but I'm afraid I can't understand what you said next. Are you suggesting induction? Thanks.

Molu

 

[0rthodontist]

The diagram is just tracking what happens to the particles over 15 seconds.

Yes, I am suggesting induction. Sometimes the top of the diagram is a triangle with a base made entirely of o's separated by spaces. In what I've shown, such triangles are rows 0, 0-1, 0-3, 0-7, and 0-15. Note that, for example, rows 0-15 consist of three of the triangles of rows 0-7, one above the other two. Do you know why? And these three triangles form a larger triangle that has a bottom row of o's separated by spaces. What will row 16 look like? Generalize this argument using induction.

 

[loom91]

The diagram shows what I had suspected: the state of the system repeats symmetrically over time with only a scaling-up in each sucessive cycle. It displays characteristics somewhat analogous to the self-similarity of fractals. But I can't think how I can use this symmetry model to make predictions. It's too complex and my skills inadequate. I've already spent a lot of time on it, I'll hand over your hints to my mathie friend and see how he fares.

 

[Robokapp]

2049 breaks...

(2^n)-1 is where we have a full line of particles...
maybe this has been stated already I'm trying my own thing.

2^n we have a always 2 particles...so step [2048] [/color]would have 2 particles.

2 particles at opposite sides of spectrum...so they would each break in two...no collisions will exist...so there will turn into 4 particles.

i got 4 as the answer. I didn't prove that (2^n)-1 is a full line I just took it as granted form the picture...so I can't take credit for this but...I think the rest is correct.

 

[loom91]

My friend managed to solve it independently using induction. Apparently, his inductive hypothesis was that after 2^k seconds we have two particles each 2^k units from the origin. Now he considered one of these two particles separately. After another 2^k seconds (making a total of 2^(k+1) seconds), we would end up with one particle at the origin and the other at a distance 2^k + 2^k = 2^(k+1) units from the origin by hypothesis. The same agument can be repeated for the other one of the original particles. The two at the origin will annihilate, therefore proving the proposition for k+1. It is trivial to show for 2^1, so by the principle of mathematical induction the result is proved for all n, including 11.

The problem's solved, but I'm still in love with the rich geometry of the structure.