Robot Utopia

(Download PDF)

Human cities, especially newer ones are usually organized with orthogonal (right-angled) streets and avenues. Here is an example from Gaza:

robot-utopia1

Robot cities are similar to human cities except they are perfect Utopias… at least that’s how the Robots describe them. Robots do not worry about aesthetics, but just want their cities to be as efficient as possible.

In a Robot city, traveling one block takes a Robot exactly 1 second. Each intersection that a Robot moves through where the Robot has a choice of how to proceed also takes a second…
For example the trip below from the top left (1,5) to the right side (6,3) is 9 blocks long and goes through 4 intersections so it takes 13 seconds.

robot-utopia2

The trip from (2,2) to (5,6) is 7 blocks long and travels through 5 intersections so takes 12 seconds.

robot-utopia3

Robots are created in special Utopian cities like CREAT-6×6. This city (like the ones pictured above) are 6 by 6 as the name suggests. Each second a robot is created on a random intersection of CREAT-6×6 and then make their way to (1,1) to pick up their names, professions, and opinions.

Design roads for CREAT-6×6 so that a robot never takes longer than 10 seconds to reach (1,1).

Robots spend most of their lives in Utopian cities like GOOD-FOOD-6×6 delivering packets from one intersection to another.

Design roads for GOOD-FOOD-6×6 so that a robot never takes longer than 11 seconds to go from one destination to another.

Extensions:

  • Design roads for CREAT-7×7 so that a robot never takes longer than 12 seconds to reach (1,1).
  • Design roads for GOOD-FOOD-7×7 so that a robot never takes longer than 13 seconds to go from one destination to another.
  • Is it always possible to design a road for CREAT-NxN that never takes more than 2N-2 seconds?
  • Is it always possible to design a road for GOOD-FOOD-NxN that never takes more than 2N-1 seconds?
  • In HOSP-6×6 Robots go to get fixed. Assume a Robot will always enter at (1,1), visit a random location,* and then leave at (6,6).
    • Find a Robot Utopian design so that the robot never takes longer than 14 seconds.
    • Find a Robot Utopian design so that the average time is not more than 13 seconds.
    • *The random locations include (1,1) and (6,6).
  • Not all Robot cities are squares. Like the name suggests, TRIANGLE-CREAT-9×9, is a triangularly shaped Robot Utopia where new robots are created. Is it possible to design a road system so that no matter which intersection a Robot is created on, it can always get to (1,1) in 10 seconds? The road system below fails because there are two intersections on the lower road that takes longer than 10 seconds.

robot-utopia4

  • Can you design a better road system? Is it possible to design a road system for TRIANGLE-CREAT-8×8 so that no matter which intersection a Robot is created on, it can always get to (1,1) in 9 seconds?

Game:

  • Each player designs a Robot Utopia on a 6 by 6 grid.
  • One person rolls a red and blue dice to determine the starting position of a robot. Everyone places a robot marker at this spot.
  • Roll the red and blue dice to find the first destination.
  • Keep a record of how long it takes for each person’s robot to reach the destination in their Robot Utopia. Roll the dice again to find your robot’s next destination… do this 10 times. The person with the fastest total time is the winner.

Game Extension:

  • Use two red and two blue dice and add them. Otherwise play the game the same as above on the following grid:

robot-utopia5

The Math in This Problem:

In this brainteaser, students will analyze and create various-sized grids. Since traveling from block to block takes one second and crossing an intersection takes an extra second, students are challenged to build efficient grids that only take a maximum of a specified number of seconds.

(Download PDF)