6
$\begingroup$

I am reading The Man Who Loved Only Numbers, a biography of Paul Erdos, and I came across an example that I don't quite understand. The book asserts that you can rearrange the first $101$ integers in any order you like and you will always be able to find an increasing or decreasing sequence of eleven integers. What if I choose $1, 101, 2, 100, 3, 99, 4, 98....$ Will I ever find an increasing or decreasing sequence of eleven if I choose this arrangement? Possibly I am misunderstanding the assertion.

$\endgroup$
1
  • 5
    $\begingroup$ I suspect the claim refers to subsequences not necessarily consecutive subsequences. $\endgroup$ – hardmath Jan 1 '17 at 17:19
7
$\begingroup$

I will just pick

$$1,2,3,4,5,6,7,8,9,10,11$$

The book says that

"You don't have to pick the numbers consecutively," Graham said" You can jump. You might pick the first one, then the nineteenth one, then the twenty-second one, then the thirty-eighth one-but they all have to be going up or going down"

Ramsey theory, says Graham, makes a generalization of this result: to guarantee either a rising or falling sequence of length $n + 1$, you need $n^2 + 1$ numbers; with $ n^2$ numbers, you may not get it.

$\endgroup$
2
  • $\begingroup$ Ok, but the book states "no matter how perverse the arrangement, you'll always be able to find eleven integers that form an increasing or decreasing sequence." Haven't you only provided one specific example? I thought that the book was stating that ALL arrangements of the first 101 numbers will give an increasing or decreasing sequence of 11 integers. $\endgroup$ – MathGuy Jan 1 '17 at 18:54
  • 2
    $\begingroup$ What the book means is if you give me a derangement from $1$ to $101$, I can find an increasing subsequence of length $11$. In your case, you have given me $1,101,2,100, 3, 99, 4, 98,\ldots$, and I give you a subsequence of length $11$ that is increasing. If you give me anoher derangement, then there exists another subsequence of length $11$ that is monotone. $\endgroup$ – Siong Thye Goh Jan 1 '17 at 23:44
0
$\begingroup$

I was confused by this passage in the book too, and here's what I've learned:

The term 'sequence' does not necessarily imply that the numbers are consecutive.

This is the example set that Graham shows in the book:

91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 71, 72, 73, 74 ,75 ,76 ,77, 78, 79, 80, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 51, 52, 53 ,54, 55, 56, 57, 58, 59, 60, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

The reason this is such a good example is that, even by skipping over numbers, you can't find a sequence of increasing/decreasing numbers that is longer than ten, but there are lots of examples that are exactly ten. The most obvious example is any one of the rows:

41. 42. 43. 44. 45. 46. 47. 48. 49. 50

...but there are also sequences like this:

94, 84, 74, 64, 54, 44, 34, 24, 14, 4

Or:

100, 84, 77, 63, 54, 49, 31, 22, 15, 6

The point is, we can't find any sequence like this longer than 10. Now if we throw in 101 at the very beginning of this set, suddenly such a sequence is possible. In fact, you could put 101 in lots of places in this set and you would be able to form a sequence of 11. If it's at the very beginning of the set, we can move down a column like so:

101, 94, 84, 74, 64, 54, 44, 34, 24, 14, 4

and if it's in the middle, or near the end of the set, we can just slap it on the end of any one of the rows to get 11.

41. 42. 43. 44. 45. 46. 47. 48. 49. 50, 101

If you wanted to disprove Ramsey theory, the idea would be to find a way to arrange the numbers so that you can't find any ordered sequence of 11 digits. The example set we use here is not notable for making sequences easy to make, it's notable for making them as hard to make as possible. If you tried to arrange the order another way, like this for example:

1, 3, 2, 4, 5, 7, 6, 8...

... you wouldn't be making it harder to construct a long sequence, you would be making it easier. Remember, sequences can be non-consecutive and with this approach you would end up finding sequences much longer than 11 in length, and proving Ramsey right.

However, there are some places you could stick that 101st digit which would NOT result in an 11-digit streak. To guarantee that you could always find a sequence of 11 digits in order, you would need the numbers from 1 to 11^2, or 121 in total.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.