Pigeonhole Principle/Combinatorics

[thecat]

Let x be a real number and let n be a positive integer. Show that between the numbers x, 2x, 3x, ..., (n-1)x there is a distance to some integer is at most 1/n.

The only part I'm confused about is that if the fractional part of the number is between (n-1)/n and 1 then the statement is true. Somebody help me, please. Thank you in advance

 

[Dr.Peterson]

I'm not sure of the wording of the problem. Is that exactly what you were given? The grammar of "there is a distance to some integer is at most 1/n" escapes me.

It sounds like you are saying you have proved most of it, but your proof doesn't work when the fractional part of x is greater than (n-1)/n. Is that what you are saying? Please show the proof as you have it so far, so we can see what is lacking.

 

[lev888]

This seems equivalent to:
For positive n consider a segment of length (n-2)/n. Prove that no matter how it's placed in [0,1], one of its ends is within 1/n from 0 or 1.

 

[pka]

This seems equivalent to:
For positive n consider a segment of length (n-2)/n. Prove that no matter how it's placed in [0,1], one of its ends is within 1/n from 0 or 1.

That may well be the meaning. However, it certainly not what was posted. As Prof. Peterson wrote, The grammar of "there is a distance to some integer is at most 1/n" escapes me.

 

[lev888]

That may well be the meaning. However, it certainly not what was posted. As Prof. Peterson wrote, The grammar of "there is a distance to some integer is at most 1/n" escapes me.

I think it should be "there is a distance to some integer that is at most 1/n"

 

[thecat]

I'm not sure of the wording of the problem. Is that exactly what you were given? The grammar of "there is a distance to some integer is at most 1/n" escapes me.

It sounds like you are saying you have proved most of it, but your proof doesn't work when the fractional part of x is greater than (n-1)/n. Is that what you are saying? Please show the proof as you have it so far, so we can see what is lacking.

"Let x be any real number. Can it be proven that among the numbers x,2x,…,(n−1)x, there is one element that differs from an integer by at most 1/n?" This is the exact question.

By Pigeonhole, being n boxes,
we put in box 1 all the real \(\displaystyle "y"\) such that \(\displaystyle a≤y <a +\frac{1}{n}\), for an integer \(\displaystyle "a"\). in box 2, we put all the real "y" such that \(\displaystyle a + \frac{1}{n} ≤y <a + \frac{2}{n}\) for some integer "a", ..., and so on, until the n-th box.

My difficulty is proving that if any number is in the n-th box, the statement already exists, because for me the simultaneous inequality \(\displaystyle a +\frac{n-1}{n} ≤ y <a + \frac {n}{ n}\), produces\(\displaystyle | y-a | >\frac {1}{n}\). I can't understand the algebra involved for the n-th box.

 

[Steven G]

"Let x be any real number. Can it be proven that among the numbers x,2x,…,(n−1)x, there is one element that differs from an integer by at most 1/n?" This is the exact question.

By Pigeonhole, being n boxes,
we put in box 1 all the real \(\displaystyle "y"\) such that \(\displaystyle a≤y <a +\frac{1}{n}\), for an integer \(\displaystyle "a"\). in box 2, we put all the real "y" such that \(\displaystyle a + \frac{1}{n} ≤y <a + \frac{2}{n}\) for some integer "a", ..., and so on, until the n-th box.

My difficulty is proving that if any number is in the n-th box, the statement already exists, because for me the simultaneous inequality \(\displaystyle a +\frac{n-1}{n} ≤ y <a + \frac {n}{ n}\), produces\(\displaystyle | y-a | >\frac {1}{n}\). I can't understand the algebra involved for the n-th box.

You do realize that \(\displaystyle a +\frac{n-1}{n} = a + 1 -\frac{1}{n}≤ y <a + \frac {n}{ n}\) so \(\displaystyle 1 -\frac{1}{n}≤ y-a <1\)?
So of course y-a is within 1/n from the integer 1.
Can you please define a, y? Where is x, 2x, 3x,...?

 

[thecat]

You do realize that \(\displaystyle a +\frac{n-1}{n} = a + 1 -\frac{1}{n}≤ y <a + \frac {n}{ n}\) so \(\displaystyle 1 -\frac{1}{n}≤ y-a <1\)?
So of course y-a is within 1/n from the integer 1.
Can you please define a, y? Where is x, 2x, 3x,...?

"y" is a generic real which will later be replaced by \(\displaystyle x, 2x, ..., (n-1)x\) and "a" is the integer that will be used to calculate the difference. For example, for box 1, we put all the reals "y" such that \(\displaystyle a≤ y <a +\frac{1}{n} \), then \(\displaystyle 0≤y-a<\frac{1}{n}\), and the statement is verified. I wanted to prove it to box "n" too. If the numbers are not in either, we will have \(\displaystyle n-1\) numbers for \(\displaystyle n-2\) boxes, so two of them would be in one, and that is simpler using PHP. My only question is to prove the validity for the n-th box, specifically, why \(\displaystyle a + \frac{n-1}{n} ≤ y <a + \frac{n}{n} \)implies that \(\displaystyle |y-a| <\frac{1}{n}\). It may be simple, but my lack of experience is limiting something.