CAPTURING OSAMA BIN LADEN

This mathtivity shows how to use (under certain not unreasonable assumptions) BINARY SEARCH to find the cave where Osama Bin Laden is hiding. Assumptions:

  • A signal associated with Bin Laden's communicating device has been detected in a long row of caves in Afganistan.

  • The row of caves is known to be 1024 in number.

  • Each cave has one or more "rooms", at most 32.

  • It is possible to detect (by increase or attenuation) whether you are moving toward, or away from, the origin of the signal, providing "Yes" or "No" (binary) answers to the query, "Is the source in this direction?"

    Please note that 1024 = 210. Then BINARY SEARCH FINDS THE ORIGIN CAVE IN 10 STEPS.

    And the "origin room"? Please note that 32 = 25. Then BINARY SEARCH FINDS THE ORIGIN ROOM IN 5 STEPS.

    Total Search Procedure: At most, 10 + 5 = 15 STEPS.

    To illustrate, suppose the Search has been completed. The ORIGINATING EQUIPMENT, along with Osam Bin Laden has been found in Cave 849, Room 23. How could that be determined by BINARY SEARCH?
    1. Put the detecting equipment in the region just beyond the 512th cave (halfway along the row of 1024). Moving the sensor FORWARD results in an INCREASE of signal. So, the "origin cave" is in the range 513-1024 Þ 512 caves.

    2. Half of that range-number is 256, so that the "halfway point" of this range is 512 + 256 = 768 caves. Placing the sensor just beyond this point and moving it FORWARD again results in SIGNAL INCREASE. So, the "origin cave" is in the range 769-1024 Þ 256 caves.

    3. Half of that range-number is 128, so the "halfway point" of this range is 768 + 128 = 896. Placing the sensor just beyond this point and moving it FORWARDS now results in ATTENTUATION. So, the "origin cave" is in the range 769-896 Þ 128 caves.

    4. Half of that range-humber is 64, so the "halfway point" of this range is 768 + 64 = 832 caves. Placing the sensor just beyond this point and moving it FORWARDS now results in SIGNAL INCREASE. So, the "origin cave" is in the range 833-896 Þ 64 caves.

    5. Half of that range-humber is 32, so the "halfway point" of this range is 832 + 32 = 864. Placing the sensor just beyond this point and moving it FORWARDS now results in SIGNAL ATTENUATION. So, the "origin cave" is in the range 833-864 Þ 32 caves.

    6. Half of that range-humber is 16, so the "halfway point" of this range is 832 + 16 = 848. Placing the sensor just beyond this point and moving it FORWARDS now results in SIGNAL INCREASE. So, the "origin cave" is in the range 849-864 Þ 16 caves.

    7. Half of that range-humber is 8, so the "halfway point" of this range is 848 + 8 = 856. Placing the sensor just beyond this point and moving it FORWARDS now results in SIGNAL ATTENUATION. So, the "origin cave" is in the range 849-856 Þ 8 caves.

    8. Half of that range-humber is 4, so the "halfway point" of this range is 848 + 4 = 852. Placing the sensor just beyond this point and moving it FORWARDS now results in SIGNAL ATTENUATION. So, the "origin cave" is in the range 849-852 Þ 4 caves.

    9. Half of that range-humber is 2, so the "halfway point" of this range is 848 + 2 = 850. Placing the sensor just beyond this point and moving it FORWARDS now results in SIGNAL ATTENUATION.

    10. Placing the sensor at point between caves 848, 849, it is confirmed that the "origin cave" is the 849th cave.
    Let's say, this cave has 32 "rooms". We need to find the "origin room" of this 849th cave.

    1. Taking the range 1-32, the "halfway point" is between "rooms" 16, 17. Placing the sensor at this point and moving FORWARD results in a SIGNAL INCREASE. So the "origin room" is in the range 17-32 Þ 16 "rooms".

    2. Half of this range is 8, so the "halfway point" is 16 + 8 = 24. Placing the sensor at this point and moving FORWARD results in ATTENUATION. So the "origin room" is in the range 17-24 Þ 8 "rooms".

    3. Half of this range is 4, so the "halfway point" is 16 + 4 = 20. Placing the sensor at this point and moving FORWARD results in SIGNAL INCREASE. So the "origin room" is in the range 21-24 Þ 4 "rooms".

    4. Half of this range is 2, so the "halfway point" is 22. Placing the sensor at this point and moving FORWARD results in SIGNAL INCREASE. So the "origin room" is in the range 23-24 Þ 2 "rooms".

    5. Half of this range is 1, so the "halfway point" is 23. Placing the sensor at this point and moving FORWARD results in ATTENUATION. So, the "origin room" is the 23rd in the 849th cave.
      So, Osama Bin Laden has been found in 15 STEPS.

      ASSIGNMENT: Suppose that the ORIGIN CAVE was 314, and its ROOM 19. Can you show how to discover this?

      This has been adapted from a "search for a word in a large dictionary", which I've conducted with elementary school children.