Math Is Fun Forum

Chriskay

Guest

Pigeonhole - Subsequence

Let m and n be positive integers. Exhibit an arrangement of the integers from 1 to mn which has no increasing subsequence of length m+1, and no decreasing subsequece of length n+1.

I have no idea what to do with this!

Bob

Administrator

Registered: 2010-06-20

Posts: 10,649

Re: Pigeonhole - Subsequence

hi Chriskay

Welcome to the forum!

I offer this example which I think meets the criteria.

Suppose m = 5 and n = 3.

arrangement = { (1,2,3,4) , (7,6,5) , (8,9,10,11) , (14,13,12) , (15,16,17,18) , (21,20,19) ,  .........}

The brackets are there purely to demonstrate increasing and decreasing sequences.

The increasing ones in the odd alternate brackets are all of length 'm-1'.  But the next digit means the true increasing length is 'm'.

Then there is a break as the next number is lower.

The even alternate brackets are all of length 'n'.  Then there is another break as the next number is higher.

Thus the increasing sequences are all length 'm' and the decreasing ones all length n.

As this can carry on indefinitely there's no problem stopping at mn.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: Pigeonhole - Subsequence

Hi Chriskay and Bob

I considered the case where sub-sequence means that we can take any elements,even ones that are not next to each other,but just keep them in order.E.g.:

For 1,2,3,4,5 I considered 1,3,4,5 to be a sub-sequence as well.A solution exists then as well:

We have the sequence:

1,2,3,...,mn

We divide it into group of m numbers:

(1,2,3,...,m),(m+1,m+2,...,2m),...(m(n-1)+1,m(n-1)+2,...,mn)

And when I reverse the order of these groups I get exactly the sequence needed.

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,649

Re: Pigeonhole - Subsequence

hi Stefy,

if I've understood you correctly you'll have

(1,2,3,...,m),(2m .....

That makes m + 1 numbers in an increasing sequence.

So you might want to 'lop' off the last number in each bracket ????

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: Pigeonhole - Subsequence

Hi Bob

Stay online. I will explain it in my next post!

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: Pigeonhole - Subsequence

My sequence is:

(m(n-1)+1,m(n-1)+2,...,mn),...,(m+1,m+2,...,2m),(1,2,...m)

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,649

Re: Pigeonhole - Subsequence

Oh, I see.  I didn't read your explanation properly.  And there's me thinking I am good at English.

I bow to your superior use of the English language and I will do my corrections ten times as a punishment!

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: Pigeonhole - Subsequence

Your English is perfectly good. And much better than mine. May have something to do with you being from England.

Hey,did Mrs S go with you today To Mrs B?

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.