Königsberg Bridges


The great Swiss mathematician Leonhard Euler, who had been asked by the Mayor of Danzig to provide a solution to the Königsberg Bridge problem, sent him this disdainful reply:

“. . .  Thus you see, most noble Sir, how this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.  Because of this, I do not know why even questions which bear so little relationship to mathematics are solved more quickly by mathematicians than by others.”

However in the same year he wrote this, in a letter to the Italian mathematician and engineer, Giovanni Marinoni.

“This question is so banal, but seemed to me worthy of attention in that [neither] geometry, nor algebra, nor even the art of counting was sufficient to solve it.”

On August 26, 1735, Euler presented a paper containing the solution to the Königsberg bridge problem, in which he addresses both the specific problem, and gives a general solution with any number of land masses and any number of bridges.  This paper, titled  ‘Solutio problematis ad geometriam situs pertinentis,’ was  published later in 1741. What follows is a verbatim version of an edited version of this paper translated by James R.Newman, that appeared  in my 1978 set of reprints from Scientific American entitled, ‘Mathematics: An Introduction to its Spirit and Use’. I have just reinstated the paragraph numbering from the original paper.

Euler’s Paper

1. The branch of geometry that deals with magnitudes has been zealously studied throughout the past, but there is another branch that was then almost unknown up to now; Leibnitz spoke of this first, calling it the “geometry of position” (geometry situs). This branch of geometry deals with relations dependent on position alone, and investigates the properties of position; it does not take magnitude into consideration, nor does it involve calculation with quantities. But as yet no satisfactory definition has been given of the problems that belong to this geometry of position or of the method to be used in solving them. Recently there was announced a problem which, whilst it certainly seemed to belong to geometry, was nevertheless so designed that it did not call for the determination of a magnitude, nor could it be solved by quantitative calculation, consequently I did not hesitate to assign it to the geometry of position, especially since the solution required only the consideration of position, calculation being of no use. In this paper I shall give an account of the method that I discovered for solving this type of problem, which may serve as an example of the geometry of position.

2. The problem, which I understand is quite well known, is stated as follows: In the town of Königsberg in Prussia there is an island A called Kneiphof, with two branches of the river Pregel flowing round it. There are seven bridges a, b, c, d, e, f and g crossing the two branches of the river. The question is whether a person can plan a walk in such a way that he will cross  each of these bridges once but not more than once. I was told that while some denied the possibility of doing this and others were in doubt, no one maintained that it was actually possible. On the basis of the above I formulated the following very general problem for myself: Given any configuration of the river and branches into which it may divide, as well as any number of bridges, to determine whether or not it is possible to cross each bridge exactly once.

3. The particular problem of the seven bridges of Königsberg could be solved by carefully tabulating all possible paths, thereby ascertaining by inspection which of them, if any, met the requirement. This method of solution, however, is too tedious and too difficult because of the large number of possible combinations, and in other problems where many bridges are involved it could not be used at all. Hence I discarded it and searched for another more restricted in its scope; namely, a method which would show only whether a journey satisfying the prescribed condition could in the first instance be discovered;  such an approach, I believed, would be simpler.


4. My entire method rests on the the appropriate and convenient way in which I denote the crossing of bridges, in that I use capital letters A, B, C, D, to designate the various areas of land that are separated from one another by the river. Thus when a person passes from area A to area B, using either of the two possible bridges a or b, I denote this by the letters AB, the first of which denotes the area whence he came and the second the area where he arrives after crossing the bridge. If the traveller then crosses from B over bridge f into D, this crossing is denoted by the letters BD; the two crossings AB and BD performed in succession I denotes simply by the three letters ABD, since the middle letter B designates the area into which the first crossing leads as well as the area out of which the second leads.

5. Similarly, if the traveller proceeds from D across bridge g into C, I designate the three successive crossings by the four letters ABDC. The crossing of four bridges will be represented by five letters and if the traveller crosses an arbitrary number of bridges his journey will be described by a number of letters that is one greater than the number of bridges. For example, eight letters are needed to denote the crossing of seven bridges.

6. With this method I pay no attention to which bridges are used; if the crossing from one area to another can be made by one of several bridges it makes no difference which is used, so long as it leads to the desired area. Thus if a route could be laid out over the seven Königsberg bridges so that each bridge was only crossed once and only once, it would be possible to describe this route using eight letters, and in this series of letters AB (or BA) would have to occur twice since there are two bridges (a and b) connecting the areas A and B. Similarly the combination AC would occur twice and the combinations AD, BD and CD would each occur once.

7. Our question is now reduced to whether from the four letters A, B, C and D a series of eight letters can be formed in which all the combinations just mentioned occur the required number of times. Before making the effort, however, I think it well to consider whether its existence is even theoretically possible or not. For if it could be shown that such an arrangement is in fact impossible, then the effort expended on trying to find it would be wasted. Therefore I have sought for a rule that would determine without difficulty, as regards this and similar questions, whether the required arrangement of letters is feasible.

EulerOneRegion8. For the purposes of finding such a rule I take a single region A into which an arbitrary number of bridges a, b, c, d, etc. lead. Of these bridges I first consider only a. If the traveller crosses this bridge, he must either first have been in A before crossing or have reached A after crossing, so that according to the above method of denotation the letter A will appear exactly once. If there are three bridges leading to A and the traveller crosses all three, the letter A will occur twice in the expression representing his journey, whether it begins at A or not. And if there are five bridges leading to A, the expression for a route that crosses them all will contain the letter A three times. If the number of bridges is odd, increase it by one, and take half the sum; the quotient (the answer) represents the number of times the letter A appears.

9. Let us now return to the Königsberg problem. Since there are five bridges leading to (and from) island A, the letter A must occur three times in the expression describing the route. The letter B must occur twice, since  three bridges lead to B; similarly D and C must both occur twice. That is to say, the series of letters that represents the crossing of the seven bridges must contain A three times and B, C, and D  each twice. But this is quite impossible with a series of eight letters, for the sum of the required letters is nine ( 3 + 2 + 2 + 2 = 9). Thus it is apparent that a crossing of the seven bridges in the manner required cannot be effected.

