Coloring 75 integers in {0,...99} red

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Coloring 75 integers in {0,...99} red

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: USA TSTST 2018 Problem 6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6872 posts

#1 h Jun 26, 2018, 4:29 PM • 8 Y

Y by Amir Hossein, v4913, FaThEr-SqUiRrEl, centslordm, Hoto_Mukai, Adventure10, Mango247, john0512

Let $S = \left\{ 1, \dots, 100 \right\}$ , and for every positive integer $n$ define $T_n = \left\{ (a_1, \dots, a_n) \in S^n \mid a_1 + \dots + a_n \equiv 0 \pmod{100} \right\}.$ Determine which $n$ have the following property: if we color any $75$ elements of $S$ red, then at least half of the $n$ -tuples in $T_n$ have an even number of coordinates with red elements.

Ray Li

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3575 posts

#2 h Jun 26, 2018, 4:56 PM • 3 Y

Y by FaThEr-SqUiRrEl, centslordm, Adventure10

Presumably there's a better way than to spoilers

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6872 posts

#3 h Jun 26, 2018, 5:04 PM • 7 Y

Y by Amir Hossein, MasterYi, v4913, FaThEr-SqUiRrEl, centslordm, Adventure10, Mango247

We claim this holds exactly for $n$ even.

First solution by generating functions Define $R(x) = \sum_{s \text{ red}} x^s, \qquad B(x) = \sum_{s \text{ blue}} x^s.$ (Here ``blue'' means ``not-red'', as always.) Then, the number of tuples in $T_n$ with exactly $k$ red coordinates is exactly equal to $\binom nk \cdot \frac 1{100} \sum_{\omega} R(\omega)^k B(\omega)^{n-k}$ where the sum is over all primitive $100$ th roots of unity. So, we conclude the number of tuples in $T_n$ with an even (resp odd) number of red elements is exactly $\begin{align*} X &= \frac1{100} \sum_{\omega} \sum_{k \text{ even}} \binom nk R(\omega)^k B(\omega)^{n-k} \\ Y &= \frac1{100} \sum_{\omega} \sum_{k \text{ odd}} \binom nk R(\omega)^k B(\omega)^{n-k} \\ \implies X-Y &= \frac 1{100} \sum_{\omega} \left( B(\omega)-R(\omega) \right)^n \\ &= \frac 1{100} \left[ \left( B(1)-R(1) \right)^n + \sum_{\omega \neq 1} (2B(\omega))^n \right] \\ &= \frac 1{100} \left[ \left( B(1)-R(1) \right)^n - (2B(1))^n + 2^n \sum_{\omega} B(\omega)^n \right] \\ &= \frac 1{100} \left[ \left( B(1)-R(1) \right)^n - (2B(1))^n \right] + 2^n Z \\ &= \frac 1{100} \left[ \left( -50 \right)^n - 50^n \right] + 2^n Z. \end{align*}$ where $Z \overset{\text{def}}{=} \frac 1{100} \sum_{\omega} B(\omega)^n \ge 0$ counts the number of tuples in $T_n$ which are all blue. Here we have used the fact that $B(\omega)+R(\omega)=0$ for $\omega \neq 1$ .

We wish to show $X-Y \ge 0$ holds for $n$ even, but may fail when $n$ is odd. This follows from two remarks:

If $n$ is even, then $X-Y = 2^n Z \ge 0$ .
If $n$ is odd, then if we choose the coloring for which $s$ is red if and only if $s \not\equiv 2 \pmod 4$ ; we thus get $Z = 0$ . Then $X-Y = -\frac 2{100} \cdot 50^n < 0$ .

Second solution by strengthened induction and random coloring We again prove that $n$ even work. Let us define $T_n(a) = \left\{ (a_1, \dots, a_n) \in S^n \mid a_1 + \dots + a_n \equiv a \pmod{100} \right\}.$ Also, call an $n$ -tuple good if it has an even number of red elements. We claim that $T_n(a)$ also has at least 50\% good tuples, by induction.

This follows by induction on $n \ge 2$ . Indeed, the base case $n = 2$ can be checked by hand, since $T_2(a) = \{ (x, a-x) \mid x \in S \}$ . With the stronger claim, one can check the case $n=2$ manually and proceed by induction to go from $n-2$ to $n$ , noting that $T_{n}(a) = \bigsqcup_{b+c=a} T_{n-2}(b) \oplus T_2(c)$ where $\oplus$ denotes concatenation of tuples, applied set-wise. The concatenation of an $(n-2)$ -tuple and $2$ -tuple is good if and only if the both or neither are good. Thus for each $b$ and $c$ , if the proportion of $T_{n-2}(b)$ which is good is $p \ge \frac{1}{2}$ and the proportion of $T_2(c)$ which is good is $q \ge \frac{1}{2}$ , then the proportion of $T_{n-2}(b) \oplus T_2(c)$ which is good is $pq + (1-p)(1-q) \ge \frac{1}{2}$ , as desired. Since each term in the union has at least half the tuples good, all of $T_n(a)$ has at least half the tuples good, as desired.

It remains to fail all odd $n$ . We proceed by a suggestion of Yang Liu and Ankan Bhattacharya by showing that if we pick the $75$ elements randomly, then any particular tuple in $S^n$ has strictly less than 50\% chance of being good. This will imply (by linearity of expectation) that $T_n$ (or indeed any subset of $S^n$ ) will, for some coloring, have less than half good tuples.

Let $(a_1, \dots, a_n)$ be such an $n$ -tuple. If any element appears in the tuple more than once, keep discarding pairs of that element until there are zero or one; this has no effect on the good-ness of the tuple. If we do this, we obtain an $m$ -tuple $(b_1, \dots, b_m)$ with no duplicated elements where $m \equiv n \equiv 1 \pmod 2$ . Now, the probability that any element is red is $\frac34$ , so the probability of being good is $\begin{align*} \sum_{k \text{ even}}^m \binom{m}{k} \left( \frac 34 \right)^k \left( -\frac 14 \right)^{m-k} &= \frac{1}{2}\left[ \left( \frac34 + \frac 14 \right)^m - \left( \frac 34 - \frac 14 \right)^m \right] \\ &= \frac{1}{2} \left[ 1 - \left( \frac12 \right)^m \right] < \frac{1}{2}. \end{align*}$
Remark: [Adam Hesterberg] Here is yet another proof that $n$ even works. Group elements of $T_n$ into equivalence classes according to the $n/2$ sums of pairs of consecutive elements (first and second, third and fourth, \ldots). For each such pair sum, there are at least as many monochrome pairs with that sum as nonmonochrome ones, since every nonmonochrome pair uses one of the 25 non-reds. The monochromaticity of the pairs is independent. If $p_i \le \frac12$ is the probability that the $i$ th pair is nonmonochrome, then the probability that $k$ pairs are nonmonochrome is the coefficient of $x^k$ in $f(x) = \prod_i(xp_i+(1-p_i))$ . Then the probability that evenly many pairs are nonmonochrome (and hence that evenly many coordinates are red) is the sum of the coefficients of even powers of $x$ in $f$ , which is $(f(1) + f(-1))/2 = (1 + \prod_i(1-2p_i))/2 \ge \frac12$ , as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

