Sunday, February 27, 2005

Some Puzzles Regarding Combinatorial Birds

Table of Contents

«It était un fois...» OR "Once upon a time..." there was a magical forest inhabited by singing birds.1 What was magical about this forest was not the birds, as one can find birds that sing most anywhere, and the species of the birds of this magical forest can also be found in many forests around the world. No, it was the songs of the birds that were magical, for a birds song would remain present in the air, present, as if it were a thing unto itself. Furthermore, a bird's song, when joined by other bird songs, could, and often did, change into another bird song (bird songs affected the sound of other bird songs), and a bird song could change the birds in the area, causing them to fly away, or to change their position on the branch, or (this is truly amazing) to become an entirely different species of bird.

The magic properties of the bird songs of this forest obeyed a set of rules. The first rule is that the order in which birds sing is important and affects the combined bird song produced. The second rule is that birds' songs are combined to produce a new bird song in a very specific order ... the normal order is that the first bird singing is first one to be combined into the resulting bird song, but this norm may be changed by the specific bird singing, as you will see below. Let us observe six species of birds to get a feel for these rules.

  1. The simplest of birds in the forest is the identity bird. When it sings, and another bird joins it in song, only that second bird's song is present. It is as if only that second bird is singing.2

  2. The second bird behaves very much like the identity bird, but the results are by no means simple. The mockingbird, when it sings, and other bird sings in response, mimics the other bird's song exactly. It is if two birds of the same species are singing together.

  3. The first two birds sing along with only one other bird. The kestrel sing along with two other birds. When the kestrel sings, joined by one other bird's song, and then the singing is joined by a second, then the kestrel flies off with the second bird, leaving the first bird singing alone. It is as if the only the first bird were singing and the other two (the kestrel and the second singer) had never come to sing.

  4. The cardinal, besides being a very pretty bird to look at, participates with three other singing birds. The effect of the cardinal's song is rather difficult to describe but rather simple in its results: when the cardinal sings, and three other birds join in order (let us call them 'a', 'b', and 'c' simply to identify them), the resulting bird song is a combination of a's song, followed by c's song and then followed by b's song. Simply put, the last two of the three birds' songs are reversed in their order.

    So, normally (as per the second rule), the three birds singing together would produce the 'abc' song, but the cardinal-abc song is different: it is the 'acb' song.

  5. Hang onto your hats, because it gets a wee bit harder from here, for now we meet the bluebird. The bluebird, like the cardinal, sings with three other bird, and, like the cardinal, the last two birds of the three other birds sing differently: a bluebird, joined by birds a, b, and c, have a combined song as if a's song is joined by the song produced by first combining the songs of b and c (in order) together.

    So, normally (again, as per the second rule), the three birds singing together would, again, produce the 'abc' song, but the bluebird-abc song is the song of two birds: the bird 'a' and the bird 'bc' which, for simplicity's sake we will write as the 'a(bc)' song.

    Do you see the magic of the bluebird? Four birds are singing together (the bluebird and birds a, b, and c), but when the bluebird flies away, it leaves behind two birds (not three), the first is as it was, but the second bird is an entirely different bird than the other two birds that it has somehow magically replaced.

  6. Finally (best for last, as they say), the starling also sings along with three other birds, but the resulting song is quite different than the songs of the bluebird or cardinal: a starling-abc song is the song of a singing with c and that song is joined by the combined song of b singing with c, or, put simply, the starling-abc song is 'ac(bc)'.

    The starling's song is somewhat like the cardinal's song: the first bird remains, and the third bird takes second position. And its song is somewhat like the bluebird's: the second and third bird combine their song to form a new bird song, but it's also more complicated than both the cardinal's song and the bluebird's song taken alone or, for that matter, those two birds' songs combined in any way.3

A walk in the forest (two examples explained)

Example 1: the kite song...

So, now that we are acquainted with some birds, let us look at a few properties and some differences of combined bird songs. We saw above that the kestrel-ab song results in just a's song, in effect choosing a's song over b's song. We will now meet the kite. The effect of the kite's song is to choose the second bird's song. The amazing thing about this bird is that it is the result of two other birds singing: the kestrel and the identity bird.

... as a kestrel-identity bird song

Come, join me for a walk into the forest to see how this comes to be. Ah, here is a tree upon which a kestrel is perched on one of its branches! Let's wait for an identity bird to land.

While we're waiting, let me remind you that it's important that you do not whistle while you wait (nor, for that matter, "whistle while you work"), because your whistling will combine with any bird's song in the air, possibly having very strange affects on you!

