HomeAbout Our ProjectContact UsSite Web Map
Mathematics ProjectsSupport for StudentsSupport for TeachersSupport for MentorsSupport for ParentsHard Math Cafe

Project Description Prerequisites Warm up Problems Hints Resources Teaching Notes Extension Problems Results

Extensions for the Amida-kuji Problem

Efficiency: "Worst Case" Assignment

For an amida-kuji with a certain number of players, what is the maximum number of horizontal lines you would ever need to create an ordering?  If you think of horizontal lines as having a cost, that number is considered the "worst case" number.  What is the worst case for 2 players?; for 3 players?; for n players?

Sorting Networks

If each horizontal line is thought of as a "sorting element" that is activated only when the number on the left is greater than the number on the right, then a "network lottery" turns into a "sorting network."   Computer scientists have done quite a bit of research on sorting networks.  However, most networks normally allow comparisons between nonadjacent lines, as in the figure below.  It is the most efficient network that is know  for sorting 13 items.  The sorting networks we get from amida-kuji are planar sorting networks, because the networks can be drawn on the plane without any lines crossing.

an efficient non-planar sorting network for 13 items

For non-planar sorting networks, see http://unplugged.canterbury.ac.nz/sortnet/index.htm

Back to Top

Translations of mathematical formulas for web display were created by tex4ht.

© Copyright 2003 Education Development Center, Inc. (EDC)

EDC Logo