355 posts

#4 h Jun 26, 2018, 5:12 PM • 4 Y

Y by Amir Hossein, FaThEr-SqUiRrEl, centslordm, Adventure10

The answer is $n$ even.

First suppose $n$ is odd. Then if we color all numbers $\not \equiv 2\pmod 4$ red, then one can use your favorite counting method (on the test I used roots of unity filter) to count that the number of $n$ -tuples with an even number of red coordinates minus the number with an odd number of red coordinates is $-50^{n-1}$ which is negative, thus odd $n$ don't work.

Let $T_{n,a}=\{(a_1,...,a_n)\in S^n | a_1+...+a_n\equiv a \pmod{100}\}$ , and $E_{n,a}$ is the subset of $T_{n,a}$ with an even number of red coordinates, and let $O_{n,a}=T_{n,a}\backslash E_{n,a}$ . We claim that if $n$ is even, then $|E_{n,a}|\le\frac{1}{2}|T_{n,a}|$ , which taking $a=0$ implies the result.

We first note that this follows in the $n=2$ case by the principle of inclusion-exclusion, as the sets $R$ of red numbers and $\{a\}-R$ have intersection at least 50.

Now suppose $n=2k$ , then by breaking into blocks of $2$ we can expand as follows
$E_{2k,a}-O_{2k,a}=\sum_{(x_1,...,x_k)\in S^k, x_1+...+x_k\equiv a \pmod{100}} (E_{2,x_1}-O_{2,x_1})(E_{2,x_2}-O_{2,x_2})\dotsm(E_{2,x_k}-O_{2,x_k}).$ But all the terms $E_{2,x_i}-O_{2,x_i}$ are nonnegative by the $n=2$ case so the entire expression is nonnegative as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2130 posts

DrMath

#5 h Jun 26, 2018, 8:13 PM • 5 Y

Y by Amir Hossein, FaThEr-SqUiRrEl, centslordm, Adventure10, Mango247

We claim the answer is all even $n$ .

Let $E(n, i)$ denote the number of $n-$ tuples in $S^n$ with an even number of red elements with sum equal to $i\pmod{100}$ and $O(n,i)$ similarly. Let $f(x)=\sum_{i\text{ red}}x^i-\sum_{j\text{ not red}} x^j$ . Note that the $x^i$ of $f(x)^n\pmod{x^{100}-1}$ gives $E(n,i)-O(n,i)$ ; in particular, the sign of the constant term determines whether or not $E(n,0)\ge O(n,0)$ .

To show that all odd $n$ fail, we just need a counterexample. We claim $f(x)=(-1+x+x^2+x^3)\left(\frac{x^{100}-1}{x^4-1}\right)$ is this counterexample; i.e. everything but multiples of $4$ are colored red. Note that $(-1+x+x^2+x^3)^2\equiv 4\pmod{x^4-1}$ . Thus, $f(x)^{2n+1}\equiv (-1+x+x^2+x^3)^{2n+1}\left(\frac{x^{100}-1}{x^4-1}\right)^{2n+1}\equiv 4^n(-1+x+x^2+x^3)\left(\frac{x^{100}-1}{x^4-1}\right)^{2n+1}\pmod{x^{100}-1}$ On the other hand, $\left(\frac{x^{100}-1}{x^4-1}\right)^{2n+1}=(1+x^4+\cdots + x^{96})^{2n+1}\equiv a_0+a_4x^4+\cdots + a_{96}x^{96}\pmod{x^{100}-1}$ for some coefficients $a_i>0$ . Thus, $f(x)^{2n+1}\equiv 4^n(-1+x+x^2+x^3)(a_0+a_4x^4+\cdots + a_{96}x^{96})\equiv -4^na_0+\cdots \pmod{x^{100}-1}$ has a negative constant term, and thus $E(2n+1,0)<O(2n+1,0)$ , showing this counterexample works.

To show that all even $n$ work, we first claim that $E(2, i)\ge O(2, i)$ for any $i$ . First, if $i$ is odd, then among all the tuples $(a,b)$ with $a+b\equiv i\pmod{100}$ , $a\neq b$ . Now, $O(2,i)$ counts the number of tuples with a non-red element, which is at most $50$ since either $a$ is not red or $b$ is not red. Thus, $O(2,i)\le 50$ . However, $O(2,i)+E(2,i)=100$ , so $E(2,i)\ge 50\ge O(2,i)$ . On the other hand, if $i$ is even, then we get $a=b$ in the pairs $(i/2, i/2)$ and $(i/2+50, i/2+50)\pmod{100}$ . However, note that the number of tuples with an even amount of red numbers among $\{(i/2, i/2+50), (i/2+50, i)\}$ is at most that of $\{(i/2, i/2), (i/2+50, i/2+50)\}$ . Applying this transformation, we can use the same argument as in the odd case before to show that $O(2,i)\le 50\rightarrow E(2,i)\ge 50$ (since among all $(a,b)$ , all the $a$ s are distinct and so are all the $b$ s but $a\neq b$ for any pair).

To kill all even $n$ , note that $f(x)^{2n}\equiv \left(f(x)^2\right)^n\equiv (a_0+a_1x+\cdots + a_{99}x^{99})^n\pmod{x^{100}-1}$ Since by the above discussion, $a_i=E(2,i)-O(2,i)\ge 0$ , it follows that $a_0+a_1x+\cdots + a_{99}x^{99}$ has all nonnegative coefficients, so must its $n$ th power, and thus its value modulo $x^{100}-1$ as well. In particular, the constant term is certainly nonnegative and thus $E(2n,0)\ge O(2n,0)$ , as desired. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Generic_Username