Aha! I see an identity bird coming to land on the branch now, and look what is happening to to bird song in the air: it was the kestrel bird song, but now it has become the kestrel-identity bird song (or, as we have said, it has now become the kite bird song, but we will refer to this particular song as the 'kestrel-identity' bird song and see how, with two more birds joining in, that it is the same song as the kite's).

Now that the kestrel-identity bird song is in the air, let us see what happens when two more birds join in with their songs. Here comes a cardinal now: it has perched itself besides the other two birds and begun singing. But, what's this! The kestrel and the cardinal have just now flown off together; just as the effect of the kestrel song has dictated. So, now, only the identity bird remains.

So, the final bird, which happens to be a bluebird, has come to land and has begun singing with the identity bird. And, we see the identity bird fly away, leaving the bluebird happily alone to sing its song.

Example 2: the kestrel-identity bird song is a kite song

In short, the kestrel-identity-cardinal-bluebird song is the same as the bluebird song. Is the kite-cardinal-bluebird song also the bluebird song? Let's go to another tree, where a kite is singing by itself and see if this is indeed the case.

Here's a nicely-aged cypress where we can watch the birds without them observing us, and, fortunately, there is a kite singing in one of its many tangled branches. By the way, isn't it nice and cool in the shade of this cypress? I particularly like the sweet smell it imparts to the surrounding air.

Flying in to perch next to our kite is a cardinal, just as we had hoped, and it joins in singing with the kite. And, close on its wings (do birds have heels, I wonder?) comes a bluebird.

Yes, the kite and the cardinal have flown off as soon as the bluebird started singing. Leaving just the bluebird to sing its song alone. So, the kite-cardinal-bluebird song is the same as the bluebird song itself. And, more generally, the kite bird song and the kestrel-identity bird song always behave equivalently.


Puzzle 1: The identity-kestrel bird song

From the rules of bird song above, we know that the order in which birds sing is important. So, we may guess that the identity-kestrel bird song is not an equivalent song of the kestrel-identity bird song (the latter song is equivalent to the kite's song). So, puzzle 1: what (sole) bird's song is equivalent to the identity-kestrel bird song?

Exercise 1: list the four birds' songs, in their simplest representations (i.e. using the fewest number of birds possible to describe the bird song), when the following four birds fly up in order to perch on yonder apple tree branch: an identity bird, then a kestrel, then a cardinal and finally a bluebird.

  1. identity bird song (so, this first song is a freebie)

  2. identity-kestrel song:

  3. identity-kestrel-cardinal song:

  4. identity-kestrel-cardinal-bluebird song:

Puzzle 2: a kite by any other name...

We've seen that the kestrel-identity bird song is equivalent to the kite's. Here's a paradoxical puzzle: if there are no identity birds in the forest, what two birds from the birds of the other five species (which are the mockingbird, the kestrel, the cardinal, the bluebird, and the starling) when combining their bird song have an equivalent song to the kite's?

Please note! This puzzle allows for only two birds to equate the kite's song. Specifically, multiple birds from two species of birds may equate to the kite's song, but will not give the correct answer to this puzzle.


Birds of a feather ...

... may flock together, but that means very little to the bird songs produced by multiple birds of the same species.

... may produce the same song ...

But first, a counter-example: we see that one species of bird that can have any number of birds sing together and still produce the same song is the identity bird. We have seen that identity bird is fond of any bird: even of itself. We will now see that if our magical forest has only one species, the identity bird species, that the songs produced are egocentric (even hopelessly so) as well as being fond.

An egocentric bird song is a song that when combined with the song of the same species of bird produces its own bird song. So, if bird x sings an egocentric song, the bird song xx is x (whereas instead if bird x were fond of bird y, the bird song xy would be y).

A hopelessly egocentric
bird song is one that, no matter what other bird joins in the singing, it is as if the new bird were shouted down into silence.

So, back to our magical-identity-bird-only forest we see that the bird songs produced are fond (an identity-identity bird song produces the latter bird song ... which so happens to be an identity bird song), as well as egocentric (an identity-identity bird song produced the identity bird song), and even hopelessly egocentric (no matter what bird joins in the singing ... and in this particular forest, the bird joining will always be an identity bird ... the result is always the first bird who sings, which so happens, again, to be the identity bird).

All this goes to show that no matter how many identity birds sing together, the song will always be the same. This is very often not the case for other birds of the same species singing together, as we shall now see.

... but probably will produce different songs...

Let us look at a flock of kites. When two kites sing together, we get an identity bird's song! Let's see how this occurs.

We're back in the forest under that old cypress, again. The kite has returned, and it is soon joined by another kite. They sing together, and their song attracts a cardinal that lands next to them and begins to sing, too. As soon as the cardinal sings, the first kite flies off, taking the second one with it. Only the cardinal remains, singing its song. The two kites singing together is equivalent to the identity bird's song.

So, the second puzzle was called paradoxical because it is impossible for a forest not to have an identity bird when the forest has kites: when an even number of kites sing together, the bird song is inevitably an identity bird's.

In short, two kites singing together does not produce a kite's song, as one would expect, but, because of the magic of this forest, the resulting song is the identity bird's song. We have already stated this more generally: given a kite and two other birds, x and y, the bird song kite-xy is y's bird song -- or, for any x, kite-x is fond fond of any and every bird.

The one-two punch-line

The purpose of this interlude was to show that two or more birds of the same species do not necessarily produce the same song. We have also introduced two new properties (the egocentric property and the hopelessly egocentric property) that we will not use directly in these puzzles ...

But these properties are rather intriguing. So, if you'd like to pursue some experiments here are a couple of areas to explore:4

  1. Find an egocentric bird song other than the identity-identity bird song. One such song is made of three birds of two species.

  2. Find a hopelessly egocentric bird song in our magical forest that allows all the birds under discussion.5

    A hint: the kestrel is only fond of hopelessly egocentric birds.

Puzzle 3: three little birdies sitting on a tree...

Enough of that interlude! Let us return to the central theme. For this
puzzle we will be looking for birds that produce songs that give us one of three birds that land on the branch to join in the song. As an aid, you may work with the following three birds that land and begin singing in order: a starling, a mockingbird and a cardinal. But, remember: the birds you find to produce the appropriate bird song should work correctly with any set of three birds.

  1. Find a bird song that produces only the first bird's song (in this case, the starling's, or, put another way: the bird song you find combined with the song of the starling, then the mockingbird, and finally the cardinal will produce the starling's song). I found it with three birds of two species.

  2. Find a bird song that produces only the second bird's song (here, the mockingbird's). I found two such songs, each song had two birds.

  3. Find a bird song that produces only the third bird's song (the cardinal's). I found a song with two species of birds.

