Catch An Atom If You Can!

With a rapid pace of advance in nanotechnology today, we may soon be able to manipulate atoms individually. Imagine we are looking for an impurity atom on the surface of a crystalline solid. The impurity atom is wandering randomly among a regular array of host atoms. We wish to capture this impurity atom by sending a probe atom onto the surface. For this year's Skadron prize, we ask you to create a FORTRAN subroutine that controls the motion of this probe atom so that it will capture the impurity atom as quickly as possible.

Overview

  1. The two-dimensional surface of the solid will be modeled by a two-dimensional lattice of discrete points whose coordinates are given by

    (n,m)

    where n and m are both integers. For example, (0, 0) , (1, 0) , (-1, 0) , (0,1) , and (0, -1) are all lattice points. Both the impurity atom and the probe atom are found at one of the lattice points.
  2. The host atoms are arranged on a regular array on the lattice and their x and y coordinates are both even integers. For example, host atoms are found at (0, 0) , (2, 0) , (0, 2) , (-2, 0) , (0, -2) , (2, 2) , (0, 4) , (2, 4) , (0, -4) , etc. The host atoms are fixed at their locations and do not move.
  3. Time runs in our model discretely so that we keep track of the positions of the impurity atom and the probe atom only at these discrete time steps designated by integers between 1 and N , where N is the total number of the time steps. For the contest, we will set N to be 2000.
  4. Initially, the impurity atom is found at lattice point (1, 1) . The impurity atom randomly jumps from one lattice point to another, but it cannot jump to a lattice point already occupied by a host atom. If the impurity atom is at lattice point (n, m) , then after a jump, it randomly chooses one of the following 4 lattice points as its next location: (n+10, m) , (n-10, m) , (n, m+10) , or (n, m-10) . We assume that the impurity atom is moving relatively fast so that after each jump, the impurity atom jumps over a distance of 10. For example, if the impurity atom is at (1, 1) , then after a jump it may be at (11, 1) , (-9, 1) , (1, 11) , or (1, -9) . If the impurity atom attempts to jump to a lattice point already occupied by a host atom, the impurity atom cannot move and stays at its current position. See also the figure below.
  5. Initially, the probe atom is found at lattice point (301, 300) . The probe atom jumps from one lattice point to another, but they cannot jump to a lattice point already occupied by a host atom. If the probe atom is at lattice point (n, m) , then after a jump, it may be found at one of the following 4 lattice points: (n+1, m) , (n-1, m) , (n, m+1) , or (n, m-1) . We assume that the probe atom is moving relatively slowly so that after each jump, the probe atom jumps over a distance of 1. For example, if the probe atom is at (2, 3) , then after a jump it may be at (3, 3) , (1, 3) , (2, 4) , or (2, 2) . If the probe atom attempts to jump to a lattice point already occupied by a host atom, the probe atom cannot move and stays at its current position. See also the figure below.
  6. The probe atom is considered to have captured the impurity atom when it comes right next to the impurity atom. More specifically, if the impurity atom is at lattice point (n, m) , the probe atom captures it when the probe atom arrives at (n+1, m) , (n-1, m) , (n, m+1) , or (n, m-1).

    Skadron Prize 03

The main program supplied by the department provides your subroutine with the current and the previous positions of the impurity atom as well as the previous position of the probe atom. Your subroutine then chooses a displacement vector of the probe atom for the next jump.

More Specifically

Write a FORTRAN subroutine move.f that must start with the following line:

subroutine move (impx, impy, impnx, impny, jprx, jpry, mx, my)

where

(impx, impy): the previous position of the impurity atom

(impnx, impny): the current position of the impurity atom

(jprx, jpry): the previous position of the probe atom

(mx, my): the displacement vector of the probe atom for the next jump.

Only the following 4 choices are allowed: (1, 0), (-1, 0), (0, 1), and (0, -1)

The Prize committee will run your subroutine move.f with the main program, which checks if the value for each displacement vector (mx, my) selected by your subroutine is valid. We will run the main program together with your subroutine for three times with three different sequences of pseudo-random numbers and will calculate an average for the total number of time steps required for capturing the impurity atom for each run. The first prize goes to the contestant whose subroutine produces the shortest average for the total number of time steps. Your program must complete its computation for each run within 2 minutes of CPU time on the departmental workstation entropy.

To test your subroutine move.f:

  1. Copy the main program skmain03.f available on entropy to your account:

    cp /u/hmb/skmain03.f skmain03.f

  2. Compile and run your subroutine with the main program:

    ncargf90 -O skmain03.f move.f
    a.out

    ncargf90 not only compiles the programs but also links the programs to NCAR graphics routines, which will allow the main program to plot the trajectories of both the impurity and the probe atoms.

    After typing in a.out, you will be prompted to type in either 0 or a positive integer larger than 100000. By typing in 0, you are letting the main program to use a default seed number for pseudo-random numbers that will be used for choosing random jumps for the impurity atom. If you type in a positive integer larger than 100000, then you are letting the main program to use the integer you have just typed in as the seed number for the pseudo random numbers. By using different seed numbers, you can create different trajectories for the impurity atom.
  3. To see the plot of the trajectories, type in:

    ctrans -d t4105 gmetactrans -d t4105 gmeta if you are using a Tektronix-capable terminal program (like BetterTelnet or TerraTerm ), or

    ctrans -d X11 gmeta

    if you are running X-Windows.

Example

In this figure we trace the impurity's path in white and the probe's path in red. The impurity atom starts at (1, 1) and wanders randomly. The probe starts at (301, 300) , gives chase for 1103 steps, and finally catches the impurity at (-69, 391) .

Sample

Prizes

$ 200 for the first place, $100 for the second place.

Who can participate

Physics majors at ISU.

How to Submit an Entry

Email your subroutine to Dr. Matsuoka.

Deadline

4 p.m. on Friday, April 25, 2003.