10. Using this method we are always able, whenever the number of bridges leading to a particular region is odd, to determine whether it is possible in a journey to cross each bridge exactly once. Such a route exists if the number of bridges plus one is equal to the sum of the numbers which indicate how often each individual letter must occur. On the other hand if this sum is greater than the number of bridges plus one, as it is in our example, then the desired route cannot be constructed. The rule that I give for determining from the number of bridges that lead to A how often the letter A will occur in the route description is independent of  whether these bridges all come from a single region B or from several regions, because I was considering only the region A, and attempting to determine how often the letter A must occur.

11. When the number of bridges leading to A is even, we must take into account whether the route begins in A or not. For example, if there are two bridges that lead to A and the route starts from A, then the letter A will occur twice; once to indicate departure from A by one of the bridges and a second time to indicate the return to A by the other bridge. However, if the traveller starts his journey in another region, the letter A will only occur once, since by my method of description the single occurrence of A indicates an entrance into as well as a departure from A.

12. Suppose, as in our case, there are four bridges leading into the region A, and the route is to begin at A. The letter A will then occur three times in the expression for the whole route, while if the journey had started in another region, A would only occur twice. With six bridges leading to A, the letter A will occur four times if A is the starting point, otherwise only three times. In general, if the number of bridges is even, the number of occurrences of the letter A, when the starting region is not A, will be half the number of bridges; when the route starts from A, one more than half.

13. Every route must, of course, start in some one region. Thus from the number of bridges that lead to each region I determine the number of times that the corresponding letter will occur in the expression describing the whole route as follows: When the number of bridges is odd, I increase it by one and divide by two; when the number is even I simply divide it by two. Then if the sum of the resulting numbers is equal to the number of bridges plus one, the journey can be accomplished, though it must start in a region approached by an odd number of bridges. But if the sum is one less than the number of bridges plus one, the journey is feasible if its starting point is approached from a region with an even number of bridges, for in that case the sum is again increased by one.

14. My procedure for determining whether in any system of rivers and bridges it is possible to cross each bridge exactly once is as follows: First I designate the individual regions separated from one another by water A, B, C, etc. Second, I take the total number of bridges, increases it by one, and write the resulting number at the top of the page. Third, under this number I write the letters A, B, C, etc. in a column, and opposite each letter note the number of bridges that lead to that particular region. Fourth, I place an asterisk again each letter that has an even number next to it. Fifth, in a third column I write opposite each even number half of that number and opposite each odd number half the sum formed by that number plus one. Sixth, I add up the last column of numbers. If the sum is one less or equal to the number at the top, I conclude that the  required journey can be made. But it must be noted that when the sum is one less than the number at the top, the route must start from a region marked with an asterisk, and when the two numbers are equal, it must start from a region that does not have an asterisk.

For the Königsberg problem, I would set up the tabulation as follows:


The last column now adds up to more than 8, and hence the required journey cannot be made.

15. Let us take an example of two islands with four rivers forming the surrounding water.


Fifteen bridges marked a, b, c, d, etc. cross the water round the two islands and the adjoining rivers. The question is whether a journey can be arranged that will pass over all the bridges , but not over any more than once. I begin by marking the regions that are separated from one another by water with the letters A, B, C, D, E and F, there are six of them. Second, I take the number of bridges (15) add one and write the number (16) uppermost. Third, I write the letters A, B, C, etc in a column and opposite each letter write the number of bridges connecting with that region, e.g. eight bridges for A, four for B, etc. Fourth, the letters that have even numbers against them are marked with an asterisk. Fifth, in a third column I write the half of each corresponding number, or if the number is odd, I add one to it, and put down half the sum. Sixth, I add the numbers in the third column and gets 16 as the sum.


The sum of the third column is the same as the number 16 that appears above, and it follows that the journey can be effected if it begins in regions D or E, whose symbols have no asterisks. The following expression represents such a route:


Here I have indicated, by small letters between the capitals, which bridges are crossed.

16. By this method we can easily determine, even in cases of considerable complexity, whether a single crossing of each bridge in sequence is possible. But I should now like to give another and much simpler method which follows quite easily from the preceding, after a few preliminary remarks. In the first place I note that the sum of the numbers written down in the second column is necessarily double the actual number of bridges. The reason is that in the tabulation of the bridges leading to the various regions each bridge is counted twice, once for each of the two  regions that it connects.

17. From this observation it follows that the sum of the numbers in the second column must be an even number, since half of it represents the actual number of bridges. Hence, if any of the numbers opposite the letters A, B, C, etc. are odd an even number of them must be odd. In the Königsberg problem for instance, all four of the numbers opposite the letters A, B, C, D, were odd, while in the example just given only two of the numbers were odd, namely those opposite D and E.

18. Since the sum of the numbers opposite A, B, C, etc. is double the number of bridges, it is clear that if this sum is increased by two in the latter example and then divided by two, the result will be the number written at the top. When all the numbers in the second column are even, and half of each is written down in the third column, the total of this column will be one less than the number at the top. In that case it will always be possible to cross all the bridges. For in whatever region the journey begins, there will be an even number of bridges leading to it, which is the requirement.

19. Further, when only two of the numbers opposite the letters are odd, and the others even, the required route is possible provided it begins in a region approached by an odd number of bridges. We take half of each even number, and likewise half of each odd number after adding one, as our procedure requires: the sum of these halves will then be one greater than the number of bridges, and hence equal to the number written at the top. But, when more than two of the numbers in the second column are odd, it is evident that the sum of the numbers in the third column will be greater than the top number and hence the desired journey is impossible.

20. Thus for any configuration that may arise the easiest way of determining whether a single crossing of all the bridges is possible is to apply the following rules:

If there are more than two regions which are approached by an odd number of bridges, no route satisfying the required conditions can be found.

If, however, there are only two regions with an odd number of approach bridges the required journey can be completed provided it originates in one of these regions.

If, finally, there is no region with an odd number of approach bridges, the required journey can be effected, no matter where it begins.

These rules solve completely the problem initially proposed.

21. After having determined that a route actually exists we are left with the question of how to find it. To this end the following rule will serve: Wherever possible we mentally eliminate any two bridges that connect the same two regions; this usually reduces the number of bridges considerably. Then, and this should not be too difficult, we proceed to trace the required route across the remaining bridges. The pattern of this route, once found, will not be substantially affected by the restoration of the bridges which were first eliminated from consideration, as a little thought will show. Therefore I do not think  I need say no more about finding the routes themselves.


After overcoming his initial reluctance to solve such a banal problem, in Section 1, Euler relates the problem to an emerging area of mathematical enquiry, the geometry of position. In Section 2, he states the problem clearly and labels the island Kneiphof A and the bridges  a, b, c, d, e, f and g. In Section 3, although Euler recognises that the problem could be solved by enumerating all routes, he rejects this method as being too tedious, too difficult and not capable of being extended.

In Sections 4, 5 and 6, Euler establishes his method of notation, labelling the separate  land areas A, B, C,  and D, and paths or journeys, from one area to another, as strings of these letters ABDC etc. paying no attention to which bridge might be used to get from one area to another. He then notes that with his notation, to represent the crossing of the seven bridges needs a string of eight letters, and that the combination AB or (BA) would need to appear twice as would the combination AC (each with two bridges), whilst the combinations AD, BD and CD would each appear once (each with only one bridge).

In Section 7, Euler notes that the problem is now reduced to whether from the four letters, A, B, C, and D a series of eight letters can be formed in which all the combinations just mentioned can occur. But before wasting effort on looking for possible arrangement he wishes to see if he can find a simple rule that says whether any arrangement is possible. In Section 8, he imagines a single area A into which an arbitrary number of bridges a, b, c, d, etc. lead. He first considers only bridge a, and notes that if the traveller crosses this bridge he must either have come from A or arrived in A and therefore the letter A will appear exactly once. If there are three bridges leading to A the letter A will appear twice and if there are five bridges it will appear three times.

So the problem as stated requires that there are only eight letters in the string representing the required route, but also requires that A appears three times and B, C, and D each appear twice, a total of nine times ( 3 + (3 x 2) = 9). The requirements are contradictory and therefore no route is possible.

Having solved the presented problem, Euler then proceeds to generalise his method and provides a step by step algorithm for solving problems with any number of islands and any number of bridges. But Euler is still not satisfied and proceeds to produce a yet simpler set of three rules that determine in any situation, if all bridges can be crossed once without any being crossed twice.

Planar Graphs

Whilst Euler’s paper is widely recognised as the origin of Graph Theory, it is interesting to note that it does not actually contain anything that looks like a graph, its major contribution being the notation adopted. By long custom, in Euclidean Geometry capital letters, A, B, C etc. denote points, and lowercase letters, a, b, c etc. edges. Euler uses capital letters to represent areas and lowercase letters to represent bridges (the connections between areas). This facilitates the idea that areas can be represented by points and connections by edges. So that the Königsberg Bridges problem can be represented graphically as follows:-


With graphs like this, one can easily count the number of nodes that have an odd number of edges entering them, marked red above. If there are more than 2 nodes with an odd number of edges then no route is possible, but if there are just 2 nodes with an odd number of edges then it is possible to find a route, provided that you start from one of the odd nodes.


As noted by Euler, where there are two (or any even number of) bridges between two regions these can be ignored because the traveller can use one bridge to go from say A to C and the other one to come back from C to A, completing a cycle, eliminating both bridges and leaving him where he started from, and able to proceed to another bridge.

In recognition of Euler’s contribution to Graph Theory, routes that visit each node once but none more than once are called Euler Cycles. Euler’s solution also applies to another banal problem, that I learnt at school, drawing figures without removing your pencil from the page.


A coloured map can be represented as a planar graph if the coloured regions of the map are replaced by same coloured vertices in the graph, and vertices are joined by an edge in the graph if their corresponding regions in the map share an edge.


In fact the planar graph is a dual of the map, and the map can be generated from the graph. Both map and graph obey, another contribution of Euler to Graph Theory, his formula for networks; regions + vertices – edges = 1. In the examples above 7 regions + 11 vertices – 17 edges = 1 for the map and 10 regions + 8 vertices – 17 edges = 1 for the graph.

The planar graph is therefore an exact equivalent of the map and the Four Colour Conjecture can be expressed as seeing if the vertices of the graph can be coloured with 4 colours so that no 2 adjacent vertices have the same colour.

More importantly planar graphs lend themselves to computer manipulation, and this in turn has lead to a, somewhat disputed, computer enabled proof of the four colour theorem. See here for more detail.

Directed Graphs

With planar graphs an edge (or arc) between two nodes A and B, is bi-directional and acts like a bridge that allows movement from B to A as well as from A to B, and can therefore only represent a symmetrical  relation between A and B, like adjacency. On the other hand, in directed graphs, edges are defined as having a direction, so that an edge from A to B acts like a turnstile or valve allowing movement from A to B but preventing movement from B to A. This allows values to be added to each edge, so that flows, electrical currents, dimensions etc. can be represented and networks modelled.



See here for details of Kirchhoff’s Laws for electrical flow in wires being applied to the automatic generation of house plans. Directed graphs also form the basis of Precedence Graphs, Critical Path Analysis  and modern Graphical Programming Systems like Grasshopper where inputs are on the left hand edge of each block, outputs on the right and scripted procedures can be added to the block itself.


Grasshopper_MainWindow (1)


Appel, K., Haken, W. and Koch, J.  (1977) Every Planar Map is Four Colorable. I: Discharging. Illinois J. Math. 21, 429-490

Appel, K. and Haken, W. (1977 ) Every Planar Map is Four-Colorable, II: Reducibility. Illinois J. Math. 21, 491-567.

Euler, L. (1736) Solutio problematis ad geometriam situs pertinentis. Comment. Acad. Sci. U. Petrop. 8, 128-140. Reprinted in Opera Omnia Series Prima, Vol. 7. pp. 1-10, 1766.

Hopkins B. and Wilson R. (2004) The Truth about Königsberg. College Mathematics Journal , 35, 198-207

March, L. and Steadman, P. (1971) The Geometry of Environment. RIBA Publications Ltd.

Newman J. R. (1953) The Königsberg Bridges. In Mathematics: An Introduction to its Spirit and Use, Scientific American. June 1978 22 121-124.

Steadman, P. (1970) The Automatic Generation of Minimum Standard House Plans Working Paper 23 University of Cambridge Land Use and Built Form Studies

Tutte, W. T. (1958) Squaring the Square from ‘Mathematical Games’ column, Scientific American Nov 1958.

Posted in Architecture, Enumeration, Geometry, Logic | Tagged , , , , | Leave a comment

Weber’s Law

Weber’s Law expresses a general relationship between an initial stimulus, a quantity or intensity, and the increased stimulus required for a change in the stimulus to be detected.

The task is to tell apart, or discriminate, two things that differ by only a slight amount.

Weber’s original 1834 observation was that if you are judging if two objects differ in weight, then two heavy objects must differ by a greater amount than two lighter ones if a difference in weight is to be detected.  That is heavier weights are harder to discriminate than lighter ones.

The ability to easily discriminate two numbers increases with the numerical distance between them. We react more quickly and make fewer mistakes the greater the distance is between the numbers being compared. This is the distance effect.


So it is easier to compare 2 and 8 (on the left) than it is to compare 8 and 9 (on the right), with separation distances of 6 (8 – 2) and 1 (9 – 8) respectively.

If the distance between the two numbers remains the same then it is easier to compare two small numbers than it is to compare two larger numbers. This is the size effect.


So it is easier to compare 3 and 4 (on the left) than it is to compare 8 and 9 (on the right), both comparisons having a separation distance of 1 (4 – 3 and 9 – 8 respectively).

The Just Noticeable Difference

The just noticeable difference, or difference threshold, is the least amount that a stimulus needs to be changed by, in order to produce a noticeable variation in the sensory experience that the stimulus is producing.

Weber’s Law states that the just noticeable difference is a constant fraction of the stimulus intensity.

                                  ΔI = Kw×I

Where ΔI is the just noticeable intensity difference, Kw is a constant factor (the Weber factor) and I is the stimulus intensity.

Example 1: 3-Day-Old Chick Experiments details here


In the first experiment 3-day-old chicks were trained on the number 5 and then exposed to the numbers 2 and 8, that is to numbers at equal numerical distances from the training value 5 (5 – 2 = 3 and 8 – 5 = 3). Similarly in the second experiment the training value was 20 and the chicks were exposed  to the numbers 8 and 32, equally distant from the trained value 20 (20 – 8 = 12 and 32 – 20 = 12).

In both cases avoiding results being contaminated by the distance effect.

Example 2 Jevons’es Data details here

In 1871 the early economist and logician William Stanley Jevons published an article in Nature “The Power of Numerical Discrimination” (Jevons 1871)

Jevons’es experimental procedure was to casually throw black beans at a 4½” diameter white target and then:-

At the very moment when the beans came to rest, their number was estimated without the least hesitation, and then recorded together with the real number obtained by deliberate counting”


Jevons concluded that for him the absolute limit of discrimination was 4, but recognised that the limit probably varied for other people and might perhaps be taken as 4½ if that made any sense.

His estimate corresponds fairly accurately to modern estimates of the subitising range for randomly located dots. See Subitising.

Jevon’s data corresponds to Weber’s Law with accuracy getting worse as set size increases.

ΔN = (N – 4½) ⁄ 9

Where ΔN is the numerical error,  is the limit of discrimination and the offset on the set size axis and the Weber Fraction is 1 ⁄ 9.

Example 3:Bayesian Analysis  details here

When baboons watch peanuts being counted into an opaque cylinder and then some more into a second cylinder, they move towards the second cylinder when it begins to have more peanuts in it than the first cylinder.

The Bayesian analysis of this switching behaviour proposes a parameterised model and uses data to infer a probability distribution for the value of each parameter.


The analysis recovers Weber fractions from the switch trials that are similar to the Weber fraction obtained with simple fits across all the trials, although the wide variability of these values is consistent with non-exact representations of the quantities in the first and second cylinders.

Fechner’s Law or Scale

In 1860 Fechner  proposed an extension to Weber’s Law. This states that as the stimulus intensity increases, it takes greater and greater changes in intensity to change the perceived magnitude by some constant amount. 

S = k  log(I)

Where S is the perceived magnitude, k is a modality and dimension constant and I is the stimulus intensity.


Weber’s Law is applicable to a variety of sensory modalities (brightness, loudness, mass, line length, etc.).  The value of the Weber fraction varies across these modalities but tends to be relatively constant within any particular modality.

It tends to be inaccurate for extremely small or extremely large stimuli values.

The concept of a just noticeable difference (JND) has commercial applications. For instance to ensure that negative changes (reduction in product size or increases in price) remain below the JND and are not apparent to customers. Or so that product improvements (better packaging, larger size or lower price) are apparent to customers but are not too wastefully expensive to produce. That is that they are at or just above the JND.


Cantlon, J. F., Piantadosi, S. T.,Ferrigno, S., Hughes, K. D.,Barnard, A. M. (2015) The Origins of Counting Algorithms. Psychological Science 1-13

Gelman, A., Carlin, J. B., Stern, H. S., Dunson, D. B., Vehtari, A., & Rubin, D. B. (2013).Bayesian data analysis (3rd ed.). Boca Raton, FL: CRC Press.

Jevons, W.S., (1871) The Power of Numerical Discrimination Nature, Thursday February 9, 1871.

Regani R., Vallortigara G., Priftis K., & Regolin L. (2015) Number-space mapping in the newborn chick resembles humans’ mental number line Science. DOI:10.1126/science.aaa1379

Posted in Architecture, Brain Physiology, Embodiment, Enumeration | Tagged , , , | Leave a comment

Baboon Counting Algorithms

Human counting can be thought of as a kind of condition controlled logic where counters increment a sequence of labels “one, two, three four…” until some condition is met. (Cantlon et al. 2015) The diagram below illustrates some, but not all, of these conditions.

/Users/grahamshawcross/Documents/blog_drafts/shooting baboons/Sm

Cantlon et al. wanted to know if condition controlled logic, as exhibited by humans when counting, also played a part in the numerical capacity of other primates.

Sequential Experiment

Their main experiment consisted of placing 3 opaque cylinders in front of one of just 2 Olive Baboon monkeys, the cylinders being separated by at least a monkey’s arm length.

Screen Shot 2015-07-09 at 11.19.46

Watched by a monkey, one cylinder was filled with from 1 to 8 shelled peanuts. This was done one peanut at a time. Still watched by the monkey a second cylinder was then filled, one item at a time, with from 1 to 8 shelled peanuts. The peanuts were shown to the monkeys for 2 seconds before being put into the cylinders and there was a 2 second gap between the presentation of each peanut. The third cylinder remained unfilled and the positions of the 3 cylinders in the row was randomly determined for each trial.

Once the second cylinder had been filled, the subject baboon was allowed to choose the cylinder she preferred by pointing to it with her finger. The baboon was then allowed to eat the peanuts from the cylinder she had chosen and shown the peanuts in the other cylinder before they were removed.

Simultaneous Procedure

Randomly interspersed with the sequential procedure described above, were an equal number of experiments where the peanuts were just presented simultaneously from the left and right hands.


On average, in 68% of all the trials the baboons chose the cylinder containing the most peanuts . However the monkeys’ numerical discrimination was effected by the ratio between the numbers of peanuts in each cylinder as indicated below.


That is, the results obey Weber’s Law, so that as the ratio between the quantities increases the monkeys’ accuracy in choosing the larger quantity decreases.

Their average sensitivity to differences between numerical values was 0.86 (their Weber fraction). This means that the monkeys required nearly a 2:1 ratio between the two quantities to reliably identify the larger one.

Switching Position

During the sequential procedure, it was observed that when the second cylinder began to have more peanuts than the first cylinder the monkeys often, if they needed to, switched position to be nearer the second, fuller cylinder .


Previous investigations had assumed that numerical comparisons only took place at the end of incrementing the second set of peanuts. The shifting of position when the second cylinder began to hold more peanuts than the first shows that the baboons are actively counting the peanuts whilst retaining an understanding of the number of items in the first cylinder.


The average success rate of 68%, is lower than that reported in a number of other similar experiments. (Cantlon & Brannon, 2006) (Nieder & Miller, 2003)

It is suggested that this is because the two baboons used in this experiment had not been trained and had not participated in any previous experiments. Also they were always rewarded with food, even if they did not pick the beaker with the most peanuts.

Two control conditions were introduced to in an attempt to exclude the possibility that the choice or shifting were influenced by experimenter cuing or the length of stimulus presentation.

In an attempt to avoid cueing, two experimenters were used, sitting back-to-back. The first experimenter filled the first cylinder with the number of peanuts specified by a trial list for that cylinder only. The second experimenter filled the second cylinder from another separate trial list.

Similar results were obtained with this procedure, so it was assumed that the choices and shifting were not influenced by cuing from the experimenter in either series of experiments.

This seems to present at least two difficulties. Dropping the peanuts into the first cylinder probably made a noise that could be heard by the second experimenter. The standard 2-second interval between peanuts also meant that the duration of the first experimenter’s activity was a measure of the number of peanuts in the first cylinder. In both cases the second experimenter, at least to some degree, ‘knows’ the number of peanuts in the first cylinder and may unconsciously communicate this to the subject or indicate when the monkey should pay more attention to the second cylinder and maybe switch over to it.

The simultaneous presentation procedure seemed to indicate that timing was unlikely to be being used to estimate numerosity. To avoid the possibility that the monkeys were judging the number of peanuts from the total duration of the presentation another series of trials was carried out. In half these trials the total baiting duration for the first cylinder was 30 seconds and the baiting duration for the second cylinder was 20 seconds. In the other half the duration times were reversed. There was no significant difference between the standard trials and these trials.

Bayesian Analysis of Switching

The idea of a Bayesian analysis is to propose a parameterised model and use data to infer a probability distribution for the value of each parameter.

The model assumes that the monkeys represent the quantity of peanuts in Set 1 as an approximate value with scalar variability and that as each peanut is added to Set 2 they noisily increment an approximate mental counter and compare it to the value of Set 1. It also assumes that there is a tendency to switch position if the value of Set 2 is greater than the value of Set 1.

Each step is parameterised with a variable whose value and probability is to be inferred from the data. In this case the parameters included

a. the variability of accumulators for Sets 1 and 2

b. a baseline rate of switching

c. a rate of switching when the Set 2 value is greater than the value of Set 1.

d. the probability of increasing the value of Set 2 when a peanut is added.

e. a baseline probability specifying how often an entire trial is ignored

Before examining any evidence (data), prior likelihoods were assigned to each parameter. The variability of the accumulators for Sets 1 and 2 were both given Gamma(2,1) priors. The rate of switching was assigned a Beta(1,9) prior, corresponding to a low expectation of switching. All the other parameters were given a Beta(1,1) prior, indicating no initial bias.

“Some settings of these parameters lead to viable alternative algorithms that do not count and compare, contrary to what we hypothesized. For instance, if the probability of incrementing Set 2 when each item is added is close to zero, this would mean that the representations of quantity are not updated with each item. If the baseline probability of switching is high, behavior is not dependent on the relative quantities of the two sets, and depends perhaps only on time. If Sets 1 and 2 are given very different noise (Weber ratio) values, it may be that the two sets are represented by qualitatively different systems. If quantities are precisely enumerated, the analysis will recover Weber ratios that approach zero. Exact counting therefore corresponds to a particular setting of the model parameters that could be supported by the data”.

A Markov-chain Monte Carlo procedure was run for 500,000 steps, drawing a sample every 200 steps. The quality of the model’s inference was tested by the standard method of running multiple chains from different starting positions. This yielded for each variable the posterior distributions shown below. These indicate the statistical probability of the various parameter values.


The posterior distributions shown above indicate that the most likely parameter values are consistent with the increment and compare algorithm. The monkeys had a high probability of incrementing their Set 2 accumulator with each additional peanut (distribution d). They also had low baseline probabilities of switching (distribution b) but a high probability of switching when they believed Set 2 contained more peanuts than Set 1 (distribution c).

The analysis also recovers Weber fractions (distributions at a) from the switch trials that are similar to the Weber fraction obtained with simple fits across all the trials, although the wide variability of these values is consistent with non-exact representations of the quantities in Sets 1 and 2.

The lack of attention demonstrated, particularly by the second monkey (distribution e) could also be a cause of behavioural noise in the analysis.


Human counting requires incrementing, iteration and condition controlled logic and the algorithm used by the monkeys exhibits all these logical elements.

The algorithm is incremental because, as each peanut is added to Set 2, it increments a mental counter. It is iterative because each time this happens a mental comparison is made with the quantity of peanuts in Set 1. It is condition controlled because each time a comparison is made the algorithm checks to see if Set 2 has approximately the same or a greater quantity of peanuts than Set 1. If it has the algorithm commits to choosing Set 2.

“non-human primates exhibit a cognitive ability that is algorithmically and logically similar to human counting”.

“the monkeys used an approximate counting algorithm for comparing quantities in sequence that is incremental, iterative, and condition controlled. This proto-counting algorithm is structurally similar to formal counting in humans and thus may have been an important evolutionary precursor to human counting”.


Barnard, A. M., Hughes, D.H., Gerhardt, R.R., DiVincenti, L., Bovee, J. M., and Cantlon J.F. (2013) Inherently Analog Quantity Representations in Olive Baboons (Papio anubis). Frontiers in Comparative Psychology, 2013 4:253

Cantlon, J. F., & Brannon, E. M. (2006). Shared system for ordering small and large numbers in monkeys and humans. Psychological Science, 17, 401–406.

Cantlon, J. F., Piantadosi, S. T.,Ferrigno, S., Hughes, K. D.,Barnard, A. M. (2015) The Origins of Counting Algorithms. Psychological Science 1-13

Gelman, A., Carlin, J. B., Stern, H. S., Dunson, D. B., Vehtari, A., & Rubin, D. B. (2013). Bayesian data analysis (3rd ed.). Boca Raton, FL: CRC Press.

Kruschke, J. (2011) Doing Bayesian Data Analysis: A Tutorial with R and BUGS. Europe’s Journal of Psychology Vol. 7, Isssue 4, Pages 1-187

Nieder, A., & Miller, E. K. (2003). Coding of cognitive magnitude: Compressed scaling of numerical information in the primate prefrontal cortex. Neuron, 37, 149–157.


Posted in Architecture, Brain Physiology, Enumeration, Logic | Tagged , , , | Leave a comment

Place Value


“The ingenious method of expressing every possible number using a set of ten symbols (each symbol having a place value and an absolute value) emerged in India. The idea seems so simple nowadays that its significance and profound importance is no longer appreciated. Its simplicity lies in the way it facilitated calculation and placed arithmetic foremost amongst useful inventions. The importance of this invention is more readily appreciated when one considers that it was beyond the two greatest men of Antiquity, Archimedes and Apollonius.”  (Laplace 1814, quoted in O’Conner et al)

Number Systems

A number system is a method for writing numbers, using numerals or other symbols in a consistent manner.

The Roman number system is illustrated below. In its development it demonstrates a number of different types of number system. In its simplest form it is an additive system. That is the values of the basic Roman numerals are simply added together, so MLXVI (1000+50+10+5+1) represents the Hindu-Arabic number 1066. In principle, with additive number systems the order of the numerals is not important, but in the Roman system numbers are usually written with largest and smallest numerals going from left to right.


When subtraction is optionally used, order does become important, so VI is 6 but IV is 4, XL is 40, XC is 90, CM 900 etc. This convention does not form part of the Roman method of calculation but is an aid to a more compact written representation. See Five Finger Exercises.

The subtraction pairs CM (1000-100) and XL (50-10) boxed above, are in effect surrogate numerals that need to be evaluated before being added to the other numerals.

The supplementary nature of subtraction can be seen in the simple Python program below that, without any checks, takes a number represented by Roman numerals and converts it to the equivalent Hindu-Arabic representation. It first adds the values of all the numerals together and then deducts any subtractions twice over to prevent double counting.


As shown in the diagram above multiplication is used to represent larger numbers. In some periods a horizontal bar above a group of numerals is used to multiply the bracketed numerals by 1,000. At various other times vertical bars are used as brackets. So |V| is 5,000, |X| 10,000, |XIV| 14,000 and |XL| is 40,000. Sometimes both horizontal and vertical bars are used to multiply by 1,000 x 1,000 or 1,000,000.


The Babylonian Number System is base 60 or sexagesimal. To avoid having separate numeral symbols for the numbers 1-59, it uses a base 10 system to generate these numerals. As shown below the 1-9 numerals use the appropriate number of copies of the units glyth. The 10, 20, 30, 40 and 50 numerals use the appropriate number of copies of the tens glyth. All the other numerals are made up from pairs of units and tens numerals, so for instance the 42 numeral consists of the 40 numeral (4 tens glyths) paired with the 2 numeral (2 units glyths). Although the numerals have a strong and memorable pattern on average they have 7 glyths each and at worst 14. See Subitising for relevance of this.


Numbers below the base 60, are simply represented by the 1-59 numerals themselves. Numbers above 59 are represented by using the 1-59 numerals to indicate the quantity of 60s. This numeral is placed to the left of the units numeral. Similarly for numbers above 359 a numeral representing the quantity of 36os (60×60) is placed to the left of the 60s numeral.

Given that 60 to the power zero (600 ) is 1, the numeral in the first right-most place or position represents the quantity of units. The numeral in the second place, to the left of the first place, represents the quantities of 6os or 601. The next place to the left represents the quantities of 360s or 60 x 60 that is 602 .

So each place, starting from zero on the right and moving to the left, represents increasing powers of the base of the number system in the Babylonian system, base 60.


In some cases as in the Babylonian version of 3609 (1 x 602 )+(9 x 60), illustrated above, there are places without a value, the second (60) place in this case. Initially this was dealt with, as in grid counting systems, by just leaving a space. This was a source of error and possible fraud so later a placeholder symbol was put in places where there were no values to be recorded.

However in the Babylonian number system the placeholder was never used in the first place or position, as it would be in the Hindu-Arabic decimal number system to differentiate say 7, 70 and 700 where zero is being used as a placeholder in the first place or position.

