Sunday, May 12, 2013

사다리 타기 (Sadari Tagi)

Today I learned about  Sadari Tagi (사다리 타기) a Korean way of drawing straws. It is a way to randomly assign N number of people to N number of tasks.

Process

First, a number of vertical lines are drawn, with numbers from 1 to N at the top and the tasks to be completed at the bottom (in random order). The numbers at the top correspond to each person. After that, a random number of staggered lines are drawn which interconnect each column.

For the picking process, a number is randomly picked. The idea is to follow down the line in the column. When an interconnecting line is first reached, cross over to the next column. After that, continue downward until another interconnecting line is reached. This is done until the task is reached at the end.

The following is an example. 3 people are supposed to complete 3 tasks. The mapping between person and task is random. The diagram is as follows (I made it horizontal instead of vertical):

1 ------------------------------------------ Task 1
              |           |       |
2 ------------------------------------------ Task 2
       |             |
3 ------------------------------------------ Task 3

So there are 3 interconnecting lines between 1 and 2, while there are only 2 interconnecting lines between 2 and 3. The number of interconnecting lines is irrelevant provided that they are staggered.

Here is an example, suppose 3 individuals (Jay, Sam and Bob) are required to perform three odious tasks. Which individual performs which task? If we use the Sadari Tagi (사다리 타기), we would construct the following diagram:

Jay ------------------------------------------ Task 1
              |           |       |
Sam ------------------------------------------ Task 2
       |             |
Bob ------------------------------------------ Task 3

To find out which task Jay is to do, start from Jay and move down until we hit the first intersection. Keep going down until we hit the second intersection. Keep going down until we reach Task #3.

Jay ------------------------------------------ Task 1
              |           |       |
Sam ------------------------------------------ Task 2
       |             |
Bob ------------------------------------------ Task 3

Using the same process, you will see that Sam is assigned to odious Task #2, and Bob is assigned to odious Task #1. (Apologies for the ASCII art!)

Question

My question is how do we know that there will always be a one-to-one mapping between number and task? So, could it be that, depending on the interconnected lines drawn, could it be that Sam and Bob be assigned to the same task? After constructing several such diagrams, I found out that the answer is no.

But how? The answer, in my mind, is quite simply. Suppose the entire diagram is broken into sections, where each section contains only one interconnecting line. For example, the diagram above is broken into 5 sections:

      #1  I  #2  I  #3  I #4 I  #5         
1 --------I------I------I----I-------------- Task 1
          I   |  I      I |  I    |        
2 --------I------I------I----I-------------- Task 2
       |  I      I   |  I    I               
3 --------I------I------I----I-------------- Task 3
          I      I      I    I               

For each section, if the process as described above is followed, there is always a one-to-one-mapping between the N numbers and each task. It does not matter how many sections there are, there always be a one-to-one mapping between N numbers and the task.

It would probably be easier just to draw straws (or randomly pick numbers from a hat) -- however the picking process of going through Sadari Tagi seems a lot more fun and exciting!