Let be the number of objects in box . The arrangements correspond exactly to nonnegative integer solutions of . By stars and bars, place stars and separating bars in a row. The number of stars between consecutive bars records the occupancy of each distinguishable box, with adjacent bars allowing an empty box. Choosing the bar positions gives
Using with integers ,
The quantity in parentheses is an integer, so the divisibility criterion for modular arithmetic gives
By modular arithmetic, and for some integers . Adding gives
Since is an integer, this proves
By Euclidean division, write and , with integers and . The hypothesis is . Apply the addition rule from part (b)(i) with to obtain
Therefore . But , and the only multiple of in that interval is zero. Hence
so the two remainders agree.
Put . Because , is a nonnegative integer, and
The function is strictly increasing for , so . Both powers are integers. Taking the floor function therefore gives
Taking nonnegative th roots now gives . Consequently
The argument also covers , when both outer floors are zero.
A function is periodic with period when
The period need not be the smallest positive one; for example, every positive integer multiple of a period is also a period.
The probability generating function of a nonnegative integer-valued random variable is
using also at . It is always defined for , and indeed the power series converges absolutely for all real or complex with , because
It may be defined beyond the unit disk where this power series converges absolutely; such a larger domain depends on the distribution. In particular and .
For parts (b)–(e), use array indices as tree handles. This also makes the shared storage in part (d) type-correct: both pending handles and output markers occupy integer cells. Zero denotes a leaf of a rooted tree; a positive handle denotes a fork whose children are in nodes[t-1]. Only finite acyclic structures are admitted. An allocated fork's children are themselves valid handles.
CONST MaxForks = 100000;
TYPE Tree = INTEGER;
     Node = RECORD left, right: Tree END;
     Arena = ARRAY MaxForks OF Node;
VAR nodes: Arena;
    used: INTEGER;

PROCEDURE NewFork(left, right: Tree): Tree;
BEGIN
  ASSERT(used < MaxForks);
  nodes[used].left := left; nodes[used].right := right;
  INC(used);
  RETURN used
END NewFork;

PROCEDURE Preorder(t: Tree; VAR out: ARRAY OF INTEGER;
                   VAR count: INTEGER);
  PROCEDURE Visit(p: Tree);
  BEGIN
    IF p = 0 THEN
      out[count] := 0; INC(count)
    ELSE
      out[count] := 1; INC(count);
      Visit(nodes[p-1].left); Visit(nodes[p-1].right)
    END
  END Visit;
BEGIN
  count := 0; Visit(t)
END Preorder;
Initialize used := 0 before constructing any trees; NewFork allocates within this arena. The fixed capacity is an implementation parameter and may be replaced by a dynamically allocated arena. The returned prefix out[0..count) encodes Boolean values by and . This encoding is part of the chosen representation, not a conversion of a pointer into a Boolean value.
The recursion invariant is that Visit(p) appends exactly the preorder traversal of the subtree represented by p. If the full binary tree has forks, it has leaves; hence
Each occurrence is visited once, using linear time complexity and a call stack bounded by the height of a binary tree. The arena is the input representation, not an extra copy made by the traversal.
Let be the final output length, the number of emitted markers, and the number of pending handles. Each pending subtree contributes at least one future marker, so
Store output from the low end and the stack from the high end of the same array. A pop frees one cell before the next write. For a fork, the two pushed children each account for at least one of the remaining markers. Thus the two regions never overlap.
PROCEDURE PreorderShared(t: Tree; VAR out: ARRAY OF INTEGER;
                         VAR count: INTEGER);
VAR top, cap: INTEGER; p: Tree;
BEGIN
  cap := LEN(out); count := 0;
  top := cap-1; out[top] := t;
  WHILE top < cap DO
    p := out[top]; INC(top);
    IF p = 0 THEN
      out[count] := 0; INC(count)
    ELSE
      out[count] := 1; INC(count);
      DEC(top); out[top] := nodes[p-1].right;
      DEC(top); out[top] := nodes[p-1].left
    END
  END
END PreorderShared;
The loop invariant includes count <= top, with pending handles in out[top..cap) and final markers in out[0..count). The preceding accounting proves every intermediate write also respects array bounds. This uses the integer handle representation chosen in part (b). Simply putting a pointer into a genuinely Boolean-typed cell would not be valid Oberon.
An Oberon pointer refers to a record containing an integer label and two subtree references:
TYPE
  Tree = POINTER TO Node;
  Node = RECORD
    left, right: Tree;
    label: INTEGER
  END;
Use NIL for the empty binary tree, including either absent child. The representation invariant requires a finite, acyclic binary tree with disjoint left and right subtrees. In particular, shared nodes would represent a different structure and invalidate destructive traversal arguments.
Use binary search on an interval with unequal endpoint values. The array need not be sorted:
l := 0; r := n;
WHILE r-l > 1 DO
  m := l + (r-l) DIV 2;
  IF b[l] # b[m] THEN r := m ELSE l := m END
END;
k := l;
The loop invariant is
It holds initially by the given endpoint inequality, which also implies . When , . If , replacing maintains unequal endpoints. Otherwise , so replacing maintains them. This does not require monotonicity or even just two possible values.
The positive integer width is a loop variant, reduced to at most its old half rounded up. On exit , giving
There are at most iterations. The additive constant handles .
Maintain an integer len, initially zero, with len = length xs:
PROCEDURE Add(x: INTEGER);
BEGIN
  ASSERT(len < N);
  u[len] := x;
  len := len+1
