1
$\begingroup$

I am stuck on solving the equation, given $k\lt\frac{n}{2},\ n,k\ge3$: $$ m=\lceil 2k-\frac{2}{n}\displaystyle\left(\lfloor\frac{n-\lfloor\frac{n}{k+1}\rfloor}{2}\rfloor\right)(k+1)\rceil$$.

I think the value of $m$ would be $k$. But, the detailed solution is beyond my reach. What inequalities and analysis should we use to reach the solution? Also, what if I modify the equation to: $$m=\lceil 2\frac{nk}{n-1}-\frac{2}{n-1}\displaystyle\left(\lfloor\frac{n-\lfloor\frac{n}{k+1}\rfloor}{2}\rfloor\right)(k+1)\rceil$$ Will the value of $m=k+1$ at any value of $n,k$? Any hints Thanks beforehand.

$\endgroup$
  • $\begingroup$ When $n=1$, the value is $2k$. I would try a few values to see what you get. $\endgroup$ – MPW Feb 25 at 11:30
  • $\begingroup$ @MPW thanks, but I've edited my question $\endgroup$ – vidyarthi Feb 25 at 11:33
  • $\begingroup$ Are $n$ and $k$ integers? Nonnegative? Positive? $\endgroup$ – MPW Feb 25 at 11:36
  • $\begingroup$ @MPW yes, I have added that in the question now. Sorry $\endgroup$ – vidyarthi Feb 25 at 11:36
1
$\begingroup$

We calculate the first expression for integer values $k\geq 0, n\geq 1$.

Let $a,b$ be non-negative integer with \begin{align*} n=a(k+1)+b\qquad\quad a,b\geq 0,\ \ 0\leq b<k+1\tag{1} \end{align*} we obtain \begin{align*} \color{blue}{ a(n,k)} &\color{blue}{=\left\lceil 2k-\frac{2}{n}\left(\left\lfloor\frac{n-\left\lfloor\frac{n}{k+1}\right\rfloor}{2}\right\rfloor\right)(k+1)\right\rceil}\\ &=\left\lceil2k-\frac{2}{n}\left(\left\lfloor\frac{n-a}{2}\right\rfloor\right)(k+1)\right\rceil\tag{2}\\ \end{align*}

Here we use (1) to get $\left\lfloor\frac{n}{k+1}\right\rfloor=\left\lfloor\frac{a(k+1)+b}{k+1}\right\rfloor=a+\left\lfloor\frac{b}{k+1}\right\rfloor=a$ noting that $0\leq b<k+1$.

In (2) we consider two cases: $n-a$ even or odd.

Case 1: $n-a$ even

We obtain from (2) \begin{align*} \color{blue}{a(n,k)} &=\left\lceil2k-\frac{2}{n}\left(\frac{n-a}{2}\right)(k+1)\right\rceil\\ &=\left\lceil2k-\left(\frac{n-a}{n}\right)(k+1)\right\rceil\\ &=\left\lceil2k-\left(1-\frac{a}{n}\right)(k+1)\right\rceil\\ &=\left\lceil k-1+\frac{a(k+1)}{n}\right\rceil\\ &=\left\lceil k-1+\frac{n-b}{n}\right\rceil\tag{3}\\ &=\left\lceil k-\frac{b}{n}\right\rceil\\ &\color{blue}{=}\begin{cases} \color{blue}{k}&\color{blue}{\qquad n>k}\\ \color{blue}{k-1}&\color{blue}{\qquad n\leq k}\tag{4} \end{cases} \end{align*}

Comment:

  • In (3) we use again the representation (1).

  • In (4) we observe from (1) that $n=b$ if $n\leq k$ so that $\left\lceil k-\frac{b}{n}\right\rceil=\left\lceil k-1\right\rceil=k-1$.

Case 2: $n-a$ odd

We obtain from (2) \begin{align*} \color{blue}{a(n,k)} &=\left\lceil2k-\frac{2}{n}\left(\frac{n-a-1}{2}\right)(k+1)\right\rceil\\ &=\left\lceil2k-\left(\frac{n-a-1}{n}\right)(k+1)\right\rceil\\ &=\left\lceil2k-\left(1-\frac{a+1}{n}\right)(k+1)\right\rceil\\ &=\left\lceil k-1+\frac{a(k+1)}{n}+\frac{k+1}{n}\right\rceil\\ &=\left\lceil k-\frac{b}{n}+\frac{k+1}{n}\right\rceil\\ &=k+\left\lceil \frac{k+1-b}{n}\right\rceil\\ &\,\,\color{blue}{=k+1}\\ \end{align*}

The last line follows since from (1) we have $b<k+1$.

$\endgroup$
  • $\begingroup$ fantastic! this is what I expected. Actually, this arose from a problem on total coloring of graphs $\endgroup$ – vidyarthi Feb 26 at 17:53
  • $\begingroup$ @vidyarthi: Thanks for your nice comment. You might be able to calculate the second expression in a similar way. $\endgroup$ – Markus Scheuer Feb 26 at 17:54
  • $\begingroup$ Are you sure your arguments are considering the parity of $n-a$? I think it should be $n-b$ right? $\endgroup$ – vidyarthi Feb 26 at 17:56
  • $\begingroup$ @vidyarthi: In case 1 for instance we can omit the floor function in the first line since $n-a$ is even. $\endgroup$ – Markus Scheuer Feb 26 at 18:18
  • 1
    $\begingroup$ @vidyarthi: I think it's valid for any parity. $\endgroup$ – Markus Scheuer Feb 26 at 18:29
0
$\begingroup$

(not a real answer, but formatting doesn't allow as a comment)

I made the following Python code:

import math

def calculate(n,k):
    aux = math.floor((n- math.floor(n/(k+1)))/2)
    return math.floor(2*k - 2/n * aux * (k+1)) +1 


for n in range(3,25):
    for k in range(3, n/2):
        print "n/k/m = ", n , "/", k ,",", calculate(n,k) -2 * k - 1

And it definitely looks like $m = 2k+1$ in the first case.

$\endgroup$
  • $\begingroup$ In the part of return math.floor(2*k-2/n* aux * (k+1)) +1, why did you put $+1$ in the end? $\endgroup$ – vidyarthi Feb 25 at 12:04
  • $\begingroup$ Because floor +1 is equal to the ceiling. $\endgroup$ – Matti P. Feb 25 at 12:05
  • $\begingroup$ but, by using the inequality $\lfloor x\rfloor\le x$, I am getting $m\le k$ in the first case! $\endgroup$ – vidyarthi Feb 25 at 12:07
  • $\begingroup$ just try substituting $k=3$, and $n=8$, you get $m=3$, i.e. what is calculate(8,3)? $\endgroup$ – vidyarthi Feb 25 at 12:11
  • 2
    $\begingroup$ floor +1 is not always equal to ceiling use math.ceil instead. $\endgroup$ – kingW3 Feb 25 at 12:12

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.