6
$\begingroup$

Can someone please post some (relatively easy, high school level) combinatorial problems which can be solved with polynomials (but not generating functions).

Here is an example of one such problem:

We have $2n$ different numbers $a_1,\dotsc,a_n, b_1,\dotsc,b_n$. A table $n\times n$ is divided on $n^2$ unit cells and in cell $(i,j)$ we write a number $a_i+b_j$. Suppose that all products of numbers written in cells in each column are the same. Prove that then all products of numbers written in cells in each row are the same.

Idea for a solution: Observe a polynomial $$P(x) = (x+a_1)\dotsb(x+a_n)-(x-b_1)\dotsb(x-b_n)$$

$\endgroup$
  • 1
    $\begingroup$ Simultaneous posting on MSE. $\endgroup$ – Joseph O'Rourke Jan 19 '20 at 21:26
  • 1
    $\begingroup$ Not exactly the same thing, but possibly some of the answers at matheducators.stackexchange.com/questions/13099/… might help. $\endgroup$ – Photon Jan 27 '20 at 21:57
  • 2
    $\begingroup$ I think the MSE has us beat pretty bad on this one. $\endgroup$ – James S. Cook Jan 31 '20 at 4:09
  • 1
    $\begingroup$ See Polya & Szego, Problems in Analysis, the first section of chapter 1. Some require series solutions, but some are polynomial. $\endgroup$ – user2913 Feb 3 '20 at 4:43
  • $\begingroup$ A surprising (and very nice) application is math.stackexchange.com/questions/3031612/… $\endgroup$ – vonbrand Feb 11 '20 at 1:05
7
$\begingroup$

An interesting example is Sicherman dice: A pair of 6-sided dice, with positive number of eyes on each face that are not the classic 1..6 ones; if you throw them, the distribution of total eyes is the same as for two regular dice.

To construct them, one die is represented by:

$\begin{align*} D(z) &= z + z^2 + z^3 + z^4 + z^5 + z^6 \\ &= z (1 + z) (1 - z + z^2) (1 + z + z^2) \end{align*}$

Throwing two dice gives the distribution:

$\begin{equation*} D^2(z) = z^2 (1 + z)^2 (1 - z + z^2)^2 (1 + z + z^2)^2 \end{equation*}$

So we want two dice, call them $D_1(z)$ and $D_2(z)$, such that $D^2(z) = D_1(z) \cdot D_2(z)$. The respective polynomials have to satisfy several conditions:

  • We want that all faces have some eyes, i.e., the constant term of the polynomial has to be zero. We need to assign a $z$ factor to each.
  • The coefficients have to be integers (number of faces with each number of eyes). It is a fun fact that if a polynomial with integer coefficients factors, the primitive factors have integer coefficients (from Gauss' lemma). So this isn't a restriction.
  • The number of faces of the dice has to be six. This is the sum of the coefficients in the polynomial, which is just $D_i(1)$. The respective factors at $z = 1$ are $1$, $2$, $1$ and $3$. We have to give a $1 + z$ and a $1 + z + z^2$ to each, we can shuffle the $1 - z + z^2$ factors around.

Thus the only solution (except for switching the dice, and classical dice) is:

$\begin{align*} D_1(z) &= z (1 + z) (1 + z + z^2) \\ &= z + 2 z^2 + 2 z^3 + z^4 \\ D_2(z) &= z (1 + z) (1 + z + z^2) (1 - z + z^2)^2 \\ &= z + z^3 + z^4 + z^5 + z^6 + z^8 \end{align*}$

This translates into dice with faces marked $\{1, 2, 2, 3, 3, 4\}$ and $\{1, 3, 4, 5, 6, 8\}$.

$\endgroup$
  • 1
    $\begingroup$ (this is neat, my above comment is not a comment about this) $\endgroup$ – James S. Cook Jan 31 '20 at 4:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.