2
$\begingroup$

How do I prove or disprove the following statements: $$(a) ∀n ∈ \mathbb N, ∃k ∈ \mathbb N, ∀x ∈ \mathbb R , \lfloor nx \rfloor − n \lfloor x \rfloor ≤ k$$ and $$ (b)\exists k \in \mathbb N, \forall n \in \mathbb N, \forall x \in \mathbb R, \lfloor nx \rfloor − n \lfloor x \rfloor ≤ k $$

I've also been given the following three properties to use: $ (i) \forall x \in \mathbb R, \exists \epsilon \in R, 0 ≤ \epsilon < 1 ∧ x = \lfloor x \rfloor + \epsilon \\ (ii) \forall x \in \mathbb Z, \forall y \in \mathbb R, \lfloor x + y \rfloor = x + \lfloor y \rfloor \\ (iii) \forall x \in \mathbb Z, \lfloor x \rfloor = x $

I know that we must negate the statement$(a)$ first in order to pave the way for a disproof(if it false) by proving: $$ \exists n \in \mathbb N, \forall k \in \mathbb N, \exists x \in \mathbb R, \lfloor nx \rfloor - n \lfloor x \rfloor > k $$ Other than that I have no idea which property to use and in which order. The help would be really appreciated.

$\endgroup$

closed as off-topic by David Richerby, Evil, Yuval Filmus, Gilles Feb 16 '17 at 12:20

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Is this specific to CS somehow? It looks as a pure math question. $\endgroup$ – chi Feb 15 '17 at 13:21
  • 3
    $\begingroup$ I'm voting to close this question as off-topic because it is purely mathematical in nature and seems to have no computational content. $\endgroup$ – David Richerby Feb 15 '17 at 16:28
  • 1
    $\begingroup$ This is Discrete Maths & it is a part of Computer science. Don't discourage Discrete structure questions. $\endgroup$ – Mr. Sigma. Feb 16 '17 at 11:39
  • 1
    $\begingroup$ @Seeker I agree that computer scientists need to know about discrete mathematics, and it's probably taught in all computer science courses. We welcome questions about the use of discrete mathematics within computer science; indeed, theoretical computer science is essentially a subfield of discrete mathematics. However, this question is completely independent of computation. It's a mathematics question that has no link to computer science, so it should be posted on Mathematics rather than here. $\endgroup$ – David Richerby Feb 16 '17 at 14:14
  • 1
    $\begingroup$ @Seeker I think a good rule of thumb is, "Would I expect a computer scientist to give a better answer to this question than a general mathematician?" In this case, I think the answer is "no". $\endgroup$ – David Richerby Feb 16 '17 at 14:17
2
$\begingroup$

You have been given that $$0\le\epsilon<1$$ multiplying by $-1$ \begin{equation} \therefore 0\ge-\epsilon>-1\tag{1} \end{equation} adding $x$ $$\therefore x\ge x-\epsilon> x-1$$ \begin{equation} \therefore x\ge \lfloor x \rfloor >x-1\tag{2} \end{equation} We can use this inequality $(2)$ to show that \begin{equation} \therefore nx\ge n\lfloor x\rfloor > nx - n\tag{3} \end{equation} adding $nx$ to inequality $(1)$ we get $$nx\ge nx-\epsilon > nx -1$$ \begin{equation} nx\ge \lfloor nx \rfloor > nx -1 \tag{4} \end{equation} Using $(3)$ and $(4)$ we can write $$nx-1 - nx<\lfloor nx\rfloor - n \lfloor x\rfloor<nx - (nx - n)$$ $$\therefore -1<\lfloor nx\rfloor - n \lfloor x\rfloor<n $$

$\endgroup$
2
$\begingroup$

The first step is to understand for each $n,k$ the following property holds: $$ P(n,k) \Leftrightarrow \forall x \in \mathbb{R}, \lfloor nx \rfloor - n\lfloor x \rfloor \leq k. $$ If $nx = na + b + \epsilon$, where $a,b \in \mathbb{Z}$, $0 \leq b < n$, and $0 \leq \epsilon < 1$, then $$ \lfloor nx \rfloor = na + b, \quad n\lfloor x \rfloor = na \quad \Longrightarrow \quad \lfloor nx \rfloor - n \lfloor x \rfloor = b. $$ This means that $$\{\lfloor nx \rfloor - n \lfloor x \rfloor : x \in \mathbb{R}\} = \{0,1,\ldots,n-1\}.$$ In particular, $$ P(n,k) \Leftrightarrow k \geq n-1. $$ Your two statements are thus equivalent to $$ \forall n \in \mathbb{N} \exists k \in \mathbb{N}, k \geq n-1, \\ \exists n \in \mathbb{N} \forall k \in \mathbb{N}, k \geq n-1. $$ You take it from here.

$\endgroup$

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