Prepared sequences

Here's an alternative (better) argument that the number of prepared sequences of length n is equal to n!, based on some ideas in Ilya's and Emily's papers.

Let p_n denote the number of prepared sequences of length n. Each such sequence arises from a prepared sequence of length (n-1) in one of two, mutually exclusive ways:

- By inserting a copy of the largest element to the left of the leftmost occurrence in the sequence of length (n-1)
- By inserting a new largest element (i.e. one that's larger than the previous largest element) anywhere to the right of the leftmost occurrence of the previous largest element.

Thus a sequence of length (n-1) generates n distinct sequences of length n (and every sequence of length n is generated in exactly one way), and so p_n = n p_{n-1}.

Since p_1 = 1, p_n = n! by induction.

Extra geometry III

Let D be a point inside an acute angled triangle ABC. Show that:

(DA)(DB)(AB) + (DB)(DC)(BC) + (DC)(DA)(CA) &ge (AB)(BC)(CA)

with equality if and only if D is the orthocentre of ABC.

Extra geometry II

Let ABC be a triangle with the angle at A equal to 40 degrees and that at B equal to 60 degrees. Let D and E be the points lying on AC and AB respectively so that angle CBD = 40 degrees and angle BCE = 70 degrees. Let BD and CE meet at F. Show that the line AF is perpendicular to BC.

Extra geometry I

A convex quadrilateral ABCD has AD = CD and angles DAB and ABC are equal and acute. The line through D and the midpoint of BC intersects AB at E. Prove that angles BEC and DAC are equal.

Geometry

Our next assignment (coming soon I promise) will be on geometry. So you might want to spend some time doing a bit of reading of whatever materials you have available.

At the EMAT 4600/6600 webpage towards the bottom you'll find some (fairly elementary) problems with hints and solutions as well as some review of many of the standard theorems. That would be a useful place to start (though Google "geometry problems" will also provide you with much more than you might want to look at -- if you do find something interesting with that, please let me know!)

Have fun.

Hint: Combinatorics Q8

Suppose a colouring satisfies the condition. What is the structure of the edges carrying the maximum label? What is the structure of the rest of the graph?

Hint: Combinatorics Q7

Start small, try to build up blocks of the same colour ...

Hint: Combinatorics Q6

The first obvious, if somewhat repetitive, hint is to work with smaller examples to try and get a feel for what is going on.

The geometric information given "no lines ..." provides quite a lot of algebraic information about the coordinates of the points (and combinations thereof).

Hint: Combinatorics Q5

An obvious invariant: the number of rooms in which all three lights are on, or all three are off.

We want to show that if this invariant is not zero it can be reduced.

If it's not zero, we go to a "same-state" room and flick a switch. This might reduce the invariant. Hurrah we're done.

If it doesn't then what happened? Can we actually have made the situation worse? What's the logical next room to try? What must eventually happen when we keep doing this?

Hint: Combinatorics Q4

This is a classic case where looking at much smaller examples will be a big help. So, go away and write down all the ways of colouring:

The number 1 black or white

The numbers 1 and 2 black or white

The numbers 1, 2 and 3 black or white

And compute the associated numbers. When there's a unique odd value what is it?

Look at some random examples of slightly longer colourings (7, 8, 9 or 10). Consider some special cases (where the black and white pattern is simple). When we get a unique odd value is it always the same? In general, how do the values change as we move through the list from left to right? When do two numbers, particularly consecutive ones, get the same associated value? How can we manipulate colourings without changing the number of values that occur an odd number of times? Aim towards producing a simple colouring which has the same value repeated an odd number of times as a (possibly) complicated one does.

Go on, get your hands dirty -- you come to grips with problems of this type by learning the shape and feel of the problem -- not by attacking it head first.

Remember that when you have 100 keys one of which might fit a lock the main thing is to start trying them, and not to get discouraged when the first ten don't fit. You would never imagine that the solution to that problem was to go out and buy more keys!

Hint: Combinatorics Q3

First part: just be systematic and look for a solution with lots of structure.

What we're trying to accomplish would seem to be helped by having relatively few entries in each row of any given label. So ...

Second part: Much harder.

Consider columns of a supposed labeling. A pair of entries of the same label in the same row of two different columns is a "danger sign". Indicate this danger by connecting the two columns with an edge carrying that label (columns may well be connected by more than one edge). Can two columns be connected with two edges having the same label?

So the maximum allowable number of edges is?

On the other hand any pair of equal labels in any row produces an edge. So the minimum number of labels occurring is?

It would be great if the first answer were smaller than the second -- unfortunately it's not (if you've done it all correctly they'll be equal). But there's one more twist in the tale -- since we have the maximum allowable number of edges we know (in principle) exactly how many of each label there are. On the other hand since we have the minimum possible number of labels, we know how they are produced. Something doesn't match.

Hint: Combinatorics Q2

What is the maximum number of airports we could reach in at most two flights from a given airport?

That implies the maximum total number of airports is?

Can we arrange things to work for this maximum? (Hint: No -- the situation is too tightly constrained, but figuring out the exact blockage will require a little work. Start drawing networks!)

What if we reduce the number of airports by one? (And aim for some sort of symmetric solution?)

Hint: Combinatorics Q1

First of all, how many cubes are there in the brick? (Hint: 5) What does this imply about cubes which we might fill (hint: their side length must be a multiple of 5). So the smallest we could hope to fill is ?? and the next smallest is ??

Working with the smallest case you should find that it seems to be difficult to get it to work out -- something always gets missed or sticks out. Think about the domino problem again. Another way to express the fact that it can't be done is to say: "There are 32 white squares in the truncated board, so we need 32 dominoes. However, there are only 62 squares all together so we could only use 31 dominoes". How many bricks would we use if we could fill the smallest cube? Can we find a bigger set of unit cubes each of which requires its own brick?

Even if you haven't shown the smallest case doesn't work, you might get frustrated and move on to the next case. Now we come to the issue that the bricks are awkward shapes -- so perhaps we should think about making more convenient super-bricks out of groups of the original bricks (e.g. bricks shaped like real bricks!) If we can get a superbrick whose dimensions divide that of the cube we'd be done ...

Invariants

One generally useful technique in handling combinatorial problems is to make use of numbers associated to the configurations which the problem is dealing with. These numbers are called invariants. Often you can show that the configurations can be manipulated somehow in order to reduce or increase the chosen invariant. This is used when we want to show that you can produce a configuration of a certain type, by illustrating that the invariant can be change to match the requirements. We saw this in several examples at camp.

Perhaps equally commonly, invariants are used to show that something can't be accomplished. That is you show that the invariant of the goal configuration has some property (often parity) which can't occur from manipulations of the current value of the invariant. A trivial example of this would be the standard problem of whether a chessboard with two diagonally opposite corners removed can be tiled with dominoes. If we look at an invariant associated with any partial tiling which we take to be the difference between the number of white squares covered and black squares covered, this must always be 0, since each domino covers one square of each colour. On the other hand in the goal, there are two more squares of one colour than the other, so if there were a tiling, its invariant would be 2. Ergo, impossible.

A number of the problems in the problem set make use of invariants (or can be thought of in that way).

More Friendship

On the grounds that you shouldn't criticize something if you're not prepared to do something about it, I wrote up my own version of the proof of the Friendship Theorem. There is nothing new here -- the ideas are the same as in the other notes, just the presentation differs. You can guess which one I prefer! I've also included some internal comments which might be useful in thinking about how to attack problems in this area. Please let me know (good or bad!) what you think of it.

The Friendship Theorem

In the training area of the olympiad site, under the combinatorics section you'll find an article about the "Friendship Theorem". This presents a proof of the result that in a graph in which every two vertices have a unique common neighbour, there exists a vertex which is a neighbour of every other vertex. However, the presentation is a little sloppy in places. By and large the presentation is correct, but be aware (for instance) that the statement of the theorem omits its conclusion (but you can figure out what it should be by reading the preceding paragraph) and that the definition of a path is non-standard. In a path, repeated vertices are normally forbidden -- what's intended here is a "trail" where we permit repeated vertices but forbid repeated edges. Note that the latter condition needs to be specified otherwise we have a "walk" in which both repeated edges and vertices are allowed, and then any edge would be a 4-cycle, x -> y -> x -> y -> x.

Email contact

The squad should all have received an email (or two) from me by now. If you haven't, and have somehow found your way to this blog, please send me your email address ASAP (my address is malbert@cs.otago.ac.nz)