Putnam 2017 A6

The post below has been deleted. Click to close.

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

Kent Merryfield

18574 posts

Kent Merryfield

#1 h Dec 3, 2017, 10:10 PM • 2 Y

Y by RedFlame2112, Adventure10

The $30$ edges of a regular icosahedron are distinguished by labeling them $1,2,\dots,30.$ How many different ways are there to paint each edge red, white, or blue such that each of the 20 triangular faces of the icosahedron has two edges of the same color and a third edge of a different color?

Z K Y

The post below has been deleted. Click to close.

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

Ravi12346

22 posts

Ravi12346

#2 h Dec 3, 2017, 10:10 PM • 4 Y

Y by somepersonoverhere, kevinatcausa, GreenKeeper, Adventure10

Solution

Z K Y

The post below has been deleted. Click to close.

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

62861

3564 posts

62861

#3 h Dec 3, 2017, 10:12 PM • 3 Y

Y by mishai, jeff10, Adventure10

The answer is $12^{10}$ . Replace the colors with residue classes modulo 3; then the condition is that the the three numbers on each face sum to a nonzero result.

Decompose the icosahedron into a pentagonal antiprism and two pentagonal pyramids. There are $3^{10}$ ways to label the lateral edges of the antiprism, and $2^{10}$ ways to label the remaining edges of the antiprism.

Suppose the edge sum for each of the 10 triangle faces on the pyramids is fixed; there are $2^{10}$ possibilities for them. We contend the remaining 10 edges of the icosahedron can be labeled uniquely. This amounts to solving two systems of the form
$\begin{align*} x_0 + x_1 & = c_0\\ x_1 + x_2 & = c_1\\ x_2 + x_3 & = c_2\\ x_3 + x_4 & = c_3\\ x_4 + x_0 & = c_4 \end{align*}$ for $x_0, x_1, x_2, x_3, x_4$ over $\mathbb{F}_3$ , where $c_0, c_1, c_2, c_3, c_4$ are constants. It is easy to verify this has a unique solution, giving a total count of $3^{10} \cdot 2^{10} \cdot 2^{10} = 12^{10}$ .

Z K Y

The post below has been deleted. Click to close.

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

superpi83

1416 posts

superpi83

#4 h Dec 3, 2017, 11:55 PM • 2 Y

Y by Adventure10, Mango247

a combinatorial solution

Z K Y

The post below has been deleted. Click to close.

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

kevinatcausa

374 posts

kevinatcausa

#5 h Dec 7, 2017, 9:32 PM • 3 Y

Y by tapir1729, Adventure10, Mango247

The condition "never have two of one color and a third of a different color" is the fundamental rule underlying the card game Set. If you start looking at the mathematics behind the game,

Ravi12346 wrote:

Ravi12346's first step

is a key starting point.

Z K Y

The post below has been deleted. Click to close.

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

Akababa

12 posts

Akababa

#6 h Feb 25, 2018, 4:03 AM • 2 Y

Y by Adventure10, Mango247

Split into 10 "rhombuses" in a symmetric way wrt two antipodal points. There are $3^{20}$ ways to color the edges of these rhombi, and given such a coloring, each of the remaining 10 diagonals has one or two possible colors. It can be shown that the expected number of ways to color each of these diagonals is $\frac43$ , and that they are independent (the conditional distribution of an edge given the diagonal is uniform, and no two rhombi share more than one edge). Thus the answer is $3^{20}(\frac43)^{10}=12^{10}$ .

This post has been edited 1 time. Last edited by Akababa, Feb 25, 2018, 4:11 AM
Reason: edge

Z K Y

The post below has been deleted. Click to close.

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

linpaws

387 posts

linpaws

#7 h Nov 25, 2018, 8:28 AM • 4 Y

Y by reedmj, Adventure10, Mango247, Mango247

Assign the colors the numbers $1, \omega, \omega^2$ , for $\omega$ a primitive third root of unity. Then, if $x_i$ is the complex number of the color of the $i$ th edge, consider the polynomial

$P=\prod_{i, j, k \text{ form a face}} (x_ix_jx_k-1)(x_ix_jx_k+2)$ .

If $x_i, x_j, x_k$ are all the same or all different for any edge formed by $i, j, k$ , then $P=0$ . Otherwise, $x_ix_jx_k=\omega, \omega^2$ , and $(x_ix_jx_k-1)(x_ix_jx_k+2)=-3$ , so $P=3^{20}$ , since there are $20$ faces.

