Ian Short

Here are some problems I developed for NRICH on disconnecting sets of points.

Introduction

There is an island, shown below, which contains five towns, each marked by a coloured disc. The people from the red towns are arch rivals with the people from the blue towns, so they decide to build a wall to separate all the red towns from all the blue towns. The red towns want to stay in contact with each other so the wall must not separate two red towns. Likewise the wall must not separate blue towns. The wall must be continuous, it must not intersect itself, it must not split, and each end of the wall must be at a point on the coast. Let us call such a wall a dividing wall.

Is it possible to construct a dividing wall? Yes, one is shown below.

If you manage the above example, then perhaps you can answer the following question. Given any configuration of red and blue towns, is it always possible to build a dividing wall?

Coastal towns

The next island (below) has coastal towns. These towns differ from all previous towns as you cannot encircle each one with a wall. Can you separate the red and blue towns with a wall in this example?

Have you managed it? If not then persevere; it is possible! Try the next example.

If you cannot build a suitable wall for the previous example then try to answer the following question. What is the simplest configuration of towns, both coastal and inland, for which you cannot build a dividing wall?

Once you have answered that question you may try this harder question. Can you characterise those configurations of towns for which it is possible to build a dividing wall?

Building roads

History is littered with examples of dividing walls that have contributed to war and misery. Let us suppose that the people from our five original towns are more enlightened, although retain their animosity towards each other. Rather than building a wall, they decide to build two roads. One road connects all the blue towns, and the other road connects all the red towns. The two roads are not allowed to intersect themselves, or each other. The blue road starts at a blue town, and then passes through each of the other blue towns, finishing at a blue town. Likewise for the red road and the red towns. Let us call a pair of such roads connecting roads. An example of a pair of connecting roads is shown below.

Here is a pair of connecting roads for the first coastal town example.

Are the problems of building a dividing wall, and building a pair of connecting roads, related?

More towns

Recent immigrants to the island have set up their own green town. The unfriendly locals quickly found reason to dislike them, and now the dividing wall must separate red towns, blue towns, and green towns.

It is impossible to separate all three sets of towns with one dividing wall. We need another! The rules for two dividing walls are that they must not intersect each other, and each end of each wall must start either from a point on the coast, or from a point on one of the other walls. We can separate red from green from blue with two dividing walls, as shown below.

We can bring in green coastal towns too, and address the next question. Which configurations of red, green, and blue towns can be separated by two dividing walls?

Questions and answers

Questions. Does the shape of the island affect the problem? How about if we introduce lakes to the island, across which neither walls nor roads can be built? We can allow more roads and walls. Does that actually help? We can introduce more towns too. Also, we can assume that the island is a sphere, rather than a disc shape. (That is, we can ask the same questions for people on the whole Earth.) Or we can assume that the people live on a torus. Unlikely, but don’t let that hold us back. We could consider multiple islands, and build bridges between them.

Answers. I haven’t worked out all the answers! The shape of the island doesn’t matter, so we may as well assume it is a disc. Lakes have no impact; we can shrink them down to points without affecting the problem. For two colour types, if there are no coastal towns then a dividing wall exists. If there are coastal towns then a dividing wall exists unless there are four coastal towns that occur in the order red, blue, red, blue, clockwise around the island. Connecting roads are the same as dividing walls. The reasons are similar, if not exactly the same as, the idea in metric space theory of equivalence of path connectivity and connectivity. I don’t imagine that extra walls would help with the two coloured towns problem. For n colour types, and n-1 dividing walls, I suspect that for successful configurations, same coloured towns must be grouped together round the coast.

Yesterday it snowed and I made an arch from the snow.

Some local kids helped for a while, before attacking me with snowballs. Later on that evening, after a long patient wait with Ellie’s camera, I caught the perfect shot.

A unique moment. The following day some more local kids – possibly the same ones – arrived with a broom and destroyed the arch. They fought with the broom in my front garden for five minutes, and then left, forgetting the broom.

For more on wolves, see all about Wolves.

Introduction

Last week E asked me about some biological data which could be modelled by an exponential curve, similar to the one shown below. It is the graph of a function such as f(x) = kexp(-sx), for positive constants k and s.

Ellie had another version of this graph, shown below.

I immediately thought that this was the graph of log f, rather than f, and that the intercept with the vertical axis should be at log k, rather than k. However, E said that this graph was a semi-log graph, and I later realised what she meant by this, and that the intercept with the vertical axis should indeed be k rather than log k.

