Monthly Archives: April 2011

Seven Bridges of Königsberg

Posted on by

The Seven Bridges of Königsberg is a notable historical problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology.

The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges.

The problem was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges, and every bridge must have been crossed completely every time (one could not walk half way onto the bridge and then turn around and later cross the other half from the other side). Euler proved that the problem has no solution.

Farey Sequence

Posted on by

In mathematics, the Farey sequence of order n is the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to n, arranged in order of increasing size.

Each Farey sequence starts with the value 0, denoted by the fraction 0⁄1, and ends with the value 1, denoted by the fraction 1⁄1 (although some authors omit these terms).

A Farey sequence is sometimes called a Farey series, which is not strictly correct, because the terms are not summed.

The Farey sequences of orders 1 to 8 are :
F1 = {0⁄1, 1⁄1}
F2 = {0⁄1, 1⁄2, 1⁄1}
F3 = {0⁄1, 1⁄3, 1⁄2, 2⁄3, 1⁄1}
F4 = {0⁄1, 1⁄4, 1⁄3, 1⁄2, 2⁄3, 3⁄4, 1⁄1}
F5 = {0⁄1, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 1⁄1}
F6 = {0⁄1, 1⁄6, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 5⁄6, 1⁄1}
F7 = {0⁄1, 1⁄7, 1⁄6, 1⁄5, 1⁄4, 2⁄7, 1⁄3, 2⁄5, 3⁄7, 1⁄2, 4⁄7, 3⁄5, 2⁄3, 5⁄7, 3⁄4, 4⁄5, 5⁄6, 6⁄7, 1⁄1}
F8 = {0⁄1, 1⁄8, 1⁄7, 1⁄6, 1⁄5, 1⁄4, 2⁄7, 1⁄3, 3⁄8, 2⁄5, 3⁄7, 1⁄2, 4⁄7, 3⁄5, 5⁄8, 2⁄3, 5⁄7, 3⁄4, 4⁄5, 5⁄6, 6⁄7, 7⁄8, 1⁄1}

http://en.wikipedia.org/wiki/Farey_sequence

The Peter Principle

Posted on by

The Peter Principle states that “in a hierarchy every employee tends to rise to his level of incompetence”, meaning that employees tend to be promoted until they reach a position at which they cannot work competently. It was formulated by Dr. Laurence J. Peter and Raymond Hull in their 1969 book The Peter Principle, a humorous treatise which also introduced the “salutary science of hierarchiology.”

The principle holds that in a hierarchy, members are promoted so long as they work competently. Eventually they are promoted to a position at which they are no longer competent (their “level of incompetence”), and there they remain, being unable to earn further promotions. Peter’s Corollary states that “in time, every post tends to be occupied by an employee who is incompetent to carry out their duties” and adds that “work is accomplished by those employees who have not yet reached their level of incompetence”. “Managing upward” is the concept of a subordinate finding ways to subtly “manage” superiors in order to limit the damage that they end up doing.

This principle can be modelled and has theoretical validity for simulations.However, all of the real world evidence for it is anecdotal (and often intended to be humorous in nature).

Yerkes-Dodson Law

Posted on by

The Yerkes–Dodson law is an empirical relationship between arousal and performance, originally developed by psychologists, Robert M. Yerkes and John Dillingham Dodson in 1908. The law dictates that performance increases with physiological or mental arousal, but only up to a point. When levels of arousal become too high, performance decreases. The process is often illustrated graphically as a curvilinear, inverted U-shaped curve which increases and then decreases with higher levels of arousal.

http://en.wikipedia.org/wiki/Yerkes%E2%80%93Dodson_law

Optically Variable Ink

Posted on by

Optically variable ink (OVI) is an anti-counterfeiting measure used on many major modern banknotes.

The ink displays two distinct colors depending on the angle the bill is viewed at. The United States fifty-dollar bill, for example, uses color shifting ink for the numeral 50 so that it displays copper at one angle, and bright green in another.

OVI is particularly useful as an anti-counterfeiting measure as it is not widely available; the major manufacturer is a Swiss company called SICPA.

Color-shifting inks reflect various wavelengths in white light differently, depending on the angle of incidence to the surface. An unaided eye will observe this effect as a change of color while the viewing angle is changed. A color copier or scanner can copy a document only at one fixed angle relative to the document’s surface.

http://en.wikipedia.org/wiki/Optically_Variable_Ink

Grounded Theory

Posted on by

Grounded theory (GT) is a systematic methodology in the social sciences emphasizing generation of theory from data in the process of conducting research. It is mainly used for qualitative research, but is also applicable to other data (e.g., quantitative data; Glaser, 1967, chapter VIII).

It is a research method that operates almost in a reverse fashion from traditional research and at first may appear to be in contradiction of the scientific method. Rather than beginning by researching and developing a hypothesis, the first step is data collection, through a variety of methods. From the data collected, the key points are marked with a series of codes, which are extracted from the text. The codes are grouped into similar concepts in order to make them more workable. From these concepts, categories are formed, which are the basis for the creation of a theory, or a reverse engineered hypothesis. This contradicts the traditional model of research, where the researcher chooses a theoretical framework, and only then applies this model to the studied phenomenon.

http://en.wikipedia.org/wiki/Grounded_Theory

Brownian Motion

Posted on by

Brownian motion (named after Robert Brown, who first observed the motion in 1827, when he examined pollen grains in water), or pedesis (from Greek: πήδησις “leaping”) is the assumably random movement of particles suspended in a fluid (i.e., a liquid such as water or a gas such as air) or the mathematical model used to describe such random movements, often called a particle theory.

The mathematical model of Brownian motion has several real-world applications. An often quoted example is stock market fluctuations. However, movements in share prices may arise due to unforeseen events which do not repeat themselves.

Brownian motion is among the simplest of the continuous-time stochastic (or probabilistic) processes, and it is a limit of both simpler and more complicated stochastic processes (see random walk and Donsker’s theorem). This universality is closely related to the universality of the normal distribution. In both cases, it is often mathematical convenience rather than the accuracy of the models that motivates their use. This is because Brownian motion, whose time derivative is everywhere infinite, is an idealized approximation to actual random physical processes, which always have a finite time scale.

http://en.wikipedia.org/wiki/Brownian_Motion

Tesseract

Posted on by

In geometry, the tesseract, also called an 8-cell or regular octachoron or cubic prism, is the four-dimensional analog of the cube. The tesseract is to the cube as the cube is to the square. Just as the surface of the cube consists of 6 square faces, the hypersurface of the tesseract consists of 8 cubical cells. The tesseract is one of the six convex regular 4-polytopes.

A generalization of the cube to dimensions greater than three is called a “hypercube”, “n-cube” or “measure polytope”. The tesseract is the four-dimensional hypercube, or 4-cube.

According to the Oxford English Dictionary, the word tesseract was coined and first used in 1888 by Charles Howard Hinton in his book A New Era of Thought, from the Greek τέσσερεις ακτίνες (“four rays”), referring to the four lines from each vertex to other vertices. Some people have called the same figure a tetracube, and also simply a hypercube (although the term hypercube is also used with dimensions greater than 4).

http://en.wikipedia.org/wiki/Tesseract

Hypercube

Posted on by

In geometry, a hypercube is an n-dimensional analogue of a square (n = 2) and a cube (n = 3). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space’s dimensions, perpendicular to each other and of the same length.
An n-dimensional hypercube is also called an n-cube. The term “measure polytope” is also used, notably in the work of H.S.M. Coxeter (originally from Elte, 1912[1]), but it has now been superseded.

The hypercube is the special case of a hyperrectangle (also called an orthotope).

A unit hypercube is a hypercube whose side has length one unit. Often, the hypercube whose corners (or vertices) are the 2n points in Rn with coordinates equal to 0 or 1 is called “the” unit hypercube.

http://en.wikipedia.org/wiki/Hypercube

Fatalism

Posted on by

Fatalism is a philosophical doctrine emphasizing the subjugation of all events or actions to fate.
Fatalism generally refers to several of the following ideas:
Though the word “fatalism” is commonly used to refer to an attitude of resignation in the face of some future event or events which are thought to be inevitable, philosophers usually use the word to refer to the view that we are powerless to do anything other than what we actually do. Included in this is that man has no power to influence the future, or indeed, his own actions. This belief is very similar to predeterminism.
That actions are free, but nevertheless work toward an inevitable end. This belief is very similar to compatibilist predestination.
That acceptance is appropriate, rather than resistance against inevitability. This belief is very similar to defeatism.

While the terms are often used interchangeably, fatalism, determinism, and predestination are discrete in emphasizing different aspects of the futility of human will or the foreordination of destiny. However, all these doctrines share common ground.

Determinists generally agree that human actions affect the future but, because the future is predetermined, human action is just part of the overall cause. Their view does not accentuate a “submission” to fate, whereas fatalists stress an acceptance of all events as inevitable. In other words, determinists believe the future is fixed because of absolute causality, whereas fatalists and many predestinarians think the future is inescapable despite causality.
Therefore, in determinism, if the past were different, the present and future would also differ. For fatalists, such a question is negligible, since no past could have happened other than the one that has happened.

