post

09 December

Share on FacebookTweet about this on TwitterShare on Reddit

Binary Magic Card Trick

Ah, the Christmas holidays. A time to be spent hiding from the cold, wearing pyjamas, eating too much food and solving integro-differential equations. (At least that’s how I think everyone spends Christmas, right?) Come Christmas Day, after you’ve finally cracked Chalkdust Issue 4’s Crossnumber and stuffed your face with turkey, why don’t you stun your (slightly drunk) family and friends with a very simple math-based magic trick?

The Trick

This trick follows a fairly standard magic setup: you are going to successfully guess (telepathically, of course) a number decided in secret by the unsuspecting watcher. Hand your target a set of cards with numbers on (an example set of cards can be seen below):

Tell them to think of a number in between the smallest and largest number present on the cards (in our case, between 1 and 63). Then ask they hand you every single card with that number on it. Add up the first number on each of the cards given to you, et voilà, you’ve ‘magically’ obtained their number.

Why does it work?

Afterwards, you’ll be asked how it works. Spend a good bit of time insisting you’re in touch with the Other Side, were recently struck by lightning and can now hear other peoples’ thoughts, or are simply VERY good at guessing. But since, as mathematicians, we need to try and convince people maths is interesting and, more importantly, not a form of witchcraft, consider explaining to them how it works (I’ve found talking over the television during the Christmas edition of Eastenders particularly effective). 

Those of you with a keen eye will have clocked it already. Certainly, a big hint is that the first number on each card is a power of 2. The cards have been designed such that each combination of cards uniquely represents a number in binary.

Binary

For those of you who are not sure what binary is, it is the base two numeral system. You will certainly be familiar with the base ten numeral system since that’s how we normally represent numbers. A good explanation on base systems can be found here.

As an example, we can represent forty-seven in binary and base-ten as

\begin{eqnarray}
\text{forty seven} &=& 4 \times 10^1 + 7 \times 10^0 \\
&=& 47 \,\,\,\, (\text{base ten}) \\
&=& 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 \\
&=& 101111 \,\,\,\, (\text{base two})
\end{eqnarray}

So, let us re-order and label the cards as follows

Card $N$ is characterised as containing all the numbers which contain a “$1 \times$” in front of the term $2^N$. Taking our example 47 (base ten), we see that 47 appears on cards [0,1,2,3,5]. That is the say


\begin{eqnarray}
47 \,\,\, \text{(base 10)} &=& 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 \\
&=& 101111 (\text{base two})
\end{eqnarray}

Ensuring that card $N$ has $2^N$ as the first number on the card (for your ease of reference), simply adding all the first digits on the cards handed back to you will give the correct answer. 

We chose 63 as it is of the form $2^6 – 1$. It is best advised to choose a number of the form $2^M -1$ as your maximum number as it ensures each card has $M/2$ digits on it, raising the least suspicion. 

Share on FacebookTweet about this on TwitterShare on Reddit
post

Killing by numbers: the mathematics of warfare

Share on FacebookTweet about this on TwitterShare on Reddit

Greece:  Leuctra (371 BC)

The city-states of Greece have constantly fought for supremacy in the region. A brief period of peace has come to an end, as the currently dominant Sparta has openly challenged the city of Thebes’ political position. For refusing to abolish the Boeotian Confederacy, a political union of city-states which Thebes heads, Sparta has declared war. The city of Thebes and her allies have amassed 7,200 foot-soldiers (called hoplites) and, lead by Epaminondas, they look over the fields of Leuctra, where entrenched in their camp rest 9,600 Spartan hoplites.

Continue reading

Share on FacebookTweet about this on TwitterShare on Reddit
post

A counterintuitive result in the theory of traffic flow

Share on FacebookTweet about this on TwitterShare on Reddit

Traffic presents a nightmare for city planners. As well as being a pain for commuters, the environmental, financial and social cost of traffic is huge. Cities are still plagued with traffic jams, with rush ‘hour’ being a far too kind a name for the three hour period during which many of the roads are gridlocked. A possible solution to seemingly never ending traffic jams is to add additional infrastructure, but is this always the best solution? Consider the following (made up) scenario.

Banner1The school run

Every weekday, 8am sharp, 40 people drive their children from Aelston (A) to Deephurst (D). As things stand, there are two possible routes, going north via Byfair (B) or south via Churchgate (C). The roads connecting AB and CD have lots of lights and a slow speed limit, fixing the flux of traffic, with both roads taking 27 minutes to traverse. The roads connecting BD and AC have no traffic lights but are more prone to jams, taking 5 minutes to travel, plus half a minute for every other car using the road.

The local council, keen to win votes for the upcoming election, have tarmacked the local green space and built a new multilane motorway connecting BC. This 4-lane monstrosity is very fast and only takes 2 minutes to traverse. To the council’s dismay, the travel time for the school run has increased for everyone! Disgruntled and embarrassed, the council have brought in a mathematician to explain what has happened.

Networks and Braess’ paradox

When considering how to present the information above, one might quite naturally draw a network (often called a graph). We represent the areas A to D as ‘nodes’ and the roads as ‘edges’. We assign ‘weights’ to each road, the value being the number of minutes it takes to go from one end of the road to the other. Allowing the edges to have directions, we obtain the following graphs for the pre and post-motorway systems:

Traffic assignment before building the road

Traffic assignment before building the road

Traffic assignment after building the road

Traffic assignment after building the road

where T represents the number of cars on the road.

Now for both systems, we shall seek the user-optimised configuration. This models the selfish nature of individuals using the network. Every driver will, if possible, change their route to the quickest path,
without concern whether the change will slow down everyone else’s journey. This is in contrast with the system-optimised configuration: the routes are assigned by someone who determines the optimal way to minimise the amount of time cars are collectively on the road.

Before the motorway was constructed, it is clear that the user-optimised configuration is to have 20 cars take ABD and 20 take ACD. In this case:

\begin{equation}
\lvert ABD \rvert = \lvert ACD \rvert = 5 + \frac{20}{2} + 27 = 42 ,
\end{equation}
where $\lvert – \rvert$ represents the time taken to complete the route $-$.

After the motorway was constructed, people taking the southern route noticed that avoiding CD would at worst take the same amount of time as going via CBD. This is because T satisfies $T\leq 40$, and hence

\begin{equation*}
\lvert CBD \rvert = 2 + 5 + \frac{T}{2} \leq 27 = \lvert CD \rvert .\\
\end{equation*}
The drivers initially taking the northern route also noticed that the slow road AB could be avoided in a similar manner:

\begin{equation*}
\lvert ACB \rvert = 2 + 5 + \frac{T}{2} \leq 27 = \lvert AB \rvert .\\
\end{equation*}
Hence, no matter what the other 39 cars are doing, it is always beneficial for the selfish driver to take the route ACBD. But, since all the drivers think the same thing, these roads are more congested than before, and the new travel time is
\begin{equation*}
\lvert ACBD \rvert = 5+\frac{40}{2} +2+5+\frac{40}{2} = 52,
\end{equation*}
10 minutes slower than before! However, no driver is willing to change, since any other route in this network with such a configuration is slower! Only if all the drivers cooperate, and agree to resist the temptation of avoiding the slow roads, can the previous system-optimised configuration be achieved. Hence, we see that in user-optimised networks, improved connectivity between two points does not imply a more efficient system. This phenomenon in networks was first demonstrated by Dietrich Braess in 1968, and is aptly named “Braess’ paradox”.

Concluding remarks

In our model, before the new motorway, there were two balanced options. The addition of the motorway then created a new preferable route, with the negative result that all traffic chose to take it, causing congestion. Although this model may seem far from realistically modelling roads, it demonstrates that networks can have this characteristic. Braess’ paradox is seriously discussed in traffic flow literature, and real life examples of this phenomenon are documented. In New York, there were reports of improved traffic when 42nd Street was shut for Earth Day in 1990. In Seoul, South Korea, the government went as far as demolishing a highway near the centre of the city to avoid the road being overused.

seoul2

Picture of Seoul before and after the destruction of the freeway.

This result is a nice example of how our intuition can be tricked.

Share on FacebookTweet about this on TwitterShare on Reddit