To give you an idea of what a semi-log graph is, here is an example of such a graph, with the axes labels carefully marked. This semi-log graph uses log to base 10, rather than log to base e.

On the vertical axis, the label b occurs where the label log b would usually occur. The horizontal axis remains as usual. Hence the phrase semi-log. Adjusting the scale of the vertical axis affects the graph (and likewise for the horizontal axis). A question presents itself: how much freedom do we have in changing the shape of a graph by adjusting the horizontal and vertical axes? I thought this question might lead to a source of problems for NRICH.

Examples

From now on, for simplicity, we restrict attention to maps that fix 0. In the next diagram, the graph of the function f(x)=x is altered by a change in the vertical axis scale.

We are allowed to expand and contract the vertical axis scale as we wish, but the ordering of the axis labels must remain the same if the graph is to be of any use at all. With this freedom, f(x)=x can be transformed to g(x)=x³ and h(x)=e^x-1. It is impossible to create from f(x)=x a graph with a stationary point though, as indicated in the next diagram.

The reason for this will be explained later. Likewise the two graphs in the next diagram cannot be transformed from one to the other.

The left hand graph has a maximum, followed by a minimum, and then another maximum. The right hand graph has a maximum, followed by a minimum, and then a saddle point. That means these two graphs are inequivalent. Here is another set of examples.

Graph A is not equivalent to graph B because the first maximum of A is larger than the second maximum of A, whereas the first maximum of B is smaller than the second maximum of B. Graph A is not equivalent to graph C because graph C has a whole interval of stationary points. Graph A is not equivalent to graph D because graph D has five stationary points, whereas graph A has only three. Graph A is equivalent to graph E: they both have three stationary points, and each function takes its maximum value at the first stationary point, and its minimum value at the second stationary point. Graph A is not equivalent to graph F because graph F has five stationary points. Graph F is not equivalent to graph D because the ordering of the values of the functions at the stationary points differ. In fact, of the six graphs, only graphs A and E are equivalent.

In the next two sections we study our problem formally.

Graph equivalence

In this formal explanation we restrict attention to the class U of continuously differentiable real functions which map [0,∞) to itself, and which fix the point 0. In this class we can explain the key ideas, and it is easy to generalise to include all the functions shown above.

The graph G(f) of an element of U is the set {(x,f(x)) : x>0}. The semi-log graph of f is the graph G(log f), but with the label b on the vertical axis replaced with exp b. However, log f is not a member of U, so we introduce another class V consisting of strictly increasing continuously differentiable maps of [0,∞) onto itself. Contracting and expanding the vertical axis of the graph of f is equivalent to replacing G(f) with G(gf), where g is a member of V. Likewise, contracting and expanding the horizontal axis of f is equivalent to replacing G(f) with G(fh), where, again, h is a member of V. We ignore issues about labelling of the horizontal and vertical axes as they are a distraction. Let us say that two elements f₁ and f₂ of U are equivalent if there exist maps g and h in V such that f₂= gf₁h. This is an equivalence relation on U. The question from the end of the first section becomes:

what are the equivalence classes of U?

Or, in other words:

given maps f₁ and f₂ in U, do there exist maps g and h in V such that f₂ = gf₁h?

Stationary points

Suppose that f₁ and f₂ are equivalent elements in U, with f₂ = gf₁h. What common features do they have? Suppose that f₁‘(x)=0. Then, by the chain-rule, f₂‘(x)=0 also. This means that f₁ and f₂ must have the same number of critical points. For simplicity, let us restrict to the subset W of U consisting of those elements f of U which have finitely many critical points, and are such that if a and b are critical points of f, then f(a) and f(b) are distinct.

Let f have critical points p₁ < p₂ < … < p_n, and let q₁, q₂,…,q_n be the corresponding critical values (so that q_i=f(p_i)). Let γ denote the unique permutation from S_n such that q_γ(1) < q_γ(2) < … < q_γ(n). We describe γ as the permutation associated to f. The following theorem characterises equivalence in terms of permutations.

Theorem.Two elements of W are equivalent if and only if their associated permutations are equal.