If the number we are trying to count is $N$ , then if we sum $P$ over all $3^{30}$ possible combinations of $x_i$ , we get $N*3^{20}$ . Also, if we expand $P$ and sum over each term, every nonconstant term sums to $0$ (it is easy to check that any term will have some $x_i$ raised to a power not divisible by $3$ , so it will have expected value $0$ ). The constant term is $2^{20}$ , so the sum over all $P$ is $3^{30}2^{20}$ . Then, $N=3^{10}2^{20}$ .

Motivation: trying to come up with a polynomial to count the number is a common technique (e.g. 2017 HMMT February Combo #8). The product of $(x_ix_jx_k-1)$ is a natural choice, but it doesn't quite work, because it can be $\omega-1$ or $\omega^2-1$ . It turns out that multiplying by $(x_ix_jx_k+2)$ makes the polynomial the same for any valid case.

This post has been edited 1 time. Last edited by linpaws, Nov 25, 2018, 8:31 AM
Reason: added motivation

Z K Y

The post below has been deleted. Click to close.

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

RedFlame2112

1444 posts

RedFlame2112

#8 h Jul 29, 2021, 12:11 AM

Y by

One of my favorite group theory/lin alg exercises I've recently happened to come across.

My thought process through the whole problem

@below bruh nou :omighty:

This post has been edited 12 times. Last edited by RedFlame2112, Feb 19, 2022, 4:39 PM

Z K Y

The post below has been deleted. Click to close.

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

CANBANKAN

1301 posts

CANBANKAN

#10 h Jan 7, 2023, 12:59 AM

Y by

Note: @above is not orzing me.

This problem is given as Canada Winter Camp Buffet. We present two solutions of the problem. The first solution is by Warren, and the second solution is by me.

Solution 1: Pick a spanning tree of 11 vertices in the graph. Since the spanning tree has 11 vertices, it has 11-1=10 edges, and they can be colored in any way, giving $3^{10}$ ways.

See argument in the diagrams to see $2^{20}$ ways to color the remaining edges.

Diagram 1

Diagram 2

:omighty:

Remark: Warren says that any spanning tree works because all faces are triangular, which is motivated by the construction of the planar graph. The fact that I need to use 11 vertices instead of 12 is slightly unmotivated.

Solution 2 (mine): Label the edges $x_1,\cdots,x_{30}$ . Color them with $1,\omega,\omega^2$ where $\omega$ is a primitive 3rd root of unity, and the three numbers correspond to different colors. Then a coloring is valid if

$\prod_{x_i,x_j,x_k \text{ forms a face}} \frac{(1-x_ix_jx_k) (1-x_i^2x_j^2x_k^2)}{3}$
is equal to 1; otherwise, this is equal to 0.

Thus we need to compute

$\sum_{x_1,\cdots,x_{30} \in \{1,\omega,\omega^2\} } \prod_{x_i,x_j,x_k \text{ forms a face}} \frac{2-x_ix_jx_k-x_i^2x_j^2x_k^2}{3}$
Expanding this and picking a monomial from $\{2,-x_ix_jx_k,-(x_ix_jx_k)^2\}$ to get $\sum_{x_1,\cdots,x_{30} \in \{1,\omega,\omega^2\} } \sum_{\text{ monomial }} c x_1^{l_1} \cdots x_{30}^{l_{30}} = \sum_{\text{ monomial }} c \prod\limits_{j=1}^{30} (1+\omega^{l_j} + \omega^{2l_j})$
We can only terms of the form $x_1^{3k_1} x_2^{3k_2} \cdots x_{30}^{3k_{30}}$ have nonzero contribution to the sum.

Claim: The only way to get a term of this form is to always pick 2.

Proof: The key insight is that each edge is only adjacent to two faces. If I consider a graph where each vertex represents a face, and two vertices are adjacent if their respective faces share an edge. Take an odd cycle. Then if I pick $(x_ix_jx_k)^a$ on a face formed by $x_i,x_j, x_k$ , I must pick $(x_ax_bx_c)^{2a}$ on the other face. The odd cycle (see the diagram on exponents picked) gives a contradiction.

Thus, our answer is $\sum_{x_1,\cdots,x_{30} \in \{1,\omega,\omega^2\} } \prod_{x_i,x_j,x_k \text{ forms a face}} \frac{2}{3} = 3^{10} 2^{20}$
Diagram for my solution

This post has been edited 2 times. Last edited by CANBANKAN, Jan 7, 2023, 4:51 AM

Z K Y