Maths Olympiad Prep

Library / /427 of 462

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Ireland

How many crosswords can we make from the word “CROSSWORD”, assuming the following rules?
1. A crossword has two words, one horizontal and one vertical, intersecting at a single letter.
2. A 'word' is any ordered set of at least two letters. It does not need to be a real word in any language.
3. Letters should be used as often as they appear in "CROSSWORD".
4. Two crosswords are different unless they have the same words oriented the same way and meeting at the same point. For instance, the following three crosswords are different:
Figure 1

Solution

We consider first the sequence of the letters, and then the configuration in which they are arranged. There are 9 letters on CROSSWORD, consisting of 3 unique letters and three duplicate pairs. If all letters were distinct there would be 9!=362,8809! = 362,880 permutations, but because of the three duplicates, this counts each case 23=82^3 = 8 times, and so the number of distinct arrangements allowing for the duplicates is 9!/8=45,3609!/8 = 45,360. We now count the arrangements, for which we show two solutions both leading to 147 cases.

Solution 1. Suppose that the horizontal word has nn letters and so the vertical word has 10n10-n letters, producing 9 letters in total after removing the double-count at the word intersection. There are nn crossing locations for the horizontal word and 10n10-n for the vertical word, and all numbers 2n82 \le n \le 8 are allowed. Thus, the total number of shapes is
n=28n(10n)=16+21+24+25+24+21+16=147 \sum_{n=2}^{8} n(10-n) = 16 + 21 + 24 + 25 + 24 + 21 + 16 = 147

Solution 2. Let us define an improper crossword to be a single nine-letter word, either horizontal or vertical (orientations counted as distinct) with one of those nine letters deemed to be an intersection with a single-letter second word. There are 18 improper crossword arrangements, that is two orientations multiplied by nine positions.
We now count the union of crosswords and improper crosswords. For each crossword or improper crossword, construct a string of 12 characters, these being the 9 characters of CROSSWORD plus three commas. The first part of the string is the horizontal word (including the letter at the intersection), with a comma just after the letter at the intersection, and a further comma at the end of the first word.
The final part of the 12-character string is the vertical word, replacing the character at the intersection with another comma.
As the intersection is not empty, the first position cannot be a comma, but any 3 of the other 11 positions can contain a comma. Therefore, there are (113)=165\binom{11}{3} = 165 valid arrangements. Of these 165, there are 9 with two commas in positions 2 and 3, corresponding to vertical improper crosswords, and 9 with two commas at the end corresponding two horizontal improper crosswords.
Thus the number of proper crossword arrangements is 16518=147165 - 18 = 147.
The number of crosswords is 147×45,360=6,667,920147 \times 45,360 = 6,667,920.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.