Unpublished Short Notes

A position paper on fairness.   1988
A rebuttal of Dijkstra's position on fairness.

On the union of well-founded relations: An application of Koenig's Lemma  Feb 16, 1996
We are given two well-founded relations on the same set, and that their union is transitive. We show that the union is well-founded.

Sorting The Rows of a Matrix Preserves the Sorted Columns  Feb 19, 1996
Given is a matrix whose columns are sorted. Show that if each row is sorted individually then the columns remain sorted.

Random Number Generation without Repetition  Mar 27, 1996
We are given a function from naturals to naturals, which is applied repeatedly starting at a fixed seed. Floyd has shown how repetitions can be detected in this sequence. We give a proof of this result.

A Counting Problem Communicated by Dijkstra  April 9, 1996
Given that there are 25 boys and 25 girls. A party has 12 tables, each of which seats 2 boys and 2 girls. Thus, a party is attended by 24 boys and 24 girls. A boy sees 2 girls at his table in a party, and so do the girls. A set of parties, P, is feasible if each boy/girl sees different girls/boys in different parties in P. What is the size of the largest feasible set?

A puzzle on Termination  April 9, 1996
Given is a 10 X 10 square grid. A cell is a square in the grid. Two cells are neighbors if they share a side. Initially 9 cells are chosen and colored red. Next, any cell may be colored red provided it has two red neighbors. Prove or disprove that the entire region can be colored red.

A puzzle on infinite sequences: An application of Koenig's Lemma  April 12, 1996
Define a word to be any non-empty finite sequence of symbols. Each word is either good or bad. Given an infinite sequence of symbols, show that beyond some point, the sequence can be broken into words that are all good or that are all bad.

Reducing Satisfiability to Quadratic Programming  May 15, 1996
We show that the boolean satisfiability problem can be reduced to the quadratic programming problem.

A Useful Recurrence for Division  June 20, 1996
We show a recurrence that is useful for division.

Coloring Grid Points, without Rabbits and Snakes  Dec 18, 1996
For any finite set of grid points in the plane, we can colour each of the points either red or blue such that on each grid line the number of red points differs by at most 1 from the number of blue points.

There are Infinitely Many Primes  Mar 21, 1997
The following proof of the classical theorem is due to Dijkstra.

Making Multiple Copies under possibility of Failure  April 4, 1997
It is required to copy a file N times; call each copy a clone of the original. The file consists of a sequence of symbols each of which is independently copied. Therefore, we consider the problem when the file consists of a single symbol.

Common Meeting Time  Dec 5, 1997
We develop the appropriate conditions on the functions which are used in the common meeting time problem.

Dijkstra's Proof of Hall's Theorem  Dec 22, 1997
This note contains my interpretation of a proof by Dijkstra of Hall's theorem.
Remarks on Hall's Theorem of Distinct Representatives  Dec 30, 1997.
This is an observation by me on Hall's theorem.

Knowledge, Product and Sum   Jan 30, 1998
There are two parties, Product and Sum, who are given numbers p and s, respectively, where p = m x n and s = m+n, for some unknown integers m and n, each between 2 and 100. The parties deduce the values of m and n after a certain exchange. This note explains a solution due to Dijkstra (EWD-666).

A Proof about the Harmonic Series.   Aug 13, 1998
The following problem and its solution was shown to me by Carroll Morgan.

Arithmetic Mean is greater than or equal to Geometric Mean.   Sep 23, 1998
A short proof of this classical result.

The Muddy Children Puzzle  Oct 8, 1998
There is a finite group of children where each child is clean or dirty. No child knows if it is clean or dirty, but it can see if every other child is clean or dirty. It is common knowledge that there is at least one dirty child. In a round, (1) the children are asked: do you know if you are dirty, and (2) each of them responds with ``NO'', ``YES, I am dirty'', or ``YES, I am clean''. Responses are heard by all children. Rounds are repeated ad infinitum starting at round 0. Prove that a child who sees n dirty children, n \ge 0, will answer YES in round n, but no earlier.

Dijkstra's Shortest Path as a Simulation Problem.  Nov 13, 1998
Dijkstra's Shortest path algorithm can be seen as a simulation of a physical system.

Rules for Division by 3 and 11.  Dec 2, 1998
Show that for any natural number n, n mod 3 = r.n mod 3, where r.n is the sum of decimal digits in n. The rule for division by 11 is to start from the lowest digit of the number, and add and subtract the digits alternately.

Minimum Spanning Tree.  Dec 12, 1998
This note develops two well-known algorithms for finding the minimum spanning tree.

A property of Identity Function: An Exercise in Induction.  Sep 16, 1999
Let f be a function from naturals to naturals. It is given that for all n, f²(n) < f(n+1). Prove that f is the identity function. We will actually prove a generalization of this result.

Russell Paradox, Cantor Diagonalization.   Sep 28, 1999
Formal Proofs are simpler than their informal counterparts, for Russell Paradox and Cantor's Diagonalization argument.

Permutations Generated by a Stack Machine.   Sep 28, 1999
An output string is computed as follows from an input string using an infinite stack. In each step either the next input symbol is added to the stack, or the top of the stack is moved to the output. We characterize the outputs for a given input.

A proof by Erdos.   Oct 1, 1999
A sequence of numbers whose length exceeds n² contains either an ascending or a descending subsequence longer than n.

Unique Prime Factorization Theorem.   Oct 15, 1999
For every positive integer there is a unique bag of primes whose product equals that integer. The fact that there is a bag of primes corresponding to every positive integer is readily proven using induction (and the axioms we have listed below). We prove the uniqueness part: distinct bags of primes have distinct products.

Locating the Center of a Set of Points on a Curve.   June 15, 2000
Given are a finite number of points on a simple closed curve; call these points anchors. It is required to find a point, called the center, so that the sum of distances between the center and the anchors is the minimum over all points.

Enumerating the Strings of a Regular Expression.   Aug 29, 2000
We develop an algorithm to enumerate the strings of a regular expression in increasing order.

A proof of quiescence of a distributed algorithm   Aug 30, 2000
An undirected connected finite graph has a natural number initially associated with each node. There is a distinguished node, anchor, whose value is always 0. A non-anchor node can make a move only if its value differs from v, which is 1 + the minimum value over all its neighbors; in that case it sets its value to v. A computation is an alternating sequence of states and moves, starting with the initial state. Show that each computation is finite.

Computing Spans.   Jan 22, 2001
Given is a sequence of integers. For any element, e, of the sequence, define its "span" to be the length of the longest segment ending at e where each element of the segment is at most e in value. This note contains development of a linear algorithm for computing all the spans.

A Problem due to J Moore.   Mar 28, 2001
The following problem was posed by J Moore during the faculty lunch today. Let there be two machines with two registers each, which can read/write a shared counter. Initially the counter holds the value 1 and all registers are empty. There are two atomic actions: