arrangements

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

arrangements

G H J

Reveal topic tags

combinatorics proposed

L

G H BBookmark kLocked kLocked NReply

Source: Ireland 2005

The post below has been deleted. Click to close.

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

1311 posts

#1 h Jul 6, 2009, 9:06 PM • 2 Y

Y by Adventure10, Mango247

Determine the number of arrangements $a_1,a_2,...,a_{10}$ of the numbers $1,2,...,10$ such that $a_i>a_{2i}$ for $1 \le i \le 5$ and $a_i>a_{2i+1}$ for $1 \le i \le 4$ .

Z K Y

The post below has been deleted. Click to close.

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

1343 posts

jgnr

#2 h Jul 7, 2009, 1:27 AM • 4 Y

Y by Soundricio, Adventure10, Mango247, and 1 other user

$a_1>a_2,a_3$
$a_2>a_4,a_5$
$a_3>a_6,a_7$
$a_4>a_8,a_9$
$a_5>a_{10}$

Therefore $a_1=\max\{a_1,a_2,\ldots,a_{10}\}=10$ . Note that the two subsets $\{a_2,a_4,a_5,a_8,a_9,a_{10}\}$ and $\{a_3,a_6,a_7\}$ do not affect each other. The number of possible distributions of 1,2,3,...,9 into these subsets is $\binom{9}3=63$ .

Now consider $a_2,a_4,a_5,a_8,a_9,a_{10}$ . $a_2$ is clearly the greatest. As before, $(a_4,a_8,a_9)$ and $(a_5,a_{10})$ do not affect each other, so there are $\binom53=10$ arrangements. But $a_8$ and $a_9$ are interchangeable, so this makes two arrangements. Now we have $63\times10\times2=1260$ arrangements.

Lastly, consider $a_3,a_6,a_7$ . $a_3$ is the greatest, but $a_6$ and $a_7$ are interchangeable. So the total number of arrangements is $1260\times2=2520$ .

Z K Y

The post below has been deleted. Click to close.

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

16123 posts

JBL

#3 h Jul 8, 2009, 1:11 AM • 2 Y

Y by Adventure10, Mango247

Since these Irish problems are all pretty basic as far as Olympiad problems go, I figure it might be worthwhile to mention on a few of them their connection to actual branches of mathematics. So: this question may be considered either to be asking for the number of linear extensions of a (fairly simple) poset or for the number of decreasing labellings of a particular (binary) tree.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a