具体数学第三章作业解答

老师的具体数学作业要电子版了,那就把我自己的解答放在这里。

10.

$$ \begin{array}{l} \left \lceil \frac{2x+1} {2} \right \rceil-\left \lceil \frac{2x+1} {4} \right \rceil+\left \lfloor \frac{2x+1} {4} \right \rfloor \ =\left \lceil \frac{2x+1} {2} \right \rceil-(\left \lceil \frac{2x+1} {4} \right \rceil-\left \lfloor \frac{2x+1} {4} \right \rfloor)\ =\left \lceil x+\frac{1} {2} \right \rceil-[\frac{2x+1}{4}不是整数] \end{array} $$

若$\frac{2x+1}{4}$是整数,则: $$ \begin{array}{l}2x+1=4N \quad (N为整数)\ 2x=4N-1\
x=2N-\frac{1}{2} \end{array}
$$

  • 若${x}\neq\frac{1} {2}$,则原式=$\left \lceil x+\frac{1}{2} \right \rceil-1=\left \lfloor x \right \rfloor$
  • 若$x=\frac{1} {2}$,则原式=$\left \lceil x+\frac{1}{2} \right \rceil=x+\frac{1}{2}=\left \lceil x \right\rceil$

12.

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

则证明:$\left \lceil \frac{n}{m} \right \rceil-\left \lfloor \frac{n-1}{m} \right \rfloor=1$即可

易知:$0<\frac{n}{m}-\frac{n-1}{m}\leq1$(当且仅当m=1时,等式成立)

  • 当m=1时,$\left \lceil n \right \rceil-\left \lfloor n-1 \right \rfloor=n-n+1=1成立$

  • 当$m\neq1$时,

    • 若$\frac{n}{m}$为整数,则$\frac{n-1}{m}<\frac{n-1}{m}且\frac{n-1}{m}不为整数$

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

    • 若$\frac{n-1}{m}$为整数,则$\frac{n-1}{m}<\frac{n-1}{m}且\frac{n}{m}不为整数$

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

    • 若$\frac{n-1}{m}和\frac{n}{m}$均非整数,则n mod m<1 ,(n-1) mod m<1且$\left \lfloor \frac{n}{m} \right \rfloor=\left \lfloor \frac{n-1}{m} \right \rfloor$, 则$\left \lceil \frac{n}{m} \right \rceil-\left \lfloor \frac{n-1}{m} \right \rfloor=1$

证毕

23.

设第n个元素为$xn$且为第m组, 则$xn=m$

此时: $$ \begin{array}{l} \frac{1}{2}m(m-1) m^2-m+\frac{1}{4}<2n (m-\frac{1}{2})^2<2n<(m+\frac{1}{2})^2\ m-\frac{1}{2}<\sqrt{2n} m<\sqrt{2n}+\frac{1}{2} 则m=\left \lfloor \sqrt{2n}+\frac{1}{2} \right \rfloor\ 即x_n=\left \lfloor \sqrt{2n}+\frac{1}{2} \right \rfloor\ \end{array} $$

约瑟夫环

n个人,每隔q个人去掉1人,最终剩下的人的编号?

n个人,初始编号为1, 2, ..., n

重新编号,第1个人:n+1,第2个人:n+2,直至第q个人:去掉,第q+1个人:n+q

假设当前去掉的人的编号为kq,此时去掉了k个人,接下来的人的编号为n+k(q-1)+1

也即:原来kq+d -> 现在n+k(q-1)+d

最后去掉的人编号为nq

令N=n+k(q-1)+d

上一次编号为kq+d=kq+N-n-k(q-1)=k+N-n

$k=\frac{N-n-d}{q-1}=\left \lfloor \frac{N-n-1}{q-1} \right \rfloor$

上一次编号为:

$\left \lfloor \frac{N-n-1}{q-1} \right \rfloor+N-n$

令D=qn+1-N替代N

$$ \begin{array}{l}D = qn + 1 - N \ = qn + 1 - \left( {\left\lfloor {\frac{ {(qn + 1 - D) - n - 1}}{ {q - 1}}} \right\rfloor + qn + 1 - D - n} \right)\ = n + D - \left\lfloor {\frac{ {(q - 1)n - D}}{ {q - 1}}} \right\rfloor \ = D - \left\lfloor {\frac{ { - D}}{ {q - 1}}} \right\rfloor \ = D + \left\lceil {\frac{D}{ {q - 1}}} \right\rceil \ = \left\lceil {\frac{q}{ {q - 1}}D} \right\rceil \end{array} $$