Use the generating function $f(x_1,...,x_p)=\prod_{S\in T}\sum_{x\in S}x_s$, where $T$ is the set of brigades, and $p=2017$, of which we want to find the sum of the coefficients of terms with all exponents being multiples of $4$. So by root of unity filter we have $$N=\frac{1}{4^p}\sum_{\epsilon_i\in\{1,i,-1,-i\}}f(\epsilon_1,...,\epsilon_p)$$. Since $4^2\equiv -1\pmod{17}$, we can use this as $i\pmod{p}$. Consider the sets $S_j=\{1,...,j\}$ and $\sigma(S_j)$ their sum. If all $\sigma(S_j)$ are distinct $\pmod{p}$, at least one is $0\pmod{p}$(it can't be $S_1$ since $\sigma(S_1)=\epsilon_1\neq 0$). If $S_j\equiv S_k$ with $j<k$ then $\sigma(\{j+1,..,k\})\equiv 0\pmod{p}$(it can't be a set with a single element as before). Therefore all terms, since they have a $0$ factor, are zero $\pmod{p}$ and thus $N$ is a multiple of $p=17$.

Very nice and hard problem. It was proposed by Mikhail Antipov, from Russia. The official solution is more or less identical to @above's, but I will write it here for completeness. Assume that every single worker also forms a brigade (with a unique possible leader). In this modified setting, we are interested in the number $N$ of ways to assign leadership so that each worker’s number of assignments is congruent to $1$ modulo $4.$ Consider the variables $x_1, x_2, . . . , x_{17}$ corresponding to the workers. Assign each brigade (from the $i$-th through the $j$-th worker) the polynomial $f_{ij}=x_i+x_{i+1}+...+x_{j},$ and form the following product: \[f=\prod_{1\leq i\leq j\leq 17}f_{ij}\]The number $N$ is the sum $\Sigma(f)$ of the coefficients of all monomials $x^{\alpha_1} x^{\alpha_2} . . . x^{\alpha_{17}}$ in the expansion of $f,$ where the $\alpha_i$ are all congruent to $1$ modulo $4.$ For any polynomial $P,$ let $\Sigma(P)$ denote the corresponding sum. From now on, all polynomials are considered with coefficients in the finite field $\mathbb{F}_{17}.$ Now, if some monomial in the expansion of $f$ is divisible by $x_i^{17},$ replace that $x_i^{17}$ by $x_i;$ this does not alter the above overall vanishing property (by Fermat’s Little Theorem), and preserves $\Sigma(f).$ After several such changes, $f$ transforms into a polynomial $g$ whose degree in each variable does not exceed $16,$ and $g(a_1,a_2,...,a_{17}) = 0$ for all $a_1, a_2, ..., a_{17}$ in $\mathbb{F}_{17}.$ For such a polynomial, an easy induction on the number of variables shows that it is identically zero. Consequently, $\Sigma(g) = 0,$ so $\Sigma(f) = 0$ as well, as desired.

cadaeibf wrote: Use the generating function $f(x_1,...,x_p)=\prod_{S\in T}\sum_{x\in S}x_s$, where $T$ is the set of brigades, and $p=2017$, of which we want to find the sum of the coefficients of terms with all exponents being multiples of $4$. So by root of unity filter we have $$N=\frac{1}{4^p}\sum_{\epsilon_i\in\{1,i,-1,-i\}}f(\epsilon_1,...,\epsilon_p)$$. Since $4^2\equiv -1\pmod{17}$, we can use this as $i\pmod{p}$. Consider the sets $S_j=\{1,...,j\}$ and $\sigma(S_j)$ their sum. If all $\sigma(S_j)$ are distinct $\pmod{p}$, at least one is $0\pmod{p}$(it can't be $S_1$ since $\sigma(S_1)=\epsilon_1\neq 0$). If $S_j\equiv S_k$ with $j<k$ then $\sigma(\{j+1,..,k\})\equiv 0\pmod{p}$(it can't be a set with a single element as before). Therefore all terms, since they have a $0$ factor, are zero $\pmod{p}$ and thus $N$ is a multiple of $p=17$. This solution is very similar to mine, and although I needed some time to handle some parts of it, seemed to be a natural approach to this problem. The multisection formula, even for multivariable polynomials, is not a totally new technique used to count this kind of stuff: see eg P6 from IMO 1995. Nice problem!

