# Representing positions on a grid as a base-3 number

I have an assignment that presents some math I don't understand.

Consider the following grid.

       |       |
|       |
_ _ _ _|_ _ _ _|_ _ _ _
|       |
|       |
_ _ _ _|_ _ _ _|_ _ _ _
|       |
|       |
|       |


The tiles must be filled with the numbers 0, 1 or 2. They can be repeated. Since there are 9 tiles, then there are $3^9$ possible combinations, right? That I understand. What I don't understand is the following: every combination can be represented by an integer from 0 to 19682 (which is $3^9 - 1$).

I'm convinced that this is true, but I don't understand why. It has something to do with using numbers in base-3. But how are base-3 numbers related to the arrangement of the numbers 0, 1 and 2 on the grid? The example my assignment gives is like this:

2 0 0
0 1 2
1 0 1


This would be represented, the assignment says, like this:

$2*3^0 + 0*3^1 + 0*3^2 + 0*3^3 + 1*3^4 + 2*3^5 + 1*3^6 + 0*3^7 + 1*3^8$

I don't really understand what's going on there. Any help is appreciated. Thanks.

-

Imagine writing the digits out in a row instead of in a square: $200,012,101$, where I’ve inserted commas in the usual way to help demarcate the digits coming from each row. If this were a base ten number, it would represent

$$2\cdot10^8+0\cdot10^7+0\cdot10^6+0\cdot10^5+1\cdot10^4+2\cdot10^3+1\cdot10^2+0\cdot10^1+1\cdot10^0\;;$$

as a base three number it represents

$$2\cdot3^8+0\cdot3^7+0\cdot3^6+0\cdot3^5+1\cdot3^4+2\cdot3^3+1\cdot3^2+0\cdot3^1+1\cdot3^0\;.$$

Each of the $3^9$ possible ways of entering digits $0,1$, or $2$ into the square can be similarly strung out into a base three representation of a number, and the representations range from $000,000,000=0$ to $222,222,222=3^9-1$.

For some reason the assignment suggests reading the numbers out of the square in reverse order; that works just as well as what I did above, but it seems a little less natural.

-
Ok, I guess I understand what makes base-3 numbers so convenient. Correct me if I'm wrong. I could very well read the numbers on the grid as base-10 numbers. But then, there would be "jumps" as I count upwards. All the possible positions of the numbers would still make 19683 possibilities, but in base-10, I wouldn't be able to count sequentially from 0 to 222,222,222. I would have to "jump" all the numbers that have the digits 3-9. Base-3 is convenient because I can increment one by one and list all the combinations. Is that right? –  BeetleTheNeato Apr 4 '13 at 20:49
@BeetleTheNeato: That’s exactly right. –  Brian M. Scott Apr 4 '13 at 20:54

Each number from $0$ through $19682$ can be represented in base $3$ as a $9$ digit number if you pad on the left with zeros. You read those digits (here in reverse) and fill in the grid with them. Note that in your example the digits multiplying the powers of $3$ are exactly the numbers in the grid in order.

Similarly, if you could put any digit from $0$ through $9$ in the cells, there would be $10^9$ possibilities, which would correspond to the numbers $000,000,000$ through $999,999,999$

-

There is a 1-1 correspondence between {3x3 grids filled with numbers 0,1 and 2} and {9-tuples of numbers 0,1 and 2}. This correspondence is given by selecting an ordering of the cells in the grid and rearranging the numbers from the grid to conform a 9-tuple. Now, it is easy to interpret 9-tuples as 9-digit numbers in the way you described in your question.

-