So as in the examples in the diagram it is difficult to differentiate (1 x 602 )+(9 x 60) from (1 x 603)+(9 x601) but they represent greatly different values, 3,609 and  24,840 respectively. It is probably this difference in value that  obviated the need to use placeholders in the first position.

Place Value Systems

The migration of the placeholder symbol to a true zero numeral that can be used in all places represents the arrival of place value systems. Our Hindu-Arabic base 10 number system is an example of such a place value system.


The base of a number system determines how many numerals that system requires. So a base 10 place value system requires ten numerals as illustrated above and a base 2 or binary system requires just two, 0 and 1. As shown earlier the Babylonian base 60 system has sixty numerals, if the placeholder symbol is included.

A place value system can be used with any base, the Mayan number system for instance is base 20 and has a genuine zero symbol. As shown below the Mayans wrote their numbers vertically with the first place at the bottom and succeeding places moving upwards.


Using a dot to represent units and a bar to represents fives, means that for each numeral there are never more than two sets of four glyths to be subitised.


As Laplace thought, place value number systems are difficult to explain, yet culturally extremely important; perhaps as important as the invention of the alphabet.

At the heart of the problem might be the difficulty in understanding that any number to the power zero is 1. This allows numerals in the first place to represent numbers up to the base of the number system. So there are 2 numerals in a binary (base 2) system, 10 in a decimal (base 10) system, 20 in the Mayan (base 20) system and 60 in the Babylonian (base 60) system if one counts their placeholder as a numeral.

Calculating systems such as Chinese rod counting, Roman grid calculating and the abacus have no problem representing zero without placeholders or a symbol for zero and use position to indicate powers of the base being used including, in the base 10 example below, negative powers for tenths, hundredths etc. Here vertical rods are units and a horizontal rod five units, again reducing the number of glyths required to five or less, that is within the subitising range.


Spoken number words, that use a hybrid system of addition and multiplication, also have no need of placeholders or zeroes. See Five Finger Exercises

/Users/grahamshawcross/Documents/blog_drafts/subitising/SubitisiAfter Dehaene (1992) Varieties of Numerical Abilities Cognition, 44 1-42

The need for placeholders, zeroes and place value number systems arrises from the need to record in writing the results of calculations for administrative and trade purposes, be it on clay tablets, papyrus or paper.



Dehaene, S. (1992) Varieties of Numerical Abilities Cognition, 44 1-42

Knuth, D. (1997) The Art of Computer Programming. Volume 2, 3rd Ed. Addison–Wesley. pp. 194–213, “Positional Number Systems”.

Lam, L.Y. (1996) The Development of Hindu-Arabic and Traditional Chinese Arithmetic Chinese Science 13: 35–54

O’Connor, John J.; Robertson, Edmund F., “Pierre-Simon Laplace”, MacTutor History of Mathematics archive, University of St Andrews., accessed 16 September 2015


Posted in Architecture, Classification, Enumeration, Logic | Tagged , , , | 1 Comment

Jevons’es Data

In 1871 the early economist and logician William Stanley Jevons published an article in Nature “The Power of Numerical Discrimination” (Jevons 1871)

According to Jevons, Sir William Hamilton had clearly stated the problem:

“Assuming that the mind is not limited to the simultaneous consideration of a single object, a question arises, How many objects can it embrace at once? ……

If you throw a handful of marbles on the floor, you will find it difficult to view at once more than six, or seven at most, without confusion; but if you group them into twos, or threes, or fives , you can comprehend as many groups as units, because the mind considers these groups as units; views them as wholes, and throws their parts out of consideration.”

Using a simple experimental technique, Jevons set out to  answer Sir William Hamilton’s question.

“A round paper box 4 1/2″ in diameter, lined with white paper and with the edges cut down to be only 1/4″ high, was placed in the middle of a black tray. A quantity of uniform black beans was then obtained, and a number of them taken up casually were thrown towards the box so that a wholly uncertain number fell into it. At the very moment when the beads came to rest, their number was estimated without the least hesitation, and then recorded together with the real number obtained by deliberate counting”

The data Jevons collected this way is tabulated below (taken directly from his article).


The table gives the number of times each set size was estimated correctly or incorrectly. So six beans were correctly identified 120 times but were incorrectly identified as five beans 7 times and as seven beans 20 times. Jevons was not surprised that he never made a mistake with three and four beans but was surprised that in 5% of trials he made mistakes with five beans.

Jevons analysed the error rates as follows:-


He supposed the error rate proportional to the excess of the real number over 4½ and obeying the formula error = m x (n – 4½) where n is the correct number and m is some constant. He than calculated m for each of the values of :-


Seeing them sufficiently equal he took the average (0.116) and proposed the following empirical formula:-

error = 0.116 x (n – 4½) or approximately n / 9 – ½


Jevons concluded that for him the absolute limit of discrimination was 4, but recognised that the limit probably varied for other people and might perhaps be taken as 4½ if that made any sense.

His estimate corresponds fairly accurately to modern estimates of the subitising range for randomly located dots. See Subitising.

The data also corresponds to Weber’s Law with accuracy getting worse as set size increases. A post on Weber’s Law to follow.

The diagram below summarises the error data.


Jevons calculated his formula  using unsigned error values (red outlines above) rather than signed errors (solid red above).

He also recognised that his method of throwing beans lead to the skewed distribution shown above with many more sets of seven beads thrown (156) than sets of three (23) or fifteen (11). Something that could easily be avoided using modern presentation techniques. See Find Your Own Space.


Jevons, W.S., (1871) The Power of Numerical Discrimination Nature, Thursday February 9, 1871.

Posted in Architecture, Brain Physiology, Enumeration, Randomness | Tagged , , , | Leave a comment

Shooting Baboons: A Story

If a man with a gun goes to shoot baboons near the edge of a forest, the baboons will see him coming, hide in the forest and not come out until he is seen to go away.

If the first man hides and a second man with a gun joins him, and then one of them walks away, the baboons will stay hidden and not come out of the forest. They know that there is still a man hiding with a gun .

The same is true if two, three, four or possibly five men join the first man and the same, or a smaller, number of men go away. The baboons stay hidden, they know that at least one man is still hiding.

However if six men with guns join the first one and then six of them ostentatiously walk away, after a while the baboons will come out of the forest and can be shot by the man they have failed to accounted for.


