4
$\begingroup$

I was helping out a student in a Maths Olympiad and I'd like to know if there's a better way to solve this problem.

(Source: International Mathematics Assessment for Schools, First Round, Upper Primary Division, Question 24)

Let $a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9$ be distinct non-zero digits such that:

  1. $a_1 < a_2 < a_3 < a_4 < a_5$
  2. $a_1 < a_6, a_2 < a_7, a_3< a_8$ and $a_4 < a_9$

How many different ways are there to assign the values to $a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9$?

Our attempt: $a_1 = 1$, possible values for $a_2$ to $a_5$ are the following:

$a_2$: 2 and 3

$a_3$: 3, 4, 5

$a_4$: 4, 5, 6, 7

$a_5$: 5, 6, 7, 8, 9

We then listed all the possible cases starting from $a_1$ to $a_4$ and tallied them together. For example, in the sequence 1, 2, 3, 4,..., digits 5 to 9 can be arrange in 5! ways.

We got the correct answer of 384 ways.

Ways to improve our solution would be greatly appreciated.

$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Here is a way to take an arbitrary permutation $(a_1,\dots,a_9)$ of the numbers $1,\dots,9$, and switch some entries around to make it satisfy your two rules:

  • Swap $1$ with $a_1$ (if $a_1=1$, do nothing).

  • Swap the smallest number among $a_2,a_3,a_4,a_5,a_7,a_8,a_9$, with $a_2$.

  • Swap the smallest number among $a_3,a_4,a_5,a_8,a_9$ with $a_3$.

  • Swap the smallest number among $a_4,a_5,a_9$ with $a_4$.

Fix a particular valid permutation $(a_1,\dots,a_9)$. We ask the following question; for how many arbitrary permutations $(b_1,\dots,b_9)$ of $1,\dots,9$ will applying the above sorting procedure to $(b_1,\dots,b_9)$ produce $(a_1,\dots,a_9)$? The answer is $9\times 7\times 5\times 3$. Namely, the complete set of permutations which become $(a_1,\dots,a_9)$ after applying the sorting procedure can be produced by the instructions below:

  • Start with the valid permutation $(a_1,\dots,a_9)$.
  • Either do nothing, or swap $a_4$ with $a_5$ or $a_9$. [3 options]
  • Either do nothing, or swap $a_3$ with $a_4,a_5,a_8,$ or $a_9$. [5 options]
  • Either do nothing, or swap $a_2$ with $a_3,a_4,a_5,a_7,a_8,$ or $a_9$. [7 options]
  • Either do nothing, or swap $a_1$ with any other entry [9 options]

Finally, we conclude that the total number of valid permutations is $$ \frac{9!}{9\times 7\times 5\times 3}=384. $$ This is because you can partition all of the $9!$ permutations into groups of size $9\times 7\times 5\times 3$ where each group has a single valid permutation.

$\endgroup$
2
  • $\begingroup$ Do you have/know a (standardized) name for this technique? I consider it as partitioning the entire space into classes, with 1 representative element in each class that satisfies the conditions. The hope is that the size of the classes is constant (or mostly constant). $\quad$ Perhaps this is just a basic version of Polya's enumeration theorem? (But not requiring the group-theory understanding) $\endgroup$ Commented Mar 17 at 18:13
  • $\begingroup$ @CalvinLin I have not heard of any standard name, but I like to call it the rule of division, by analogy with the standard terms "rule of sum" and "rule of product". $\endgroup$ Commented Mar 17 at 23:41

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.