1088 posts

Generic_Username

#6 h Jul 15, 2018, 9:06 PM • 3 Y

Y by FaThEr-SqUiRrEl, centslordm, Adventure10

We claim that the property holds iff $n$ is even. Define blue to be not red, and a good tuple to have an even number of red coordinates.

First, we show that $n$ works. Define $T_{n, k} = \{(a_1,\cdots, a_n)\in S^n | a_1+\cdots+a_n\equiv k \mod 100,\}$ and note that by fixing the first $n-1$ elements we get $|T_{n,k}|=100^{n-1}.$ We claim by induction on $n$ that for all even $n,$ at least half the $n$ -tuples in $T_{n, k}$ will have an even number of red coordinates.

For the base case $n=2,$ note that if $k$ is odd then each element in $S$ has an element it can pair with (to sum to $k$ ). Then if a pair can only be bad if there is exactly one blue element among them, and thus the worst that can happen is when the $25$ blue points are spread out between $25$ of the $50$ pairs in which case the property still holds.

If $k$ is even, the same thing holds except the pairs $\tfrac{k}{2},\tfrac{k+100}{2}$ are actually self-loops. But coloring either of them blue will still yield a good pair so we get the same conclusion as above.

Now for the inductive step, let $R_{i,k}\subseteq T_{i,k}$ contain all of the good tuples and let $p_{i,k}=\tfrac{|R_{i,k}|}{|T_{i,k}|}\geq\tfrac{1}{2}$ Then
$\begin{align*}|R_{n+2, k}|&=\sum_{i=0}^{99}\left(|R_{n, i}|\cdot|R_{2, k-i}|+|T_{n,i}-R_{n, i}|\cdot|T_{2,k-i}-R_{2,k-i}|\right)\\&= \sum_{i=0}^{99}(p_{n,i}p_{2,k-i}+(1-p_{n,i})(1-p_{2,k-i}))\cdot 100^{n-1}\cdot 100\\&=100^n\sum_{i=0}^{99}\tfrac{(2p_{n,i}-1)(2p_{2,k-i})+1}{2}\\&\geq100^n\sum_{i=0}^{99}\tfrac{1}{2}=\tfrac{100^{n+1}}{2}=\tfrac{|T_{n+2,k}|}{2},\end{align*}$ as desired.

We now show that odd $n$ fail by choosing a coloring uniformly at random. Then each element is red with probability $\tfrac{3}{4},$ so the probability of a given tuple being good is
$\sum_{k=0}^{(n-1)/2}\binom{n}{2k}\left(\frac{3}{4}\right)^{2k}\left(\frac{1}{4}\right)^{n-2k}=\frac{1}{2}\left(\left(\frac{3}{4}+\frac{1}{4}\right)^n-\left(\frac{3}{4}-\frac{1}{4}\right)^n\right)<\frac{1}{2}$ ,
so by linearity of expectation there is a coloring with less than half its tuples being good.

This post has been edited 1 time. Last edited by Generic_Username, Jul 15, 2018, 9:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1614 posts

yayups

#8 h Nov 29, 2018, 2:51 AM • 4 Y

Y by FaThEr-SqUiRrEl, centslordm, Adventure10, Mango247

The answer is $n$ even.

