Encoding a line-up as a sequence of numbers

0:00Seven children, standing in a line. And each one of them says a number out loud. Left to right: zero, one, zero, two, two, two, one. Nobody has told you what the numbers mean yet, and that is deliberate. Now the same seven children line up again, in a different order. This time: zero, zero, one, two, two, five, six. Same children. Same heights. Nothing about them has changed at all.

0:30But run along the two rows and compare them. Four of the seven numbers have changed. So whatever those numbers describe, it is not the children. It is the arrangement. Have a look at the two rows before I tell you. What could each of those children possibly be counting? Here is a clue. In both rows, the child at the front says zero. Here is another. In the second row, the numbers get big at the back.

1:01Five, then six. And six is as big as a number can get with seven people. One more clue. In the first row, a child standing in the middle also says zero. So it is not simply position. Standing third does not force you to say two. Whatever the rule is, it involves the people ahead of you, and something about you. And with the heights drawn on the wall behind them, there is really only one candidate.

1:32Here it is. Look at everybody standing ahead of you in the line. Count how many of them are taller than you are. Say that number. That is the whole rule. There is nothing else to it, and no part of it is hidden. You do not measure anybody. You do not need a single centimetre. You look forward, and you count the heads above your own. Which means every number in the row is a count of comparisons and nothing more.

2:02That will turn out to matter far more than it sounds like it should. So let us check it against the first row, child by child. Front of the line. Nobody ahead at all, so nothing to count. Zero. Second. One person ahead, and that person is taller. So, one. Third. Two people ahead, and this child is taller than both of them. Zero. In fact this child is the tallest of all seven, and they are standing third.

2:34Fourth. Three people ahead, two of them taller. Two. Fifth, and sixth. Two each. Both have exactly two taller children in front of them. And the one at the back, seventh in the line, has a single taller child ahead. One. Zero, one, zero, two, two, two, one. Which is the row we started with. Now the second row, and remember, these are the same seven children. This time the two shortest of them have ended up right at the back.

3:08Watch what that does. The child at the very back is the shortest of all seven. Everybody is ahead of them, and every single one is taller. Six. The one just in front is the second shortest. Five taller people ahead. Five. Those same two children said one and two when they stood in the other order. Same child, same height, and a completely different number, purely because they moved.

3:37So the biggest number does not belong to the shortest child. Only sometimes it does. Your turn now. Here is a third row of the same seven children, with all the balloons empty. Stop the video if you want to try it. Front of the line: zero. Second. This child is taller than the one ahead of them, so zero again. Third. One taller person ahead. One. Fourth. Taller than all three of the people ahead. Zero.

4:10Fifth. Three taller people ahead. Three. Sixth. Taller than everyone ahead of them. A zero, from a child standing sixth. And seventh, three. So: zero, zero, one, zero, three, zero, three. Two things about all this are worth stopping on. The first is that the front of the line always says zero. Every row, always. Not because they are tall. Because there is nobody ahead of them to count. The count runs over an empty group, and an empty group has nothing in it.

4:47Which kills a very tempting mistake straight away, and it is worth killing carefully. Saying zero does not mean you are the tallest. The tallest child does always say zero, because nobody ahead of them can be taller. But it runs one way only. Tallest gives you zero. Zero does not give you tallest. The second thing is about how big a number can possibly get. The child standing first has nobody ahead. Their largest possible number is zero.

5:22The second has one person ahead, so at most one. The third, at most two. The fourth, at most three. Position by position the ceiling climbs. Zero, one, two, three, four, five, six. You can never announce more people than are actually standing in front of you. So with eight children in the line, the largest number anybody can say is seven. And that ceiling is the whole law here. Obey it and you are possible. Break it and you are not.

5:56Which lets us answer a question that looks much harder than it is. Given a list of seven numbers, could any arrangement of children produce it? Try this one. A single one at the front, and then six zeros behind it. The very first entry kills it. The first child has nobody to count. So no arrangement gives that. Ever. It is not rare, it is impossible. Now try seven zeros. That one is fine, and look what it forces.

6:29Every child taller than everyone ahead means the row climbs, front to back. And zero, one, two, three, four, five, six forces exactly the reverse. Tallest at the front. Now the part of this I find genuinely surprising. The numbers threw away every height. So how much did we lose? Nothing at all. The row can be rebuilt from the numbers alone. Take zero, zero, one, two, two, five, six, and build it up from the front.

7:03First child. Alone at the front so far, so there is nothing at all to decide. Second says zero, so nobody already standing is taller. They go above. Third says one, so exactly one of the two already there is taller. That pins them. And so on. Every child slots in with no choice left at any step. The row comes back. So let us sort some claims about all this, into always, sometimes, and never.

7:36The tallest child says zero. Always, because nobody ahead of them can be taller. A child who says zero is the tallest. Only sometimes, and we have seen exactly why. The biggest number belongs to the shortest child. Only sometimes. Move that same short child to the front and they say zero instead. The last child says the biggest number. Only sometimes, again. Nobody says more than six. Always, with seven in the line. That is the ceiling.

8:11And notice that one counterexample settles a sometimes. One is all it takes. So what was all of that actually for? Seven numbers, and they contain no heights at all. No centimetres. No tallest in the class. Nothing you could measure with anything. They keep only comparisons. Who is taller than whom, and not one thing besides. And that turns out to be everything you needed, with nothing at all to spare.

8:43Count them if you like. There are five thousand and forty ways to line seven children up. And exactly five thousand and forty lists that obey the ceiling. One each, none left over. So the row and its seven numbers are the same information, wearing different clothes.