Sketch proof. Suppose first that f₁ and f₂ are equivalent elements in U, which means that there are maps g and h in V such that f₂ = gf₁h^-1. Let p₁ < p₂ < … < p_n be the critical points of f₁, and let γ be the permutation associated to f. Then the critical points of f₂ are h(p₁) < h(p₂) < … < h(p_n), and the critical values are f₂h(p_i) for i=1,2,…,n. However, f₂h = gf₁, which means that the critical values of f₂ are gf₁(p_i) for i=1,2,…,n. Since g preserves order, the permutation associated to f₂ is also γ.

Conversely, if the permutations associated to f₁ and f₂ are equal then, after applying preliminary transformations on the left and right, we can assume that they have identical critical points and critical values. That is, we can assume that f₁ and f₂ both have critical points p₁ < p₂ < … < p_n, and critical values q₁, q₂,…,q_n. To finish the proof, define p₀=0, p_n+1=∞, and define h to be the element of U that is equal to f₂^-1f₁ when restricted to the interval [p_i-1,p_i], for i=1,2,…,n+1. Then f₂h = f₁, and this completes the proof.

There is a similar (but slightly more complicated) theorem for U rather than W.

Ecosia is a search engine that donates 80% of the advertising revenue it makes to the WWF. The money goes towards rainforest preservation. The search engine is powered by Yahoo! and bing, and it joins a number of emerging search engines with an environemtnal bias. Ecosia claim that their servers are powered by energy sources with minimal environmental impact.

The Wave was an event organised by the Stop Climate Chaos Coalition in London on 5 December 2009. The Stop Climate Chaos coalition comprises the WWF, the RSPB, Friends of the Earth, Greenpeace, Oxfam, and many other charitable bodies. The Wave was held before the environmental summit in Copenhagen.

Approximately fifty thoursand people attended the march. The last similar large event I participated in (in London) was before the recent Iraq war, and between one and two million people were present then. It’s a shame that this more important event received far fewer people. Read this description of why combating climate change is so important.

During the march a guy handed MC an object which said on it “pass it on!”. The object consisted of two short cuboids of wood with a hinge joining them together. When the two pieces of wood were opened up, there was a short article inside with some information about climate chaos; I’m not sure what exactly. The words “pass it on!” were written in white paint on top of the closed contraption, on the wood. The guy said to MC, “here, pass this on.” MC refused it. So the guy said, “okay, just hold it whilst I send this text message” (he was typing away on his mobile phone). MC still refused it. The guy moved away and gave the wood thing to someone else. Then a woman came along and said to the person carrying the wood, “shall I take that from you?” She did so, and then they all drifted off.

What was going on? Seemed like a peculiar scam.

Before eating fish, check out the guidelines laid out by the Marine Conservation Society. Only buy and eat fish that are MCS approved. (That includes cat and dog food. I was annoyed to notice the other day that I had been buying cat food containing fish. They’ll be getting rabbit and chicken from now on, plus all the other crap – mostly not meat – that goes into cat food.)

I only learnt about the grim future of fish last night when Ellie and I attended a screening of the film The End of the Line in Chester Zoo. The film’s director Rupert Murray was present to discuss the film and answer questions. The film’s message is that the massive fishing industry is anihilating the world’s fish population, beyond repair. At current rates of fishing there will essentially be no edible sea creatures by half way through this century. I say edible, because there will probably be loads of jellyfish, algae, etc, to take the place of the fish.

Much I learnt of fish consumption surprised me. For example, in many ways eating farmed fish is worse than eating fish from the sea. The farmed fish are fed on sea fish, and significantly more fish (in weight) are needed to feed the farmed fish than the farmed fish themselves. Of course, how bad this situation is depends on the particular fish in question.

The film also described the massively endangered bluefin tuna, and the Japanese company, Mitsubishi, who are behind most of the catching of this fish. Don’t eat it. It will soon be exctinct. Would you eat a panda?

There was discussion of existing fishing quotas that remind me of carbon dioxide emissions quotas. Rich European countries are bound by regulations, albeit weak regulations (which they ignore anyway), to limit the number of fish they catch. They are allowed to buy rights to fish from other (poorer) countries. The film showed massive European trawlers clearing out all the fish from a local fishing village in Senegal, after a rich European country (I don’t know which) had bought some of Senegal’s fishing quota. The local Senegalese people couldn’t make any money, so they had to leave. They will come to England and we will complain that they are taking our jobs!

What can you do? First, only buy MSC approved fish. Second, check out this booklet for information on less endangered fish. Third, use this guide to learn of fish friendly restaurants. The website is run by Charles Clover, the author of the book The End of the Line on which the film is based. Fourth, watch the film. Fifth, read the book.