Let $a, b, c, d$ be odd positive integers and pairwise coprime. For a positive integer $n$, let $$f(n) = \left[\frac{n}{a} \right]+\left[\frac{n}{b}\right]+\left[\frac{n}{c}\right]+\left[\frac{n}{d}\right]$$Prove that $$\sum_{n=1}^{abcd}(-1)^{f(n)}=1$$
Problem
Source: FKMO 2024 P1
Tags: number theory
23.03.2024 13:18
We let $g(n) = (n \mod a) + (n \mod b) + (n \mod c) + (n \mod d)$. Then $f(n) + g(n) \equiv (\left[\frac{n}{a}\right] + a) + (\left[\frac{n}{b}\right] + b) + (\left[\frac{n}{c}\right] + c) + (\left[\frac{n}{d}\right] + d)$ $\equiv (a\left[\frac{n}{a}\right] + a) + (b\left[\frac{n}{b}\right] + b) + (c\left[\frac{n}{c}\right] + c) + (d\left[\frac{n}{d}\right] + d) \equiv n+n+n+n \equiv 0 \, (\mod 2)$. Recall that each $((n \mod a), (n \mod b), (n \mod c), (n \mod d))$ corresponds to each $n$ in $[1,abcd]$. So the number of $n$ in $[1,abcd]$ such that $g(n)$ is odd is $$(\frac{a+1}{2})(\frac{b+1}{2})(\frac{c+1}{2})(\frac{d-1}{2}) + ... + (\frac{a+1}{2})(\frac{b-1}{2})(\frac{c-1}{2})(\frac{d-1}{2}) = \frac{abcd-1}{2},$$So the value we want is $\frac{abcd+1}{2} - \frac{abcd-1}{2}=1$, as desired. *Remark Even though the solution is shorter, the difficulty of solving this on the test was greater than #2.
23.03.2024 13:54
This problem is just a generalization of IMC 2013/2/2, the same approach works as seen in the above solution. It also appears as lemma 2. in the solution below.
23.03.2024 14:26
Maybe I am the one who solved this in the most complicative way...... This is my exact solution in the test... Lemma 1. For coprime odd integers $x,y$ and $k$ such that $(k,xy) = 1$, the following equality holds for any integer $m$. $$\sum_{n = 0}^{xy-1}{(-1)^{\left \lfloor \frac{kn + m}{x} \right \rfloor + \left \lfloor \frac{kn + m}{y} \right \rfloor}} = \sum_{n = 0}^{xy-1}{(-1)^{\left \lfloor \frac{n}{x} \right \rfloor + \left \lfloor \frac{n}{y} \right \rfloor}}$$ Proof 1. Since $\{ kn + m : 0 \le n \le xy - 1 \} = \mathbb{Z}_{xy}$, we have that there are $s_0, s_1, \cdots ,s_{xy-1}$ such that $\{ kn + m : 0 \le n \le xy - 1 \} = \{ xys_{\ell} + \ell : 0 \le \ell \le xy-1 \}$ Here, we can see that $\{ \left \lfloor \frac{kn + m}{x} \right \rfloor + \left \lfloor \frac{kn + m}{y} \right \rfloor : 0 \le n \le xy - 1 \} = \{ (x+y)s_{\ell} + \left \lfloor \frac{\ell}{x} \right \rfloor + \left \lfloor \frac{\ell}{y} \right \rfloor : 0 \le \ell \le xy-1\} \equiv \{ \left \lfloor \frac{\ell}{x} \right \rfloor + \left \lfloor \frac{\ell}{y} \right \rfloor : 0 \le \ell \le xy - 1 \} \pmod 2$ Hence, as desired, we get that $$\sum_{n = 0}^{xy-1}{(-1)^{\left \lfloor \frac{kn + m}{x} \right \rfloor + \left \lfloor \frac{kn + m}{y} \right \rfloor}} = \sum_{\ell = 0}^{xy-1}{(-1)^{\left \lfloor \frac{\ell}{x} \right \rfloor + \left \lfloor \frac{\ell}{y} \right \rfloor}}$$ Lemma 2. For coprime odd integers $x,y$, the following equality holds. $$\sum_{n = 0}^{xy-1}{(-1)^{\left \lfloor \frac{n}{x} \right \rfloor + \left \lfloor \frac{n}{y} \right \rfloor}} = 1$$ Proof 2. Denote the sum $S$, so that it suffices to prove that $S = 1$. $$S = \sum_{i = 0}^{x-1} \sum_{j = 0}^{y-1} (-1)^{\left \lfloor \frac{yi + j}{x} \right \rfloor + \left \lfloor \frac{yi + j}{y} \right \rfloor} = \sum_{i = 0}^{x-1} \sum_{j = 0}^{y-1} (-1)^{\left \lfloor \frac{yi + j}{x} \right \rfloor + i}$$Let $x + y =2k$ and here, we get that $(x,2k) = 1$. $$S = \sum_{i = 0}^{x-1} \sum_{j = 0}^{y-1} (-1)^{\left \lfloor \frac{yi + j}{x} \right \rfloor + i} = \sum_{i = 0}^{x-1} \sum_{j = 0}^{2k-x-1} (-1)^{\left \lfloor \frac{2ki + j}{x} \right \rfloor} = \sum_{i = 0}^{x-1} \sum_{j = 0}^{2k-1} (-1)^{\left \lfloor \frac{2ki + j}{x} \right \rfloor} - \sum_{i = 0}^{x-1} \sum_{j = 2k - x}^{2k-1} (-1)^{\left \lfloor \frac{2ki + j}{x} \right \rfloor} = \sum_{n = 0}^{2kx - 1}{(-1)^{\left \lfloor \frac{n}{x} \right \rfloor}} - \sum_{i = 0}^{x-1} \sum_{j = 2k - x}^{2k-1} (-1)^{\left \lfloor \frac{2ki + j}{x} \right \rfloor}$$Here, we can easily see that $\sum_{n = 0}^{2kx - 1}{(-1)^{\left \lfloor \frac{n}{x} \right \rfloor}} = 0$, so it suffices to prove that $$T = - \sum_{i = 0}^{x-1} \sum_{j = 2k - x}^{2k-1} (-1)^{\left \lfloor \frac{2ki + j}{x} \right \rfloor} = - \sum_{i = 0}^{x-1} \sum_{t = 1}^{x} (-1)^{\left \lfloor \frac{2k(i+1) - t}{x} \right \rfloor} = 1$$ Here, we can see that $$T = - \sum_{i = 0}^{x-1} \sum_{t = 1}^{x} (-1)^{\left \lfloor \frac{2k(i+1) - t}{x} \right \rfloor} = \sum_{i = 1}^{x} \sum_{t = 1}^{x} (-1)^{\left \lfloor \frac{2ki - t}{x} \right \rfloor + 1} = \sum_{i = 1}^{x} \sum_{t = 1}^{x} (-1)^{\left \lfloor \frac{2ki + x - t}{x} \right \rfloor} = \sum_{i = 1}^{x} \sum_{j = 0}^{x - 1} (-1)^{\left \lfloor \frac{2ki + j}{x} \right \rfloor}$$ We divide the sum into two parts to get, $$T = x + \sum_{i = 1}^{x - 1} \sum_{j = 0}^{x - 1} (-1)^{\left \lfloor \frac{2ki + j}{x} \right \rfloor}$$ It is easy to see that, for any integer $i$ in the range $[1,x-1]$, there exists a unique integer $T_i \in \{1, 2, \cdots ,x-1 \}$ that $x \mid 2ki + T_i$ If $2x \mid 2ki + T_i$, we have $2 \mid T_i$ and $\sum_{j=0}^{x-1}{(-1)^{\left \lfloor \frac{2ki + j}{x} \right \rfloor}} = x - 2T_i$ and $x \mid 2k(x-i) + (x - T_i)$ and $2x \nmid 2k(x-i) + (x-T_i)$ so $\sum_{j=0}^{x-1}{(-1)^{\left \lfloor \frac{2k(x-i) + j}{x} \right \rfloor}} = x - 2T_i$. Therefore, $$T = x + \sum_{i = 1}^{x - 1} \sum_{j = 0}^{x - 1} (-1)^{\left \lfloor \frac{2ki + j}{x} \right \rfloor} = x + 2 \times \sum_{2 \mid T_i}{(x - 2T_i)} = x + x(x-1) - 4 \times \sum_{2 \mid T_i}{T_i} = x^2 - 4 \times \sum_{s = 0}^{\frac{x-1}{2}}{2s} = x^2 - 4 \times 2 \times \frac{\frac{x-1}{2} \times \frac{x+1}{2}}{2} = 1$$ Hence, we have that $T = 1$, or, $S = 1$. Now, we will prove that $$\sum_{n=1}^{abcd}(-1)^{f(n)} = \sum_{n=0}^{abcd - 1}(-1)^{\left \lfloor \frac{n}{a} \right \rfloor + \left \lfloor \frac{n}{b} \right \rfloor + \left \lfloor \frac{n}{c} \right \rfloor + \left \lfloor \frac{n}{d} \right \rfloor} = \sum_{i=0}^{ab - 1} \sum_{j = 0}^{cd - 1}(-1)^{\left \lfloor \frac{cdi + j}{a} \right \rfloor + \left \lfloor \frac{cdi + j}{b} \right \rfloor + \left \lfloor \frac{cdi + j}{c} \right \rfloor + \left \lfloor \frac{cdi + j}{d} \right \rfloor}$$ Here, we use Lemma 1, to get $$\sum_{n=1}^{abcd}(-1)^{f(n)} = \sum_{i=0}^{ab - 1} \sum_{j = 0}^{cd - 1}(-1)^{\left \lfloor \frac{cdi + j}{a} \right \rfloor + \left \lfloor \frac{cdi + j}{b} \right \rfloor + \left \lfloor \frac{j}{c} \right \rfloor + \left \lfloor \frac{j}{d} \right \rfloor + (c+d)i} = \sum_{i=0}^{ab - 1} \sum_{j = 0}^{cd - 1}(-1)^{\left \lfloor \frac{cdi + j}{a} \right \rfloor + \left \lfloor \frac{cdi + j}{b} \right \rfloor + \left \lfloor \frac{j}{c} \right \rfloor + \left \lfloor \frac{j}{d} \right \rfloor} = \sum_{i=0}^{ab - 1} \sum_{j = 0}^{cd - 1}(-1)^{\left \lfloor \frac{i}{a} \right \rfloor + \left \lfloor \frac{i}{b} \right \rfloor + \left \lfloor \frac{j}{c} \right \rfloor + \left \lfloor \frac{j}{d} \right \rfloor}$$ Therefore, by Lemma 2, $$\sum_{n=1}^{abcd}(-1)^{f(n)} = \left ( \sum_{i = 0}^{ab - 1}{(-1)^{\left \lfloor \frac{i}{a} \right \rfloor + \left \lfloor \frac{i}{b} \right \rfloor}} \right) \left ( \sum_{j = 0}^{cd - 1}{(-1)^{\left \lfloor \frac{j}{c} \right \rfloor + \left \lfloor \frac{j}{d} \right \rfloor}} \right) = 1 \times 1 = 1$$
27.03.2024 12:08
I solved this on the test for 2 hours, solving this was much more difficult than #2.
Attachments:
2024 fkmo 1.pdf (32kb)
27.03.2024 12:37
Here is my solution which I found pretty straightforward: First note that the parity of $\left\lfloor \frac{n}{a}\right\rfloor$ (which is all that matters) only depends on $n$ modulo $2a$. So the whole function only depends on $n$ modulo $2abcd$. But we are only summing up to $abcd$. So we first try to extend this to the whole range of $2abcd$. Indeed, note that if we change $n$ by $abcd$, then we change the parity of each summand of $f$, thus the parity of $f$ does not change. So we might as well prove that \[\sum_{n=1}^{2abcd} (-1)^{f(n)}=2.\]So now we have a well-defined sum over the residues modulo $2abcd$. Why is this useful? We want to apply the Chinese Remainder Theorem to split this into individual sums modulo $2a,2b,2c,2d$. However, they are not quite coprime. But their gcd is $2$, so this is not too bad. What we get from CRT then is that each tuple $(n_1,n_2,n_3,n_4)$ of residues modulo $2a, 2b, 2c, 2d$ respectively corresponds to a residue modulo $2abcd$ iff all $n_i$ have the same parity. So we just get two sums: those with all $n_i$ odd and all $n_i$ even. The expression now becomes \[\left(\sum_{n_1 \text{ mod } 2a, 2 \mid n_1} (-1)^{\left\lfloor \frac{n_1}{a}\right\rfloor}\right)\left(\sum_{n_2 \text{ mod } 2b, 2 \mid n_2} (-1)^{\left\lfloor \frac{n_2}{b}\right\rfloor}\right)\left(\sum_{n_3 \text{ mod } 2c, 2 \mid n_3} (-1)^{\left\lfloor \frac{n_3}{c}\right\rfloor}\right)\left(\sum_{n_4 \text{ mod } 2d, 2 \mid n_4} (-1)^{\left\lfloor \frac{n_4}{d}\right\rfloor}\right)\]plus the same expression with odd $n_i$. Again, the whole point is that we have separated this into a product of four sums, each of which only involves one of the floor functions. The rest is just a trivial computation: All the sums are equal to $1$ for the even $n_i$ and $-1$ for the odd $n_i$. Hence the total expression is $1^4+(-1)^4=2$ as desired.
30.03.2024 10:45
You can just solve the problem by thinking about when does [n/a]+[n/b]+[n/c]+[n/d]'s mod 2 changes. Let t be the time when a particular one's mod 2 changes. Let's assume that none of others' mod 2 changes. Then the mod2 of sum changes for abcd/a+abcd/b+abcd/d+abcd/d=abc+bcd+cda+dab, therefore it's 0 mod 2 Now, let's think about when two of (a,b,c,d)'s period overlaps. and it's ab,bc,cd,da,abc,bcd,cda,dab,abcd When the sum of it doesn't change, is when a,b/b,c/c,d/d,a ,....'s period overlaps, and when a,b,c,d's period overlaps. the first case is, abcd/ab+abcd/bc+abcd/cd+abcd/da+abcd/ac+abcd/bd=ab+ac+ad+bc+bd+cd and it's 0 mod 2, but we have to not check about when 3 of (a,b,c,d) overlaps. And it's when abc,abd, acd, bcd therefore we should remove abcd/abc+abcd/abd+abcd/acd+abcd/bcd=a+b+c+d and it's also 0 mod 2, and the last one is abcd it's quite easy if you do inclusion-exclusion principle, you can easily prove that it is true. Any errors?
08.06.2024 06:21
Same solution as @above
09.07.2024 14:54
Let $r_a,r_b,r_c$ and $r_d$ be integers with $$0\leqslant r_a\leqslant a-1,\quad0\leqslant r_b\leqslant b-1,\quad0\leqslant r_c\leqslant c-1,\quad0\leqslant r_d\leqslant d-1$$By Chinese Remainder Theorem with $a,b,c,d$ are pairwise coprime, the system of congruences: $$\left\{\begin{array}{l}n\equiv r_a\pmod{a}\\n\equiv r_b\pmod{b}\\n\equiv r_c\pmod{c}\\n\equiv r_d\pmod{d}\end{array}\right.$$must have a unique solution in modulo $abcd$, let's call it $\delta$. Notice that $$f(n)=\left\lfloor\frac{\delta}{a}\right\rfloor+\left\lfloor\frac{\delta}{b}\right\rfloor+\left\lfloor\frac{\delta}{c}\right\rfloor+\left\lfloor\frac{\delta}{d}\right\rfloor=\frac{\delta-r_a}{a}+\frac{\delta-r_b}{b}+\frac{\delta-r_c}{c}+\frac{\delta-r_d}{d}$$Since $a,b,c,d$ are odd integers then \begin{align*} v_2\left(\frac{\delta-r_a}{a}\right)&=v_2(\delta-r_a)-v_2(a)=v_2(\delta-r_a)\\ v_2\left(\frac{\delta-r_b}{b}\right)&=v_2(\delta-r_b)-v_2(b)=v_2(\delta-r_b)\\ v_2\left(\frac{\delta-r_c}{c}\right)&=v_2(\delta-r_c)-v_2(c)=v_2(\delta-r_c)\\ v_2\left(\frac{\delta-r_d}{d}\right)&=v_2(\delta-r_d)-v_2(d)=v_2(\delta-r_d) \end{align*}Which means $f(n)\equiv (\delta-r_a)+(\delta-r_b)+(\delta-r_c)+(\delta-r_d)\equiv r_a+r_b+r_c+r_d\pmod{2}$. By a simple observation, we can get that $$\sum_{n=1}^{abcd}(-1)^{f(n)}=\sum_{n=0}^{abcd-1}(-1)^{f(n)}=\sum_{r_a,r_b,r_c,r_d}(-1)^{r_a+r_b+r_c+r_d}$$this is because from CRT we can bijects $(r_a,r_b,r_c,r_d)$ to every integers in $[0,abcd-1]$. The idea to evaluate all possible values of $r_a+r_b+r_c+r_d$ is via using generating function. Therefore, it suffices to consider the generating function \begin{align*} g(x)=(1+x+\cdots+x^{a-1})(1+x+\cdots+x^{b-1})(1+x+\cdots+x^{c-1})(1+x+\cdots+x^{d-1}) \end{align*}Take note that if we fully expand and simplify $g(x)$, the sum of all coefficients of even degrees is exactly the number of $(r_a,r_b,r_c,r_d)$ such that $r_a+r_b+r_c+r_d$ is even and the sum of all coefficients of odd degrees is exactly the number of $(r_a,r_b,r_c,r_d)$ such that $r_a+r_b+r_c+r_d$ is odd. Furthermore, plugging $x\mapsto -1$ yields the difference between the number of even and odd sums, and $$g(-1)=\underbrace{(1+(-1)+\dots+1)}_a\underbrace{(1+(-1)+\dots+1)}_b\underbrace{(1+(-1)+\dots+1)}_c\underbrace{(1+(-1)+\dots+1)}_d$$So that $g(-1)=1$. Which implies that $$\sum_{n=1}^{abcd}(-1)^{f(n)}=\sum_{r_a,r_b,r_c,r_d}(-1)^{r_a+r_b+r_c+r_d}=1$$as desired.
27.08.2024 14:40
mathlove_13520 wrote: We let $g(n) = (n \mod a) + (n \mod b) + (n \mod c) + (n \mod d)$. Then $f(n) + g(n) \equiv (\left[\frac{n}{a}\right] + a) + (\left[\frac{n}{b}\right] + b) + (\left[\frac{n}{c}\right] + c) + (\left[\frac{n}{d}\right] + d)$ $\equiv (a\left[\frac{n}{a}\right] + a) + (b\left[\frac{n}{b}\right] + b) + (c\left[\frac{n}{c}\right] + c) + (d\left[\frac{n}{d}\right] + d) \equiv n+n+n+n \equiv 0 \, (\mod 2)$. Recall that each $((n \mod a), (n \mod b), (n \mod c), (n \mod d))$ corresponds to each $n$ in $[1,abcd]$. So the number of $n$ in $[1,abcd]$ such that $g(n)$ is odd is $$(\frac{a+1}{2})(\frac{b+1}{2})(\frac{c+1}{2})(\frac{d-1}{2}) + ... + (\frac{a+1}{2})(\frac{b-1}{2})(\frac{c-1}{2})(\frac{d-1}{2}) = \frac{abcd-1}{2},$$So the value we want is $\frac{abcd+1}{2} - \frac{abcd-1}{2}=1$, as desired. *Remark Even though the solution is shorter, the difficulty of solving this on the test was greater than #2. Wow.. wonderful solution !