HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
  1. Problems
  2. /A club has 12 members. The committee rule allows a committee of any size, including the empty one…
AdvancedMathematicsHigh School (11–12)Roots of Polynomial EquationsproofNumericalOlympiad

A club has 12 members. The committee rule allows a committee of any size, including the empty one…

StemPy LabContributed by StemPy Lab

Try it on paper first. A hint, the key idea and the worked solution are here when you need them.

A club has 121212 members. The committee rule allows a committee of any size, including the empty one, as long as its size is a multiple of 333.

  1. Prove that for any nnn, with ω\omegaω a cube root of unity other than 111,
∑3∣k(nk)\displaystyle \sum_{3 \mid k}\binom{n}{k}3∣k∑​(kn​)
=2n+(1+ω)n+(1+ω2)n3.\displaystyle \quad = \dfrac{2^n + (1 + \omega)^n + (1 + \omega^2)^n}{3}.=32n+(1+ω)n+(1+ω2)n​.
  1. Find how many committees the rule allows for n=12n = 12n=12.
  1. Find also the number of committees whose size is one more than a multiple of 333, and check that the three classes add to 2122^{12}212.

Check your answer

Work it out on paper, then type your number. The answer itself stays hidden.

Need a reminder? The key ideaShowHide

A nonzero polynomial of degree at most nnn has at most nnn roots, so two such polynomials equal at n+1n + 1n+1 points are equal. The remainder on division by D(x)D(x)D(x) agrees with PPP at every root of DDD.

The worked solution

Check an answer or open a hint to unlock the worked solution.

Have you tried it?

Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.

Step 1. Part (a). Add (1+x)n(1 + x)^n(1+x)n at x=1x = 1x=1, ω\omegaω and ω2\omega^2ω2. The term (nk)\binom{n}{k}(kn​) is multiplied by 1+ωk+ω2k1 + \omega^k + \omega^{2k}1+ωk+ω2k. That is 333 when 3∣k3 \mid k3∣k, and 000 otherwise, because then ωk\omega^kωk is a cube root of unity other than 111. Divide by 333.

Step 2. Part (b). (1+ω)12=(−ω2)12=ω24=1(1 + \omega)^{12} = (-\omega^2)^{12} = \omega^{24} = 1(1+ω)12=(−ω2)12=ω24=1, and in the same way (1+ω2)12=1(1 + \omega^2)^{12} = 1(1+ω2)12=1. So the count is 4096+23=1366\dfrac{4096 + 2}{3} = 136634096+2​=1366.

Step 3. Part (c). Multiply by ω−k\omega^{-k}ω−k before adding: the size-one-more class is

13[2n+ω2(1+ω)n\displaystyle \tfrac{1}{3}\left[2^n + \omega^2(1 + \omega)^n\right.31​[2n+ω2(1+ω)n
+ ω(1+ω2)n].\displaystyle \qquad \left. + \,\omega(1 + \omega^2)^n\right].+ω(1+ω2)n].

For n=12n = 12n=12 this is 4096+ω2+ω3=40953=1365\dfrac{4096 + \omega^2 + \omega}{3} = \dfrac{4095}{3} = 136534096+ω2+ω​=34095​=1365.

Step 4. The third class. By the symmetry (12k)=(1212−k)\binom{12}{k} = \binom{12}{12 - k}(k12​)=(12−k12​), the sizes ≡2\equiv 2≡2 give the same total as the sizes ≡1\equiv 1≡1, since 12−k≡−k12 - k \equiv -k12−k≡−k. So it is 136513651365 too, and 1366+1365+1365=4096=2121366 + 1365 + 1365 = 4096 = 2^{12}1366+1365+1365=4096=212.

Answer: 136613661366 committees; 136513651365 of size one more than a multiple of 333. Proof complete.

Log in to save this for later
← All Problems
← A polynomial P of degree 4 has P(k) = k/(k + 1) for k = 0, 1, 2, 3, 4…A power line hangs between two pylons that stand 30 m apart on level ground… →
More onRoots of Polynomial Equations

Discussion (0)

Log in to join the discussion.

Loading…

Learn it in

  1. Polynomial identitiesComplex Roots and Roots of Unity

More on this topic

  1. A polynomial P of degree 4 has P(k) = k/(k + 1) for k = 0, 1, 2, 3, 4…Advanced
  2. A polynomial P(x) leaves the remainder 4 when it is divided by x - 1, the remainder 7 when divided…Hard
  3. A monic quartic P(x) with real coefficients has the roots 2 + i and 1 - 3i…Hard
  4. Find the four roots of z⁴ + 4 = 0 in the form a + bi…
Advanced
  • Let z = √2 + i. Find the monic quartic x⁴ + px² + q with rational coefficients that has z as a root…Advanced
  • All problems on this topic →