END Add;
The precondition is the abstract capacity condition. Appending at the first unused array index establishes in constant running time.
If get(k) first applies a comparison sort to all entries, the comparison sorting lower bound gives at least comparisons in the worst case. A merge sort or heapsort meets that order, after which indexing costs constant time:
This is a logarithmic factor worse than linear. The qualification to comparison sorting is necessary: merely saying that keys are integers does not prohibit counting sort for a bounded small range or radix sort under suitable machine-key assumptions. The printed assertion of an unavoidable superlinear bound needs the comparison model.
Represent a multiset by a pure multiplicity function. Every operation returns a new function describing updated counts:
class ContraMSet[-T](f: T => Int) {
  def count(x: T): Int = f(x)

  def insert(x: T): ContraMSet[T] =
    new ContraMSet[T]((y: T) => f(y) + (if (y == x) 1 else 0))

  def delete(x: T): ContraMSet[T] =
    new ContraMSet[T]((y: T) => {
      val old = f(y)
      if (y == x && old > 0) old - 1 else old
    })

  def union[U <: T](that: ContraMSet[U]): ContraMSet[U] =
    new ContraMSet[U]((y: U) => this.count(y) + that.count(y))
}
An empty instance is new ContraMSet[T]((_: T) => 0). The constructor's precondition is that f is pure and gives a nonnegative integer count, with finite support of a multiset if only finite multisets are intended. Nonnegativity and the support condition are preserved by each operation. Integer overflow must be excluded for this fixed-width count interface.
A contravariant type parameter makes ContraMSet[T] a consumer of values of type T. Thus a counter able to answer queries for every animal can also answer queries restricted to cats. It does not expose or enumerate stored T values. The return type ContraMSet[T] is legal: its outer covariant result position and the class's contravariant argument position together place negatively.
For union, the argument itself is in a negative position, while its ContraMSet argument would reverse that sign. Using ContraMSet[T] directly as the parameter type would therefore put positively and fail the variance-position rule. Introduce : both operands can count every U, and their sum is a ContraMSet[U]. This is a restriction to a common query domain; operations do not promise to preserve counts outside the narrowed domain.[ref]
Pointwise evaluation gives
No old function is modified, so updates preserve immutable object. Constructing each wrapper takes constant work, but a later count may traverse a chain of previously created programming closures; its running time need not be constant in the history length. This functional representation trades enumeration and direct storage of occurrences for composable counting behavior.
We prove the contrapositive. If , Euclidean division gives or for an integer . Squaring gives respectively or . Both have remainder upon division by , so . Taking the contrapositive yields .
For a proof by contradiction, suppose for positive integers in lowest terms, so . Squaring gives , and part (a) implies . Write ; then , hence , and part (a) again implies . This contradicts the coprimality of . Therefore is an irrational number.
For each fixed positive integer , part (i) gives . This meets big O notation with constant and threshold . True: for fixed . The constant may depend on ; no claim uniform in a varying is required.
Use the symmetric tree fold equations for the other algebraic data type:
foldZag (fZag,eZag) (fZig,eZig) Nal = eZag
foldZag (fZag,eZag) (fZig,eZig) (Cans x z) =
  fZag x (foldZig (fZig,eZig) (fZag,eZag) z)
The most general type signatures, using the same schematic variable names independently for each function, are
foldZig :: (a -> s -> r, r) -> (b -> r -> s, s)
        -> Zig a b -> r
foldZag :: (a -> s -> r, r) -> (b -> r -> s, s)
        -> Zag a b -> r
For foldZig, the first empty value has type r, so the first combining function must return r. Its label argument has type a. The recursively folded tail has some independent result type s, giving a -> s -> r. The second combining function consumes a b label and an r result and returns s, giving b -> r -> s. The second empty value has type s. Swapping the two handler pairs and the label types makes the recursive call well-typed. The identical argument applies to foldZag.
The two result types need not coincide. For example, one handler can return an integer and the other a list; forcing both results to have one type would lose parametric polymorphism allowed by the definitions.
Evaluate the supplied function once at each positive integer, retaining its largest value so far. In particular do not initialize the maximum to zero: might be negative everywhere.
PROCEDURE record(f, emit);
VAR n, best, y: INTEGER;
BEGIN
  best := f(1);
  emit(1);
  n := 2;
  WHILE TRUE DO
    y := f(n);
    IF y > best THEN
      emit(n);
      best := y
    END;
    n := n + 1
  END
END record;
At the loop head the loop invariant is , best , and precisely the record values with argument less than have been emitted, in increasing argument order. The first argument is a record because its comparison set is empty. The strict test correctly excludes ties. Updating best only on a strict increase preserves the loop invariant.
Exactly one call of f is made per processed argument. For an arbitrary supplied function, an unexamined argument can have a value larger than all previous values, so skipping its evaluation cannot be correct in general. This assumes is a total, deterministic function; the requested infinite computation ignores integer overflow.
Use the Euclidean algorithm with floor quotient and nonnegative remainder, including for a negative numerator:
PROCEDURE rat2cf(n, d: INTEGER): fraction;
VAR q, r: INTEGER; p: fraction;
BEGIN
  q := n DIV d; r := n MOD d;
  NEW(p); p.head := q; p.tail := NIL;
  IF r # 0 THEN p.tail := rat2cf(d, r) END;
  RETURN p
END rat2cf;
For , Euclidean division gives with . If , the singleton [q] is exact. Otherwise
so the recursive tail represents . Its numerator is positive and greater than its denominator, so every tail head is a positive integer. The new denominator is strictly smaller than , proving algorithm termination by descent through the positive integers.
The returned list represents exactly . For example gives [-3,1,2]; truncating negative division toward zero would violate the required positivity of the tail. There are Euclidean algorithm steps, with output allocation and recursive stack depth linear in the number of generated nodes.