Waste less time on Facebook — follow Brilliant.
×

Australian School of Excellence 2015 Combinatorics Exam

  • Each question is worth 7 points

  • Time allowed is 4 hours

  • No books,notes or calculators permitted

  • Write full proofs with your answers

1) Steven has a collection of squares with the following properties.

(i) Each square has side length 2016.

(ii) The sides of each square are parallel to the coordinate axes.

(iii) The vertices of each square have integer coordinates.

(iv) Each pair of squares have exactly two points in common.

What is the maximal number of squares in Steven's collection.

2) Ivan's spacious bathroom floor is in the shape of a 3 metre by 3 metre square. Ivan wishes to tile this floor with nine large square tiles. Each tile is 1 metre by 1 metre, and is either red or blue. However, a 2 metre by 2 metre block of tiles that is all blues is not considered trendy.

In how many different trendy ways can Ivan tile his bathroom floor?

3) Kevin owns 49 coins, one of each value \(\$1, \$2, \$3, \ldots, \$49\). He wishes to put all these coins in his money box, one at a time. However, Kevin suffers from triskaphobia (fear of the number three), so he never wants the amount of money in his money box to be a multiple of three.

In how many different ways can Kevin put the money in his money box?

4) Maven is an expert in tiling square bathroom floors of side length \(n\), where \(n\) is a positive integer. The tiles she uses are in the shape of a \(4 \times 1\) rectangle. The only jobs she is willing to take are those in which she does not have to cut any tiles.

For which values of \(n\) is Maeve willing to take the job?

5) Gavin is doing business with Steven, Ivan, Kevin, Maven and Joven. Gavin owes Ivan $5000. For each of the other four people, either Gavin owes them money, or they owe Gavin money, or neither owes each other anything. A group of three of these five people are called a triad if the net debt/credit of Gavin to the group as whole is zero. For example, if Steven owed Gavin $1667 and Kevin owed Gavin $3333 then Ivan, Steven and Kevin form a triad. Note that a person can be in more than one triad.

(a) What is the maximum possible number of triads to be found among Steven, Ivan, Kevin, Maven and Joven?

(b) For the answer to part (a), what are all possible debts and credits between Gavin and the others?

Note by Sharky Kesa
11 months, 2 weeks ago

No vote yet
1 vote

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...