3

This is from a discrete math homework question. I really don't know where to begin, except that I understand the concept of a proof by counterexample, just not how to get to it.

In the statement of the pigeonhole, we argued that $$\left\lfloor\frac{n-1}m\right\rfloor+1=\left\lceil\frac{n}m\right\rceil\;.$$

Prove that this is generally not true.

Martin Sleziak
  • 53,687
Marla
  • 153
  • A good way to start is by throwing numbers at it and seeing what happens. – muzzlator Apr 03 '13 at 20:37
  • Wrote the LaTeX for you. But now that I'm looking at it I'm not sure that this is what you meant. Why would you take the floor or ceiling of an integer? Maybe you meant fraction, and not "choose"? – Yoni Rozenshein Apr 03 '13 at 20:37
  • @YoniRozenshein $M$ and $m$ are different, is that expected? Could be $n \in \mathbb{R}\backslash \mathbb{Z}$. – gt6989b Apr 03 '13 at 20:39
  • I'm not sure, I didn't modify that from the original text. Also using "choose" with non-integers is not really done, I think, in beginning discrete math courses (but, maybe? @Marla - can you clarify?). – Yoni Rozenshein Apr 03 '13 at 20:39
  • 1
    @Yoni: Taking the pigeonhole context into account, I’ll bet that Marla meant $$\left\lfloor\frac{n-1}m\right\rfloor+1=\left\lceil\frac{n}m\right\rceil;,$$ and not binomial coefficients at all. – Brian M. Scott Apr 03 '13 at 20:42
  • It is supposed to be floor of n-1/ m + 1 is equal to ceiling of n/m – Marla Apr 03 '13 at 20:43
  • @BrianM.Scott: That sounds plausible. The original question explicitly said "choose", so I guess it might be a case of mis-copying the question. – Yoni Rozenshein Apr 03 '13 at 20:43
  • You two are right, choose was just a mistake on my end. – Marla Apr 03 '13 at 20:44
  • Fixed now. ${}{}$ – Brian M. Scott Apr 03 '13 at 20:44

2 Answers2

7

HINT: The identity

$$\left\lfloor\frac{n-1}m\right\rfloor+1=\left\lceil\frac{n}m\right\rceil$$

is valid for positive integers $m$ and $n$, so you’ll have to look elsewhere for a counterexample. What if $m=-1$ and $n$ is some positive integer? what if $m=1$ and $n$ is not an integer at all?

Brian M. Scott
  • 616,228
4

If it is not assumed that $m,n\in\mathbb{Z}$, then consider $m=3$ and $n=3.5$

robjohn
  • 345,667