See also HMMT 2017 Combinatorics #8 for an example of the same technique.

Actually,I think this might be too easy for RMM P3 Use generating function method: $P(x_1,x_2,...x_{17})=\prod_{1\le i<j\le 17}(x_i+x_{i+1}+...+x_j)$. Then the number of such ways to assign the leaders is $\sum_{i_1,i_2,...i_{17}\in\mathbb{N}}\text{the coefficient of } x_1^{4i_1}x_2^{4i_2}\cdots x_{17}^{4i_{17}}\text{in }P$ Which is $\frac 1 {4^{17}}\sum_{x_1,x_2,...,x_{17}\in\{1,-1,i,-i\}}P(x_1,x_2,...,x_{17})$ Because $4^2\equiv -1\pmod{17}$,we have $\sum_{x_1,x_2,...,x_{17}\in\{1,-1,i,-i\}}P(x_1,x_2,...,x_{17})\equiv\sum_{x_1,x_2,...,x_{17}\in\{1,-1,4,-4\}}P(x_1,x_2,...,x_{17})\pmod{17}$ There is a well known lemma:for any positive integer $n$ and $a_1,a_2,...,a_n\in\mathbb{Z}$,there exist $1\le i\le j\le n$ such that $n\mid(a_i+,...,+a_j)$ Also,if $n\nmid a_1,a_2,...,a_n$,then $i\neq j$ . Pf: If it's not true,suppose $S_i=a_1+,...,+a_i\text{ for }1\le i\le n$.Then $S_1,S_2,...,S_n$ will have different nonzero reminder $\pmod n$,which is contradiction. Acording to the lemma, for any $x_1,x_2,...,x_{17}\in\{1,-1,4,-4\}$ there exist $1\le i<j\le 17$ such that $17\mid (x_i+x_{i+1}+...+x_j)$,then $17\mid P(x_1,x_2,...,x_{17})$. So $\sum_{x_1,x_2,...,x_{17}\in\{1,-1,4,-4\}}P(x_1,x_2,...,x_{17})\equiv 0\pmod {17}$.That solve the problem!