Fatalism is a broader term than determinism. The presence of history indeterminisms/chances, i.e. events that could not be predicted by sole knowledge of other events, does not exclude fatalism. Necessity (such as a law of nature) will happen just as inevitably as a chance—both can be imagined as sovereign.

http://en.wikipedia.org/wiki/Fatalism

Optimism Bias

Posted on by

Optimism bias is the demonstrated systematic tendency for people to be overly optimistic about the outcome of planned actions. This includes over-estimating the likelihood of positive events and under-estimating the likelihood of negative events. Along with the illusion of control and illusory superiority, it is one of the positive illusions to which people are generally susceptible. Excessive optimism can result in cost overruns, benefit shortfalls, and delays when plans are implemented or expensive projects are built. In extreme cases these can result in defeats in military conflicts, ultimate failure of a project or economic bubbles such as market crashes.

http://en.wikipedia.org/wiki/Optimistic_Bias

Alberti Cipher Disk

Posted on by

The Alberti cipher disk, also called formula, is a cipher disc which was described by Leon Battista Alberti in his treatise De Cifris of 1467. The device embodies the first example of polyalphabetic substitution with mixed alphabets and variable period, and is made up of two concentric disks, attached by a common pin, which can rotate one with respect to the other.
The larger one is called Stabilis [stationary or fixed], the smaller one is called Mobilis [movable]. The circumference of each disk is divided into 24 equal cells. The outer ring contains one uppercase alphabet for plaintext and the inner ring has a lowercase mixed alphabet for ciphertext.
The outer ring also includes the numbers 1 to 4 for the superencipherment of a codebook containing 336 phrases with assigned numerical values. This is a very effective method of concealing the code-numbers, since their equivalents cannot be distinguished from the other garbled letters.
The sliding of the alphabets is controlled by key letters included in the body of the cryptogram.

First method of encipherment

A lowercase letter on the smaller ring is used as an index.
In this example the letter g in the inner ring is chosen as an index and is moved under an uppercase letter (in this case A) of the stationary ring. The alphabets in use are (see figure):
ABCDEFGILMNOPQRSTVXZ1234 Stationary disk
gklnprtuz&xysomqihfdbace Movable disk
Dispatch: “La guerra si farà …”
_LAGVER2RA_ Plaintext
AzgthpmamgQ Ciphertext
The key letters A and Q are included in the cryptogram. The small letter a resulting from the encipherment of the number 2 is a null and must be discarded in the decipherment.
After enciphering a few letters a different uppercase letter (Q) is inserted in the cryptogram and the movable disk is accordingly rotated obtaining a new combination:
QRSTVXZ1234ABCDEFGILMNOP Stationary disk
gklnprtuz&xysomqihfdbace Movable disk
The encipherment will resume thus:
_SIFARÀ Plaintext
Qlfiyky Ciphertext.
The same procedure will be continued with different key letters through the end of the message.

Second method of encipherment

An uppercase letter in the stationary disk is used as an index.
In this example the letter A is chosen as an index and the small m of the movable disk is juxtaposed to the index letter. The changes of alphabets will be indicated by enciphering one of the four numbers.
ABCDEFGILMNOPQRSTVXZ1234 Stationary disk
mqihfdbacegklnprtuz&xyso Movable disk
Dispatch: “La guerra si farà …”
_LAGVERA3 Plaintext
mcmbufpms Ciphertext
One of the two R’s is omitted to defy cryptanalysis. The presence of the letter s enciphering the number 3 indicates the need for turning the movable disk to a new position. The letter s is then moved under the letter A.
ABCDEFGILMNOPQRSTVXZ1234 Stationary disk
somqihfdbacegklnprtuz&xy Movable disk
The encipherment will resume thus:
_SIFARÀ Plaintext
sndhsls Ciphertext

The same procedure will be continued through the end of the message, using the four numbers to designate the alphabet shifts.
The Alberti disk encipherment has nothing to do with Affine Shifts, Keyword shifts, Caesar shift or Vigenère ciphers. Caesar’s cipher is a simple substitution based on the sliding of a single ordinary alphabet with fixed key. Once the equivalent of a letter is discovered all the equivalent cipher letters are known. With the Alberti cipher there are two mixed alphabets and the key varies continuously during encryption, therefore the discovery of a single letter does not permit further progress. Frequency analysis is also impossible because the same letter is always enciphered differently. The Vigenère cipher is based on a single ordinary alphabet like that of Caesar and is easily solved after discovering its fixed period by means of the Kasiski exam. This is not possible with Alberti.

http://en.wikipedia.org/wiki/Alberti_cipher_disk