When a second man joins the first man and then one of them walks away, the baboons can calculate that one man remains hidden, they can subtract 1 from 2 and get the right answer that there is 1 left.

The baboons can also get the right answer with 1 plus (2, 3, 4 and possibly 5) minus (2, 3, 4 or 5 respectively).

It is therefore thought that baboons can do small number arithmetic with numbers up to about six, so have a number system something like none, one, two, three, four, five, six and many (more than six).

But when six men join the first man and then six  men walk away the baboon’s number system lets them down. This is because one plus six results in many, and many minus many gives none, the wrong answer. So it seems to the baboons that all the hunters have gone away and it is safe to come out of the forest.

Small Number Arithmetic

The diagram below illustrates the problem with small number arithmetic, using a slightly more restricted number system consisting of none, one, two, three and many (more than 3).

/Users/grahamshawcross/Documents/blog_drafts/shooting baboons/Sm

The system works well for addition, exhibiting closure (each operation results in a unambiguous instance of the number system itself). So one plus two gives three, two plus three gives many and many plus many gives many etc.

As baboons can apparently find out to their cost, problems arise with subtraction. Subtracting anything except none (one, two, three or many) from many is always problematic. In particular taking many from many seems most likely to result in none but in reality could also result in one, two, three or many depending on the unknowable “real” values of many.

It seems that the baboons are applying the simple rule “same minus same always results in none”. So one minus one, two minus two, three minus three and many minus many all give a result of none.


There is no evidence of anyone hunting baboons like this. The story was probably just made up to illustrate the limitations of languages that do not have words or a number system that can represent all numerosities.

There are human languages that use small number arithmetic and have a word like many to represent large numerosoties. (Butterworth et al., 2008) Isolated hunter gatherer cultures seem to have little need for an elaborate number system in their languages but tend to acquire them quite quickly upon contact and trade with the outside world.

The story also suggests an experimental technique for establishing the upper numerosity discrimination limits of animals and pre-verbal children, using an ‘expectancy violation technique’. See What Counts and  Otto Koehler.

Unneccessary Expansion

The problem caused by a lack of necessary number words is superficially similar to the apparent order in which languages “acquire” colour words. Some languages only have two colour words, cold and warm, corresponding to monochrome, black and white. Others have black and white plus red. Yet others add yellow then green or green then yellow, then blue, brown and finally purple, pink, orange or grey. (Berlin and Kay, 1969)

/Users/grahamshawcross/Documents/blog_drafts/shooting baboons/Co

Colour Hierarchy Diagram (after Berlin and Kay 1969)

The diagram above works from left to right (following the arrows and plus signs). If a language has a particular colour word then it will also have all the colour words to the left of that word. So if a language has a word for blue, then it will also have words for yellow, green, red, black and white. The diagram also indicates that if a language has a word for say pink, then it may, or may not, have a word for purple, but it will have colour words for brown, blue etc.

The colour words in a language provide foci, or prototypes, for the colour experience but say nothing about the boundaries between these colour foci.

This sequence corresponds fairly closely to the order in which children acquire colour words and is therefore a cultural example of the discredited evolutionary theory of recapitulation. This is summarised in Ernst Haekel’s phrase “ontogeny recapitulates phylogeny”, suggesting that as embryos develop into adults, they go through stages that resemble the evolution of their species.


Thanks again to my brother-in-law Tony Payne who told me the baboon story, although he cannot remember where he first heard it. See also Beau Geste Hypothesis and Cafetières, Disorder, Chaos and Anarchy


Berlin, B. and Kay, P. (1969) Basic Color Terms: Their Universality and Evolution. Berkeley: University of California Press.

Butterworth, B., Reeve, R., Reynolds, F., & Lloyd, D. (2008). Numerical thought with and without words: Evidence from indigenous Australian children. Proceedings of the National Academy of Sciences of the USA, 105, 13179-13184.

Posted in Architecture, Brain Physiology, Camouflage, Enumeration | Tagged , , , | 2 Comments

Beau Geste Hypothesis

In the 1924 book Beau Geste, and the many film versions that followed it, the climax of the action takes place in the desert at Fort Zinderneuf where members of the French Foreign Legion are attempting to hold off an Arab  attack.

‘As each man fell, throughout that long and awful day, he had propped him up, wounded or dead, set the rifle in its place, fired it, and bluffed the Arabs that every wall and every embrasure and loophole of every wall was fully manned.’ (Wren 1924).

Still from the 1939 film

Still from the 1939 film

Learning Many Songs

Many species of birds have larger repertoires of songs than seems strictly necessary. In an attempt to explain this John Krebs suggested what he called the Beau Geste Hypothesis. (Krebs 1977)

He describes the use by an individual, usually male, bird of a variety of different songs as an attempt to increase the apparent density of occupation of a territory and so discourage the interest of rivals. Singing the same song from many locations within the territory would most likely be interpreted as a single bird moving about, but singing different songs from lots of locations would more likely be interpreted as coming from a number of different birds. In effect different songs add verisimilitude to the individuality of the singer.

Being a good Darwinian, Krebs suggests that having a large repertoire of songs has an evolutionary advantage, because it allows birds to defend larger territories than would otherwise be the case.


Kreb’s hypothesis is that a large repertoire of songs allows a bird to falsely indicate a higher density of territory occupation than there is in reality. I think it not unreasonable to map density to numbers of individuals in the territory and say that the territory being defended has a larger number of competitive occupiers than is actually the case.


Thanks to my brother-in-law Tony Payne whose PhD was in animal behaviour and was latterly Professor of Anatomy at Glasgow University who told me this story, see also Cafetières, Disorder, Chaos and Anarchy


Krebs, J. R. (1977) The significance of song repertoires: The Beau Geste hypothesis. Animal Behaviour 25: 475-478

Wren, P. C. (1924) Beau Geste. John Murray

Yasukawa, K., Searcy, W. A. (1985) Song repertoires and density assessment in red-winged blackbirds: further tests of the Beau Geste hypothesis. Behavioral Ecology and Sociobiology. Vol. 16, Issue 2, 171-175

Posted in Architecture, Camouflage, Enumeration, Illusions | Tagged , , , , | 2 Comments