Solved with nukelauncher. Consider the polynomial \[P(x_1,\ldots,x_{17})=\prod_{1\le j<k\le17}(x_j+x_{j+1}+\cdots+x_k).\]Then each monomial \(x_1^{e_1}\cdots x_{17}^{e_{17}}\) refers to a possible distribution of assignments, where \(e_j\) refers to the number of assignments \(x_j\) receives. We wish to count the number of monomials \(M\) with \(e_1\equiv\cdots\equiv e_{17}\equiv0\pmod4\). Let \(i=\sqrt{-1}\). Claim: \[\sum_{x_1,\ldots,x_{17}\in\{\pm1,\pm i\}}P(x_1,\ldots,x_{17})=4^{17}M.\] Proof. Observe that \begin{align*} \sum_{x_1,\ldots,x_{17}\in\{\pm1,\pm i\}}x_1^{e_1}\cdots x_{17}^{e^{17}} &=\prod_{j=1}^{17}\Big[1^{e_j}+i^{e_j}+(-1)^{e_j}+(-i)^{e_j}\Big]\\ &=\prod_{j=1}^{17}\begin{cases}4&e_j\equiv0\pmod4\\0&e_j\not\equiv0\pmod4\end{cases}\\ &=\begin{cases}4^{17}&e_1\equiv\cdots\equiv e_{17}\equiv0\pmod4\\0&\text{otherwise},\end{cases} \end{align*}from which the claim readily follows. \(\blacksquare\) Note \(i\equiv4\pmod{17}\), so \[\sum_{x_1,\ldots,x_{17}\in\{\pm1,\pm4\}}P(x_1,\ldots,x_{17})\equiv4^{17}M\pmod{17}.\]It will suffice to show: Claim: For nonzero integers \(x_1\), \(x_2\), \(x_3\), \(x_4\), we have \(P(x_1,\ldots,x_{17})\equiv0\pmod{17}\). Proof. It suffices to show there are \(j\le k\) with \(x_j+\cdots+x_k\equiv0\pmod{17}\). (We won't have \(j=k\), since \(x_j\not\equiv0\pmod{17}\).) Consider the 17 numbers \[x_1,\quad x_1+x_2,\quad x_1+x_2+x_3,\quad\ldots,\quad x_1+\cdots+x_{17}.\]If neither is zero, by Pigeonhole two are congruent modulo 17, so their difference is zero. \(\blacksquare\) This completes the proof.

Isn't this problem instantly proved with Chevalley-Warning theorem?

Let $X = \{x_1,x_2,\dots,x_{17}\}$ denote a set of parameters representing each of the 17 workers. We consider the generating polynomial \[P(x_1,x_2,\dots,x_{17}) = \prod_{X_0 \subset X}\sum_{x \in X_0}x.\]The degree of $x_i$ in each term represents the worker's number of assignments. We want to keep only the terms with degree divisible by 4 under all $x_i$. This can be done using roots-of-unity filter. Note that 4 is a primitive fourth root modulo 17. The number of ways to assign leaders is expressed as follows. \[\frac{1}{4^{17}}\left(\sum_{x_i \in \{1,4,-1,-4\}}P(x_1,x_2,\dots,x_{17})\right).\]To conclude, we note that among $x_1, x_1 + x_2, \dots, x_1 + x_2 + \cdots + x_{17}$, there is either a partial sum with at least two terms that is divisible by 17, or two nonconsecutive partial sums that are equivalent modulo 17. In either case, we find a multiplicand of $P(x_1,x_2,\dots,x_{17})$ that sums to a multiple of 17. Hence, the sum evaluates to a multiple of 17.

Nguyen wrote: Isn't this problem instantly proved with Chevalley-Warning theorem? Which polynomials do you apply Chevalley-Warning to? I don't see it right away.

We employ generating functions. Let $$f(x_1,\ldots,x_{17})=\prod_{1\leq i<j\leq 17} (x_i+\cdots+x_j).$$Using a roots of unity filter, the number of satisfactory assignments is simply $$\frac{1}{4^{17}}\sum_{x_i \in \{1,i,-1,-i\}} f(x_1,\ldots,x_{17}).$$Viewing this in $\mathbb{F}_{17}$ henceforth, so $i=4 \in \mathbb{F}_{17}$. We then have the following crucial claim. Claim: No matter the choice of $x_i$, we have $f(x_1,\ldots,x_{17})=0$. Proof: Suppose otherwise, so none of the factors are $0$. Consider the factors $x_1,x_1+x_2,\ldots,x_1+\cdots+x_{17}$. By definition $x_1 \neq 0$, and by construction the rest are also nonzero. Thus by Pigeonhole there must exist $i<j$ with $x_1+\cdots+x_i=x_1+\cdots+x_j \implies x_{i+1}+\cdots+x_j=0$. The LHS is a factor of $f(x_1,\ldots,x_{17})$, since $x_{i+1}-x_j \neq 0$ by definition so $j-i\geq 2$: contradiction. Thus each of the individual terms in the summation vanishes, so the summation as a whole vanishes modulo $17$, which is the desired result. $\blacksquare$

Nice mix of basic generating function manipulation and Pigeonhole! Most gen func problems are bland and either have a completely algebraic or completely combinatorial solution, but here it was cool to see Pigeonhole take care of some messy algebra for us. Define the generating function \[ f(x_1,\ldots,x_{17})=\prod_{1\leq i<j\leq 17} (x_i+\cdots+x_j). \]By RoUF, we want to show that \[ S := \frac{1}{4^{17}} \sum_{x_i^4=1} f(x_1,\ldots,x_{17}) \]is divisible by $17$. Consider all polynomials over $\mathbb{F}_{17}[X]$ going forward. Since $4$ and $13$ are the only solutions to $x^2+1\equiv 0 \pmod{17}$, we can assume WLOG that $i \equiv 4 \pmod{17}$ henceforth, so \[ S = \frac{1}{4^{17}} \sum_{x_i=\pm 1, \pm 4} f(x_1,\ldots,x_{17}). \]In fact, we have a stronger claim: Claim: $f(x_1,\ldots,x_{17})$ is identically zero over $\mathbb{F}_{17}^{17}$. Proof. It suffices to show that there exist integers $j \leq k$ such that $x_j +\ldots+x_k=0$. Consider the prefix sums \[ a_i = x_1+\ldots+x_i \]for $1 \leq i \leq 17$. If two $a_i$ are congruent modulo 17, then we are done. If no two $a_i$ are congruent modulo 17, then by Pigeonhole, there exists $a_j$ congruent to zero modulo 17, which also finishes. Thus the claim is true. We conclude.

Was this day in reverse difficulty order? Define a generating function $$f(x_1,\dots,x_{17}) = \sum_{1\le i<j\le 17}\left(x_i+x_{i+1}+\dots+x_j\right).$$ Then the number of ways $N$ to assign leaders is precisely the sum of the coefficients of all terms in which the degree of every $x_i$ is a multiple of $4$. To extract this, we apply a roots of unity filter mod $17$: $$N\equiv\frac{1}{4^{17}}\sum_{(x_1,\dots,x_{17})\in \{4,-1,-4,-1\}^{17}} f(x_1,\dots,x_{17})\pmod{17}$$ (this works because $4$ is a primitive $4^{\text{th}}$ root of unity mod $17$). In fact, we claim that each individual term in this sum is divisible by $17$. Indeed, by PHP $2$ of the prefix sums $0, x_1, x_1+x_2, \dots, x_1+x_2+\dots+x_{17}$ are equivalent mod $17$. Clearly they are nonconsecutive since the $x_i$ are nonzero, so their difference, which is a factor in $f(x_1,\dots,x_{17})$, is a multiple of $17$, as desired.

By roots of unity filter, the number of possible assignments is $$\frac{\sum_{a_1,\dots a_{17}\in \{1,-1,i,-i\}}(a_1+a_2)(a_1+a_2+a_3)\dots(a_{16}+a_{17})}{4^{17}}.$$Taking this mod $17$, we want $$\sum_{a_1,\dots a_{17}\in \{1,-1,4,-4\}}(a_1+a_2)(a_1+a_2+a_3)\dots(a_{16}+a_{17})\equiv 0\pmod{17}$$since $1,-1,4,-4$ are the fourth roots of unity mod $17$. Let $s_i=a_1+a_2+\dots+a_i$ denote the $i$th prefix sum of the $a_i$ (we let $s_0=0$). This then becomes $$\sum_{a_1,\dots a_{17}\in \{1,-1,4,-4\}}(s_2-s_0)(s_3-s_0)\dots(s_{17}-s_0)(s_3-s_1)\dots\dots(s_{17}-s_{15})\pmod{17}$$(essentially the product of differences of all pairs of non-consecutive $s_i$). Clearly, some two of $s_0$ through $s_{17}$ are the same (mod $17$). Furthermore, no two consecutive $s_i$ are the same, as we are adding $1$, $-1$, $4$, or $-4$ at each step. Thus, there exist two nonconsecutive $s_i$ that are equal, so the entire summand is $0\pmod{17}$. Furthermore, this is true regardless of our choices of $a_1\dots a_{17}$ (!!!) so we are done.