Puzzle 4: Four calling birds

Now you have the ability, given a pair of birds, to find the first or the last (second) bird of that pair (using the kestrel and the kite), or, given three birds, to find the first, second or last bird (using the ... oops! you found that out yourself, anyway, so there's no need for me to tell you). Let us take those mad-skilz (yo!) of yours to single out birds in a quartet.

In keeping with the quartet theme, and to add a modicum of confusion by mixing metaphors, the four birds that fly up to join in the bird songs you discover are, in order, suprano, alto, tenor, and bass. We may not know what affect these birds' songs have, but I must say, they do make lovely music, indeed!

  1. Find a bird song that results in the suprano singing an aria -- perhaps "The Spring" by Sir Theopholus Pinkum?

  2. It's a rare thing indeed, but, what is a song that has the alto singing a solo?

    I suppose there's always a solo for the contralto in a Gilbert&Sullivan vehicle. And, as the word 'alto' is viewed with some scorn in that community, such singers often refer to themselves as 'mezzo-suprano' ... an interesting euphamism, that: Mahler's Second Symphony has about two seconds where the alto mezzo-suprano sings unaccompanied by the suprano.

  3. It is an unfortunate happenstance that there are an overabundance of tenor solos (in fact, one such album containing a plethora of such showtunes sung by three such tenors come to mind as I write this section) that we must be forced to sit through maintaining a façade of rapt admiration and attention. Please find a bird song that furthers this entrenchment.

  4. The bassist ... unless we mean bassist as in the player of that big-ole violin in the jazz ensemble ... suffers much of same fate as the 'alto' soloist (and, according to Peter Schickele, also known as P.D.Q. Bach, the bassist in a jazz ensemble should suffer that fate): the only two songs in the repetoire must be "Old Man River" and "Thus Says the Lord" (and I don't think Handel was thinking about the Mississippi when he composed the Messiah ...): let's give the poor guy a helping hand, shall we? What is a bird song that allows our bass bird to sing his heart out uninterrupted? (Remember: bass is not spelt: 'H-A-M').



Opening strongly inspired by [S85]: the introduction to chapter 9.


This property of two birds songs combined to produce the second's bird song is called fondness. The indentity bird is fond of any and every bird; other birds, that do not equate to the identity bird, may have a fondness to one or a few birds, but not all birds -- the identity bird is special in this regard.


Even more significantly: a starling cannot be produced from any combination of the bluebird, cardinal and identity bird. So, there are some (other) magical forests that contain only bluebirds, cardinals, identity birds and starlings.


[S85], chapter 11, §3 and §4


I would be flattered if you arrive at the same bird that I did, but you may find the meditations on the subject amusing, rather convoluted, or, dare I write, hopelessly egocentric. Besides, the previous endnote shows a much more straightforward way of finding a hopelessly egocentric bird song.

Works consulted

[S85]To Mock a Mockingbird and other logic puzzles including an amazing adventure in combinatory logic, by Raymond Smullyan, Alfred A. Knopf (pub), New York, 1985.

Copyright © 2005, Cotillion Group, Inc. All rights reserved.
Author: Douglas M. Auclair (