The main idea is to shift focus to blueness rather than redness (blue iff not red). Suppose we pick an element of $T_n$ randomly. Let $b_i$ be $1$ if the randomly chosen $a_i$ is blue, and $0$ if it is red. Note that if $I\subsetneq[n]=\{1,\ldots,n\}$ , then $(a_i)_{i\in I}$ has a uniform random distribution (note that $I\not=[n]$ ). In particular, this means that $\mathbb{E}\prod_{i\in I}b_i=(1/4)^{|I|}$ . Note that the probability that the number of reds in some randomly chose element of $T_n$ is even is
$\begin{align*} p_e &= \sum_{\substack{I\subset[n]\\|I|\text{ even}}}\mathrm{Pr}\left(b_i=0\iff i\in I\right)\\ &= \sum_{\substack{I\subset[n]\\|I|\text{ even}}}\mathrm{Pr}\left(\prod_{i\in I}(1-b_i)\prod_{i\not\in I}b_i=1\right) \\ &= \sum_{\substack{I\subset[n]\\|I|\text{ even}}}\mathbb{E}\left(\prod_{i\in I}(1-b_i)\prod_{i\not\in I}b_i\right), \end{align*}$ where the last equality follows since $\prod_{i\in I}(1-b_i)\prod_{i\not\in I}b_i$ is a random variable that takes values in $\{0,1\}$ . We can similarly derive that the probability that the number of reds is odd is
$p_o = \sum_{\substack{I\subset[n]\\|I|\text{ odd}}}\mathbb{E}\left(\prod_{i\in I}(1-b_i)\prod_{i\not\in I}b_i\right).$ One can see then that
$p_e-p_o = \mathbb{E}\sum_{I\subset[n]}\left(\prod_{i\in I}(b_i-1)\prod_{i\not\in I}b_i\right)=\mathbb{E}f(b_1,\ldots,b_n),$ where $f(b_1,\ldots,b_n)=\sum_{I\subset[n]}\left(\prod_{i\in I}(b_i-1)\prod_{i\not\in I}b_i\right)$ . Note that $f(b_1,\ldots,b_n)=(2b_1-1)\cdots(2b_n-1)$ by factoring. We noted that all squarefree monmials in the $b_i$ that are not $b_1\cdots b_n$ have expectation $(1/4)^{\text{\# of variables}}$ , so we see that
$p_e-p_o=\mathbb{E}f(b_1,\ldots,b_n) = 2^n\mathbb{E}(b_1\cdots b_n)+(2\cdot(1/4)-1)^n-(2\cdot(1/4))^n,$ or that
$p_e-p_o=\frac{1}{2^n}((-1)^n-1)+2^n\mathbb{E}(b_1\cdots b_n).$ Since the condition of the problem is equivalent to $p_e-p_0>0$ , we see that it is equivalent to
$\frac{\text{\# of elements of }T_n\text{that are all blue}}{|T_n|}>\frac{1}{4^n}(1-(-1)^n).$ If $n$ is even, this is clearly true, so all $n$ even work, as desired. However, if $n$ is odd, we can force $T_n$ to not have any all blue elements by coloring $x\in S$ blue if and only if $x\equiv 2\pmod{4}$ , so the LHS of the inequality is $0$ , whereas the RHS is $2/4^n>0$ . Therefore, $n$ odd cannot possibly satisfy the condition, so we have completed the proof. $\blacksquare$

Remark: In test, I did this argument wrt redness, and got some not-so-good inequality with all red sets that was equivalent to the condition. However, this turns out to not be nearly as helpful as reducing it to all blue. Nevertheless, my efforts earned me 1 point

This post has been edited 1 time. Last edited by yayups, Nov 29, 2018, 2:53 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

894 posts

#9 h Dec 17, 2018, 2:36 PM • 4 Y

Y by FaThEr-SqUiRrEl, centslordm, Adventure10, Mango247

v_Enhance wrote:

We claim this holds exactly for $n$ even.

First solution by generating functions Define $R(x) = \sum_{s \text{ red}} x^s, \qquad B(x) = \sum_{s \text{ blue}} x^s.$ (Here ``blue'' means ``not-red'', as always.) Then, the number of tuples in $T_n$ with exactly $k$ red coordinates is exactly equal to $\binom nk \cdot \frac 1{100} \sum_{\omega} R(\omega)^k B(\omega)^{n-k}$ where the sum is over all primitive $100$ th roots of unity. So, we conclude the number of tuples in $T_n$ with an even (resp odd) number of red elements is exactly $\begin{align*} X &= \frac1{100} \sum_{\omega} \sum_{k \text{ even}} \binom nk R(\omega)^k B(\omega)^{n-k} \\ Y &= \frac1{100} \sum_{\omega} \sum_{k \text{ odd}} \binom nk R(\omega)^k B(\omega)^{n-k} \\ \end{align*}$

Can we say that
$\implies X-Y = \frac 1{100} \sum_{\omega} (B(\omega)-R(\omega))^n \\ = \text{constant term of } (B(x)-R(x))^n \in \{(-1)^n, 1^n\}$ which is always $>0$ when $2|n$ but $< 0$ when $n$ odd ( $(-1)^n$ obtained by coloring $100$ red)? (This sounds quite wrong though)

This post has been edited 1 time. Last edited by stroller, Dec 17, 2018, 2:36 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

894 posts

#10 h Dec 18, 2018, 12:54 PM • 2 Y

Y by FaThEr-SqUiRrEl, Adventure10

Bump....

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

710 posts

#11 h Mar 29, 2019, 12:47 AM • 4 Y

Y by FaThEr-SqUiRrEl, centslordm, Adventure10, Mango247

Generic_Username wrote:

We now show that odd $n$ fail by choosing a coloring uniformly at random. Then each element is red with probability $\tfrac{3}{4},$ so the probability of a given tuple being good is
$\sum_{k=0}^{(n-1)/2}\binom{n}{2k}\left(\frac{3}{4}\right)^{2k}\left(\frac{1}{4}\right)^{n-2k}=\frac{1}{2}\left(\left(\frac{3}{4}+\frac{1}{4}\right)^n-\left(\frac{3}{4}-\frac{1}{4}\right)^n\right)<\frac{1}{2}$

Don't we have to group the elements by value before we can do this? For example, the tuple (100,100,1) does not have the same probability as listed above. (Probability is 1/4, not 7/16) Luckily, we only need to consider the values that appear and odd number of times, and there are an odd number of them so the solution is still the same. Just out of curiosity, how many points would be awarded for a proof n odd not work?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

466 posts

#12 h Sep 11, 2019, 6:12 AM • 4 Y

Y by FaThEr-SqUiRrEl, centslordm, Adventure10, Mango247

This seems to be the same as v_E's first solution but with a slight change at the beginning.

The answer is $n$ even. We proceed with generating functions. Change $S$ to $\{0,1,\dots,99\}$ to match the title of this thread.

Let $R \subset S$ be the set of red elements, with complement $R'$ , and define
$g(x) = \left(1 + x + \dots + x^{99} - 2\sum_{r \in R} x^r \right)^n.$ Note that, when $g(x)$ is expanded, those $n$ -tuples with an even number of red elements will be counted $+1$ times, while those with an odd number will be counted $-1$ times; hence, the sum of the coefficients of $x^{100k}$ terms of $g(x)$ gives us the difference $D$ between the number of $n$ -tuples in $T_n$ with an even number red elements and the number of $n$ -tuples in $T_n$ with an odd number red elements. Apply a roots of unity filter:
$\begin{align*} D &= \frac{1}{100}\sum_{w^{100}=1} g(w)\\ &= \frac{1}{100} \left[ (-50)^n + (-2)^n \sum_{\substack{w^{100}=1 \\ w \neq 1}}\left(\sum_{r \in R} w^r \right)^n \right] \\ &= \frac{1}{100} \left[ (-50)^n + 2^n \sum_{\substack{w^{100}=1 \\ w \neq 1}}\left(\sum_{r \in R'} w^r \right)^n \right]. \end{align*}$ In switching the sum from $R$ to $R'$ , we use the fact that for $w \neq 1$ we have $\sum_{r \in R} w^r + \sum_{r \in R'} w^r = 1 + w + \dots + w^{99} = 0$ . Now define $f(x) =\left( \sum_{r \in R'} x^r \right)^n$ so that $D$ rewrites as
$D=\frac{1}{100} \left[ (-50)^{n}-50^n + 2^n \sum_{w^{100}=1} f(w) \right].$ The claim is that, when $n$ is even, $D$ is necessarily nonnegative, while if $n$ is odd, there is a choice of $R'$ for which $D$ is negative, which solves the problem. If $n$ is even, then we are left with
$D = 2^n \cdot \frac{1}{100}\sum_{w^{100}=1} f(w),$ which is indeed nonnegative since $\frac{1}{100}\sum_{w^{100}=1} f(w)$ counts the number of $n$ -tuples of elements of $R'$ with sum $0 \pmod{100}$ . On the other hand, if $n$ is odd, we can choose $R'$ to be the set of elements of $S$ that are $2 \pmod{4}$ , meaning it is impossible to choose an $n$ -tuple of elements of $R'$ to have sum $0 \pmod{100}$ . Then $\sum_{w^{100}=1} f(w)$ vanishes and what remains is negative, so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#13 h Aug 3, 2020, 11:21 PM • 2 Y

Y by FaThEr-SqUiRrEl, centslordm

Solved with eisirrational.

Let
$A(x)=\sum_{i\text{ red}} x^i, \ B(x)=\sum_{i\text{ not red}} x^i, \text{ and } \ P(x,y)=yA(x)+B(x).$ For example, if $\{1,\ldots,75\}$ are red, then $P(x,y)=yx^1+\cdots+yx^{75}+x^{76}+\cdots+x^{100}$ . Note that $P(x,y)$ is a function only of the coloring of $S$ .

Now, each term of $P(x,y)^n$ corresponds to a tuple $(a_1,\ldots,a_n)$ , and the exponent of $y$ counts the number of reds in this tuple. Consider $\omega$ , a 100th root of unity. Then $P(\omega,y)^n$ makes all the terms that are pure $y$ (no $\omega$ ) correspond to tuples $(a_1,\ldots,a_n)$ with $a_1+\cdots+a_n\equiv 0 \pmod{100}$ . Summing
$Q(y)= \tfrac{1}{100}[ P(1,y)^n+P(\omega,y)^n+\cdots+P(\omega^{99},y)^n]$ leaves only the terms with pure $y$ , so $Q(y)$ is a polynomial only in $y$ . The coefficient of $y^k$ in $Q(y)$ is the number of tuples $(a_1,\ldots,a_n)$ whose sum is a multiple of 100, and which have $k$ reds. Now, if $Q(-1) \ge 0$ , then there are more tuples with even number of reds, so $n$ is good, otherwise $n$ is bad.

Note that $A(1)=75,B(1)=25$ . Also note that $A(x)+B(x)=1+x+\cdots+x^{99}$ , so if $x^{100}=1$ , this is 0. We have
$\begin{align*} Q(-1) &= \sum_{k=0}^{99} P(\omega^k,-1)^n = \sum_{k=0}^{99} [-A(\omega)^k+B(\omega^k)]^n \\ &= (-50)^n + \sum_{k=1}^{99} [2B(\omega^k)]^n = [(-50)^n -50^n] + 2^n \sum_{k=0}^{99} B(\omega^k)^n. \end{align*}$ But note that $\sum_{k=0}^{99} B(\omega^k)^n$ is the sum for $P(\omega^k,y)^n$ but with $A(x)=0$ . So it counts the number of tuples all not red. Hence it is nonnegative. So if $n$ is even, then $Q(-1) \ge 0$ , so $n$ is good.

If $n$ is odd, we can use $B(x)=x^2+x^6+\cdots+x^{98}$ ; then $\sum_{k=0}^{99} B(\omega^k)^n=0$ using the counting argument above. Hence $Q(-1)=-2\cdot 50^n<0$ . So $n$ is bad for $n$ odd.

Remarks

This post has been edited 1 time. Last edited by pad, Aug 3, 2020, 11:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#14 h Sep 15, 2020, 10:58 PM • 2 Y

Y by FaThEr-SqUiRrEl, centslordm

We solve this problem with generating functions. Let $R(x) = \sum_{\text{red } i} x^i$ and $B(x) = \sum_{\text{blue } j} x^j$ . Note that the number of $n$ -tuples with $k$ red elements is $\frac{1}{100}\left(\sum_{x = \omega}\binom{n}{k}R(x)^kB(x)^{n - k}\right)$ where the sum is over all $100$ th roots $\omega^i$ where $i : 0 \to 99$ . Let $P$ denote the number of $n$ -tuples for which $k$ even and $Y$ for which $k$ odd. Our goal is to find all $n$ for which $P \geq Q$ always holds. Indeed, by Binomial Theorem, $\begin{align*} P - Q &= \frac{1}{100}\sum_{x = \omega} \left(\sum_{\text{even } k}\binom{n}{k}R(x)^kB(x)^{n - k} - \sum_{\text{odd } k}\binom{n}{k}R(x)^kB(x)^{n - k}\right)\\&= \frac{1}{100}\sum_{x = \omega} (B(x) - R(x))^n \end{align*}$ which we wish to be always $\geq 0$ . We simplify this expression further using the fact that $R(\omega) + B(\omega) = 0$ for all roots of unity $\omega$ : $\begin{align*} \sum_{x = \omega} (B(x) - R(x))^n &= (B(1) - R(1))^n + \sum_{i = 1}^{99} (B(\omega^i) - R(\omega^i))^n\\&= (B(1) - R(1))^n + \sum_{i = 1}^{99} (2B(\omega^i))^n\\&= (B(1) - R(1))^n - 2^nB(1)^n + \sum_{i = 0}^{99} (2B(\omega^i))^n\\&= (-50)^n - 50^n + 2^n\sum_{i = 0}^{99} B(\omega^i)^n\\ \end{align*}$ where by roots of unity filter, $T = \sum_{i = 0}^{99} B(\omega^i)^n$ counts $100$ times the number of $n$ -tuples that are blue, and is thus nonnegative. As a result, the quantity $(-50)^n - 50^n + 2^n\sum_{i = 0}^{99} B(\omega^i)^n = 2^n\sum_{i = 0}^{99} B(\omega^i)^n \geq 0$ for all even $n$ . Hence all even $n$ work.

For odd $n$ , we may choose all $2 \pmod 4$ numbers to be blue, and it would follow that $T = 0$ due to impossibility, hence clearly $(-50)^n - 50^n$ would be negative, and $P - Q < 0$ .

Since all even $n$ work and odd $n$ do not, our answer is all $\boxed{\text{even } n}$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

779 posts

#15 h Oct 4, 2020, 7:36 PM • 2 Y

Y by FaThEr-SqUiRrEl, centslordm

Let $\omega$ denote a primitive $100$ th root of unity, and let $B,R$ denote the set of blue and red numbers respectively. Define $B(x)=\sum_{i\in B}x^i,$ $R(x)=\sum_{i\in R}x^i.$ By the roots of unity filter, the statement in the problem is equivalent to $S=\sum_{\omega}(B(\omega)-R(\omega))^n\ge 0.$ Note that for all $\omega\ne 1,$ we have $B(\omega)+R(\omega)=\omega+\omega^2+\dots+\omega^{100}=\frac{\omega(\omega^{100}-1)}{\omega-1}=0.$ Therefore,
$\begin{align*} S&=(B(1)-R(1))^n+\sum_{\omega\ne 1}(2B(\omega))^n\\ &= (-50)^n+2^n\left(\sum_{\omega\ne 1}(B(\omega))^n\right)\\ &= (-50)^n+2^n\left(\sum_{\omega}(B(\omega)^n)\right)-50^n\ge 0 \end{align*}$ Observe that the expression $\sum_{\omega}(B(\omega)^n)$ is simply the number of $n$ -element multisets of $B$ with sum divisible by $100.$

If $n$ is even, then the inequality follows from the fact that the aforementioned quantity is nonnegative.

If $n$ is odd, then choose $B=\{2,6,10,\dots,98\}.$ It is easy to see that every $n$ -element multisets of $B$ has sum congruent to $2$ mod $4,$ and in particular, not divisible by $100.$ This implies that $\sum_{\omega}(B(\omega)^n)=100\cdot 0=0,$ so the inequality does not hold.

Hence, the answer is all even $n.$

I used the set $\{2,6,10,\dots,98\}$ as a counterexample for $n$ odd because all the other solutions did; I can't figure out why any set of $25$ odd numbers, like $\{1,3,5,\dots,49\}$ doesn't work. Could someone explain this to me?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

492 posts

#17 h Oct 9, 2020, 12:49 PM • 5 Y

Y by FaThEr-SqUiRrEl, centslordm, Mango247, Mango247, Mango247

hmm... im not sure if this works

ok nvm a friend told me this is wrong

This post has been edited 1 time. Last edited by fukano_2, Mar 20, 2021, 2:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#18 h Apr 6, 2021, 4:30 AM • 2 Y

Y by FaThEr-SqUiRrEl, centslordm

The answer is all $n$ even.

$n$ even:

We proceed by induction on $n$ , and we claim that at least half $(a_1,\cdots,a_n) \in \mathbb{Z}_{100}^n, \sum\limits a_i\equiv r(\bmod\; 100)$ have an even number of red numbers. Call an $n$ -tuple good if it has an even number of red numbers.

Base Case: $n=2$ . Let $M = \{ x: x \text{ red} \}$ and $N=\{ r-x: x \text{ red} \}$ . Then $|M|=|N|=75, |M\cap N|=|M|+|N|-|M \cup N|\ge 150-100=50$ , so we win.

Inductive Step: Notice we are simply concerned about the sign of $f(n,r)=\sum\limits_{\sum\limits_{i=1}^n a_i=r} (-1)^{\sum g(a_i)}$
Where $g(a_i)$ is 1 if $a_i$ is red and 0 otherwise.

We shift the sum of the first two elements, call $s$ which gives a sum of $f(2,s) \cdot f(n-2,r-s)$ .

Therefore, $f(n,r)=\sum\limits_{s=0}^{99} f(2,s)\cdot f(n-2,r-s)\ge 0$ , so we win.

$n$ odd:

Consider all subsets with $m$ elements showing up an odd number of times. Note $2\mid m-n$ .

The probability each element is selected is $\frac 34$ , so the probability that an even number of numbers are selected is $\mathbb{E}$ [set is good] = $\frac 12 \sum\limits_{k=0}^{m} (1+(-1)^k) \binom mk (\frac 34)^k (\frac 14)^{m-k} = \frac 12 (1+(-\frac 12)^m) < \frac 12$ , so we are done by linearity of expectation.

This post has been edited 3 times. Last edited by CANBANKAN, Apr 6, 2021, 3:55 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeronimoStilton

1521 posts

GeronimoStilton

#19 h Apr 6, 2021, 11:57 AM • 2 Y

Y by FaThEr-SqUiRrEl, centslordm

Let $R$ denote the set of red elements. We use the two variable generating function
$f(x,y)=\bigg(\sum_{i\not\in R}x^i + y\sum_{i\in R}x^i\bigg)^n$ to resolve the problem. Let $a$ denote the number of $n$ -tuples in $T_n$ with an even number of red coordinates and $b$ denote the number of $n$ -tuples with an odd number of red coordinates. The question is to determine when $a\ge \tfrac 12 (a+b)$ , that is, when $a\ge b$ or equivalently $a-b\ge 0$ . The $x^ky^j$ coefficient of $f(x,y)$ indicates how many sets of $n$ elements of $S$ have sum $k$ and contain $j$ elements of $R$ . Let $\omega=e^\frac{2\pi i}{100}$ . Then by a roots of unity argument,
$a-b=\tfrac{1}{100}\sum_{j=1}^{100} f(\omega^j,-1).$ Then, it suffices to determine when
$\sum_{j=1}^{100} \left(\sum_{i\not\in R}\omega^{ij}-\sum_{i\in R}\omega^{ij}\right)^n\ge 0$ holds for all $R$ . It is clear that
$\sum_{j=1}^{100} \left(\sum_{i\not\in R}\omega^{ij}-\sum_{i\in R}\omega^{ij}\right)^n=(-50)^n + \sum_{j=1}^{99} \left(\sum_{i\not\in R}\omega^{ij}-\sum_{i\in R}\omega^{ij}\right)^n=(-50)^n + \sum_{j=1}^{99} \left(2\sum_{i\not\in R}\omega^{ij}\right)^n=$ $(-50)^n + 2^n\sum_{j=1}^{99} \left(\sum_{i\not\in R}\omega^{ij}\right)^n = (-50)^n-50^n+2^n\sum_{j=1}^{100} \left(\sum_{i\not\in R}\omega^{ij}\right)^n.$ Remark that
$\sum_{j=1}^{100} \left(\sum_{i\not\in R}\omega^{ij}\right)^n$ is $100$ times the number of $n$ -tuples of non-elements of $R$ with sum divisible by $100$ . Then, if $n$ is even, the sum is at least $0$ for any choice of $R$ . If $n$ is odd, then note that if the set of non-elements of $R$ is $\{1,3,5,7,\dots,49\}$ , then no $n$ -tuples of the non-elements of $R$ have sum divisible by $100$ and the sum is
$-2\cdot50^n<0.$ Hence, the $n$ satisfying the property are even $n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

351 posts

#20 h Aug 11, 2021, 8:52 PM • 4 Y

Y by samrocksnature, centslordm, RedFlame2112, Bradygho

Slightly different solution (sketchy):

For odd, just proceed as the above solutions. For even, we can use the ~~tringel~~ triangle inequality to prove the statement for all $n \geq 8$ , so we only need to resolve the cases $2$ , $4$ , and $6$ . The cases of $2$ and $4$ are easy, and I presume $6$ can be bashed.

This post has been edited 2 times. Last edited by tigerzhang, Aug 11, 2021, 8:55 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3363 posts

#21 h Mar 15, 2023, 5:09 PM • 2 Y

Y by FlyingChangeRider, Combe2768

Let $R$ be the set of red integers $B$ be the set of integers that are not red. Let $A(x) = \sum_{i \in R} x^i$ and $B(x) = \sum_{i \in B} x^i$
Claim: The number of $n$ -tuples in $T_n$ with $k$ red integers is ${n \choose k} \cdot \sum_{j = 0}^{99} A(\omega^j)^kB(\omega^j)^{n-k}$ where $\omega$ is a primitive 100th root of unity.

Notice that the generating function $A(x)^kB(x)^{n-k}$ would count situations with $k$ red integers and $n-k$ non-red integers. Now, the coefficients of the terms $x^{100i}$ correspond to tuples in $T_n$ . This can be easily done with a root of unity filter. Since the tuples are ordered, we need to order $k$ terms that are the same and $n-k$ terms that are the same, which comes out to ${n \choose k}$ . Notice, the only thing we need to multiply after the root of unity filter is the number of ways to order $k$ $A(x)$ 's and $n-k$ $B(x)$ 's. Therefore this gives the desired conclusion.

Notice that we need to prove $\sum_{\text{k even}} \left [ {n \choose k} \cdot \sum_{j = 0}^{99} A(\omega^j)^kB(\omega^j)^{n-k} \right ] \ge \sum_{\text{k odd}} \left [ {n \choose k} \cdot \sum_{j = 0}^{99} A(\omega^j)^kB(\omega^j)^{n-k} \right ]$ Now by subtracting the RHS from the LHS and by binomial theorem we require

$\sum_{i = 0}^{99} (B(\omega^i) - A(\omega^i))^n \ge 0$ Note that this is equal to
$\begin{align*} (-50)^n + \sum_{i = 1}^{99} (B(\omega^i) - A(\omega^i))^n \\ = (-50)^n + \sum_{i = 1}^{99} (2B(\omega^i))^n \\ = (-50)^n + 2^n \cdot \sum_{i = 1}^{99} (B(\omega^i))^n \\ = (-50)^n - (50)^n + 2^n \cdot \sum_{i = 0}^{99} B(\omega^i)^n \end{align*}$ Notice that $\frac{1}{100} \cdot \sum_{i = 0}^{99} B(\omega^i)^n > 0$ because it is the sum of the positive coefficients by root of unity filter.

Notice that if $n$ is even then it is obviously positive. If $n$ is odd we can select any set of $25$ odd numbers to be not red, and this will make the summation equal to $0$ . Therefore the answer is all even $n$ .

This post has been edited 1 time. Last edited by pi271828, Mar 15, 2023, 5:09 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#22 h Jul 26, 2023, 12:38 AM • 1 Y

Y by centslordm

The answer is $n$ even only. Replace $\{1,\ldots,100\}$ with $\{0,\ldots,99\}$ . We use generating functions. Let
$R(x)=\sum_{r \text{ red}} x^r \text{ and } B(x)=\sum_{b \text{ blue}} x^b.$ Then, for some coefficient $k$ , the coefficient of $x^k$ in the expansion of $(B(x)-R(x))^n$ counts the difference between the number of $n$ -tuples which sum to $n$ and have an even amount of red elements, minus the number with an odd amount of red elements. Therefore, we would like to prove that for any choice of coloring, the sum of the $x^{100k}$ coefficients is always nonnegative when $n$ is even, but can be negative if $n$ is odd for a suitable coloring. Let $\omega=e^{2\pi i/100}$ . By a roots of unity filter, $100$ times the sum of the $x^{100k}$ coefficients equals
$\sum_{i=0}^{99}(B(\omega^i)-R(\omega^i))^n=\sum_{i=0}^{99}(2B(\omega^i)-(\omega^{0i}+\cdots+\omega^{99i}))^n\\=\sum_{i=0}^{99}\sum_{k=0}^n \binom{n}{k}(2B(\omega^i))^k(-\omega^{0i}-\cdots-\omega^{99i})^{n-k}.$ If $n-k>0$ , then $(\omega^{0i}+\cdots+\omega^{99i})^{n-k}=\frac{\omega^{100i}-1}{\omega^i-1}$ vanishes for all $\omega^k \neq 1 \iff k \neq 0$ . Thus the sum equals
$\sum_{k=0}^n\binom{n}{k}(2B(1))^k(-100)^{n-k}+\sum_{i=1}^{99} (2B(\omega^i))^n=\sum_{k=0}^n \binom{n}{k}(50)^k(-100)^{n-k}+2^n\sum_{i=0}^{99}B(\omega^i)^n-50^n=(-50)^n-50^n+2^n\sum_{i=0}^{99}B(\omega^i)^n.$ Note that $\sum_{i=0}^{99} B(\omega^i)^n$ , by a roots of unity filter argument, is simply $100$ times the number of $n$ -tuples of all-blue elements whose sum is divisible by $100$ , which is always nonnegative. Therefore, for $n$ even, the above quantity is always at least $(-50)^n-50^n=0$ , so all even $n$ work. For $n$ odd, color any $25$ odd numbers blue, so then the sum of any $n$ blue elements is odd and therefore not divisible by $0$ , hence the above quantity equals $(-50)^n-50^n=-2\cdot 50^n<0$ . Therefore, the answer is precisely $n$ even. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Jul 26, 2023, 12:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8857 posts

#24 h Dec 27, 2023, 9:48 PM

Y by

The answer is $n$ even only.

Consider the generating function $F(x) = \left(\sum_{i=0}^{99} \varepsilon_i x^i \right)^n$ where $\varepsilon_i = -1$ if $i$ is colored red and blue otherwise. The terms in $T_n$ are given by $x^k$ terms in the expansion of $F$ where $100 \mid k$ ; in particular, the coefficient of each individual $x^k$ term is $1$ if there are an even number of red coordinates and $-1$ otherwise.

It follows that the desired condition requires the sum of all the $x^k$ coefficients to be nonnegative. Let $|T|=25$ be the set of the $i$ with $\varepsilon_i = 1$ . Then by roots of unity filter the required condition is equivalent to $0 \leq \sum_{\omega^{100} = 1} \left(\sum_{i=0}^{99} \varepsilon_i \omega^i\right)^n = (-50)^n + 2^n \sum_{i=1}^{99} \left(\sum_{i \in T} e^{i \pi/50} \right)^n = B.$ Let $g(x) = \sum_{i \in T} x^i$ . Before we proceed, we have the following claim:

Claim. $A = \sum_{i=0}^{99} g\left(e^{i \pi/50}\right)^n \geq 0$ .

Proof. Combinatorially, this counts ( $100$ times) the number of $n$ -tuples in $T_n$ such that every element in the $n$ -tuple is blue. This number must be nonnegative. $\blacksquare$

Now we are ready to finish the problem. Rewrite the given sum as $B = 2^n(A-25^n) + (-50)^n$ as $g(1) = 25^n$ . When $n$ is odd, pick $T$ to consist of only odd elements. It follows that $A = 0$ for parity reasons (or, the terms $g(\omega)$ and $g(-\omega)$ in the sum pair up and disappear), which leaves us with $B = -2 \cdot 50^n < 0$ . On the other hand, when $n$ is even, $B \geq -25^n \cdot 2^n + 50^n = 0$ , as needed.

Remark: The choice of $|T| = 25$ in the problem statement is precisely pivotal to guarantee the final inequality.

This post has been edited 1 time. Last edited by HamstPan38825, Dec 27, 2023, 9:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

662 posts

#25 h Oct 4, 2024, 5:22 PM

Y by

Somewhat standard for #6

We claim that the answer is $n$ even, odds fail by coloring all numbers $n$ so that $n \not\equiv 2 \pmod 4$ . Let $R(x) = \sum_{\text{s red }} x^s$ and $B(x) = \sum_{\text{s blue}} x^s$ .
The number of tuples in $T_n$ with exactly $k$ red coordinates is equal to $\binom nk \cdot \frac 1{100} \sum_{\omega} R(\omega)^k B(\omega)^{n-k}$ by Roots Of Unity Filter, where the sum is taken over primitive $100$ -th roots of unity. Let $C,D$ be the number of tuples in $T_n$ with an even and odd (respectively) number of red elements, in what follows $n$ is even, then $C-D = \frac 1{100} \sum_{\omega} \left( B(\omega)-R(\omega) \right)^n =$ $\frac{1}{100}\left((B(1)-R(1))^n-(2B(1))^n + 2^n(\sum_{\omega}B(\omega)^n)\right)$ $= \frac{1}{100}(-50^n-(-50)^n) + \frac{2^n}{100}(\sum_{\omega} B(\omega)^n ) \geq 0$

This post has been edited 2 times. Last edited by math_comb01, Oct 4, 2024, 5:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4178 posts

#26 h Nov 8, 2024, 5:24 AM

Y by

The answer is $n$ even.

Let $R_i=0$ if $i$ is not red and $R_i=1$ if $i$ is red.

Consider the generating function
$P(x,y)=(x^0y^{R_0}+x^1y^{R_1}+\dots+x^{99}y^{R_{99}})^n.$ We wish to find the sum of the cofficents of the terms where the $x$ exponent is a multiple of $100$ and the $y$ exponent is even.

Let $a_1,\dots a_{75}$ denote the red numbers, so
$Q(x)=P(x,1)=(x^0+\dots +x^{99})^n$ and
$R(x)=P(x,-1)=(x^0+\dots +x^{99}-2(x^{a_1}+\dots+x^{a_{75}}))^n.$
Let $\omega$ be a primitive $100$ th root of unity, so we wish to find
$\frac{\sum_{\omega^k} Q(\omega^k)+R(\omega^k)}{200}.$
Clearly, $Q(1)=100^n$ and $Q(\omega^k)=0$ for $k\neq 0$ , so the $Q$ portion evaluates to $\frac{100^n}{200}$ , which is exactly half of the total number of $n$ -tuples in $T_n$ . Thus, the problem is now a matter of whether $\sum R(\omega^k)$ is positive or negative.

Note that
$=\sum R(\omega^k)=R(1)+\sum_{x=\omega^k,k\neq 0} (-2(x^{a_1}+\dots+x^{a_{75}}))^n$ $=(-50)^n+(-2)^n\sum_{x=\omega^k,k\neq 0}(x^{a_1}+\dots+x^{a_{75}})^n.$ Let $b_1,\dots b_{25}$ be the things that are not $a_i$ . Then, because for any $k\neq 0$ , we have $\sum (\omega^k)^{b_i}=-\sum (\omega^k)^{a_i}$ , this becomes
$(-1)^n(50^n+(-2)^n\sum_{x=\omega^k,k\neq 0}(x^{b_1}+\dots+x^{b_{25}})^n).$
If $n$ is even, we want to show that this is nonnegative regardless of $b_i$ . In other words, we wish to show that
$\sum_{x=\omega^k,k\neq 0}(x^{b_1}+\dots+x^{b_{25}})^n \geq -25^n.$ Consider expanding the LHS. If the exponent is not divisible by $100$ , then the sum over $x=\omega^k,k\neq 0$ is $-1$ , because the entire sum is $0$ but $x=1$ is excluded. If it is divisible by $100$ , the sum is $99$ as it's always 1. Since the expansion has $25^n$ terms, each of which is at least $-1$ , it is at least $-25^n$ , as desired. This also shows that the equality case is when no entirely non-red $n$ -tuple sums to a multiple of $100$ (that is, the $-1$ case always occurs and the $+99$ case never does).

Now, to show that odd $n$ fails, we wish to show that there is some choice of $b_1,\dots,b_{25}$ for which the result is negative. Since there is a $(-1)^n$ in front, this is equivalent to
$50^n-2^n\sum_{x=\omega^k,k\neq 0}(x^{b_1}+\dots+x^{b_{25}})^n>0$ $\sum_{x=\omega^k,k\neq 0}(x^{b_1}+\dots+x^{b_{25}})^n<25^n.$ $\sum_{x=\omega^k}(x^{b_1}+\dots+x^{b_{25}})^n<2\cdot 25^n.$ However, if we make all the $b_i$ odd, then no term in the expanded form of the LHS will have an exponent divisible by 100, as all the exponents would be odd due to $n$ being odd. Thus the entire sum would vanish. We are done.

This post has been edited 4 times. Last edited by john0512, Nov 8, 2024, 5:47 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a