Competition problem — Combinatorics

Library / /597 of 860

Combinatorics Difficulty 5.3 AIME, harder Find the answer

How many ways are there to win tic-tac-toe in $\mathbb{R}^{n}$ ? (That is, how many lines pass through three of the lattice points $(a_{1}, \ldots, a_{n})$ in $\mathbb{R}^{n}$ with each coordinate $a_{i}$ in $\{1,2,3\}$ ? Express your answer in terms of $n$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

A line consists of three points. Each coordinate can do one of three things passing from the first point to the last point: increase by 1 each time, stay the same, or decrease by 1 each time. There are three ways to stay the same (three coordinates), one way to increase by 1, and one way to decrease by 1, so there are $5^{n}$ possible types of behavior. Determining this behavior uniquely determines the end point and start point except that we have traced every line exactly twice (forwards and backwards) and incorrectly counted the $3^{n}$ "lines" where each coordinate stays the same, so we subtract $3^{n}$ and divide by 2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.