Prove the stronger statement with a nonempty subset. Order the $n\ge 1$ integers as $a_1,\dots ,a_n$, and form the prefix sumsThere are $n+1$ such sums but only $n$ residue classes modulo $n$. The pigeonhole principle gives indices $0\le i<j\le n$ with $s_i\equiv s_j(\mathrm{mod}n)$. Their difference satisfiesThe selected elements form a nonempty subset of $S$, proving the claim. Neither positivity nor distinct values in a general ordered sequence are needed for the consecutive sum divisible by the sequence length argument; distinctness merely makes the present input a set.

For five points, partition the unit square into four squares of side $1/2$. Assign boundary points to just one neighbouring piece. By the pigeonhole principle, two of the points lie in one piece, whose diameter is its diagonal, $\sqrt{(1/2{)}^2+(1/2{)}^2}=\sqrt{2}/2$.

For eight points, use seven smaller-diameter pieces rather than eight rectangles. Start with the convex pentagonTake its four reflected copies at the corners of the square. The remaining pieces are the left triangle with vertices $(0,1/4),(1/4,1/2),(0,3/4)$, its right-hand reflection, and the central diamond with vertices $(1/4,1/2),(1/2,1/4),(3/4,1/2),(1/2,3/4)$. These seven polygons cover the square with disjoint interiors. To verify coverage directly, for $0\le y\le 1/4$ the two bottom pentagons split the horizontal section at $x=1/2$. For $1/4\le y\le 1/2$, the five successive sections have endpoints $0,y-1/4,3/4-y,y+1/4,5/4-y,1$ and belong respectively to the left triangle, bottom-left pentagon, diamond, bottom-right pentagon and right triangle. Reflection gives the top half.

The diameter of a finite convex hull is the greatest distance between its vertices: if two points are convex combinations of vertices, their difference is a convex combination of vertex differences, and the triangle inequality bounds its norm by the largest such distance. Checking the five vertices of $P$ gives diameter $\sqrt{(1/2{)}^2+(1/4{)}^2}=\sqrt{5}/4$; reflections preserve that value. Each remaining triangle and the diamond has diameter $1/2$, which is smaller. After assigning shared boundaries to one piece, eight points in these seven pieces force a pair in a common piece. Hence some pair is at distance at most $\sqrt{5}/4$.

Both arguments are instances of a pigeonhole distance bound from a partition.

The pigeonhole principle states that if more than $r$ objects are placed in $r$ boxes, with $r\ge 1$, at least one box contains two or more objects. Equivalently, a function from a finite set of more than $r$ elements to a set of $r$ elements cannot be injective: if every box held at most one object, there would be at most $r$ objects altogether.

The Euclidean algorithm givesThe last nonzero remainder is $g=92$. Back-substitution produces its Bézout coefficients:Thus $(m,n)=(-8,11)$ is a requested pair. The final equality independently checks the calculation.

The integer congruence $x\equiv y(\mathrm{mod}n)$ means $n\mid (x-y)$: the difference is an integer multiple of the positive modulus $n$. Write $x_1-x_2=na$ and $y_1-y_2=nb$ for integers $a,b$. Thenso addition preserves integer congruence. For multiplication,The final coefficient is an integer, so multiplication also preserves integer congruence. These properties make addition and multiplication well defined on residue classes.

Suppose first that $f=O(g)$. Choose $C>0$ and $N$ so that $|f(n)|\le C|g(n)|$ for $n\ge N$. There are only finitely many natural numbers below $N$. Because $g(n)\ne 0$ at each of them, all ratios $|f(n)|/|g(n)|$ in this finite prefix are finite. LetThen $|f(n)|\le c|g(n)|$ both in the prefix and in the tail, hence on the entire domain of a function. This proves the finite-prefix extension of a big O bound.

Conversely, a bound valid for every natural number is certainly valid eventually. The purported real constant cannot be negative because $g$ never vanishes; if it is zero, enlarge it to a positive constant. The definition of Big O notation then applies. The nonvanishing assumption is what permits the finite exceptions to be absorbed into one constant.

For real-valued functions, use magnitude comparisons. The constants below are independent of $n$.

The statement $f(n)=O(g(n))$ in Big O notation means that some $C>0$ and integer $N$ satisfy $|f(n)|\le C|g(n)|$ for all $n\ge N$. The statement $f(n)=\Omega (g(n))$ in big omega notation means that some $c>0$ and $N$ satisfy $|f(n)|\ge c|g(n)|$ for all $n\ge N$.

Finally, $f(n)=\Theta (g(n))$ in big theta notation means that some $c,C>0$ and $N$ satisfyEquivalently it is both an eventual upper bound and an eventual lower bound. These definitions ignore a finite initial segment; they do not assert pointwise inequalities with constant one.

Pad every integer from $0$ through $999999$ with leading zeros to obtain a unique six-digit decimal string. If its digits sum to $5$, each digit is automatically at most $5$, so the usual digit upper bound $9$ adds no restriction. We therefore count the nonnegative integer solutions ofBy stars and bars, there are $\left(\genfrac{}{}{0ex}{}{5+6-1}{6-1}\right)=\left(\genfrac{}{}{0ex}{}{10}{5}\right)$. The all-zero string is not counted because its digit sum is zero, so every counted integer is positive. Thus the answer is $252$.

An allocation is a tuple $(x_1,\dots ,x_k)$ of nonnegative integers with ${\sum }_j{x}_j=n$, where $x_j$ is the number in labelled box $j$. Empty boxes are allowed. Encode the allocation by $n$ stars and $k-1$ bars: put $x_1$ stars before the first bar, $x_2$ between the first two bars, and so on. Adjacent bars represent an empty intermediate box; a bar at an end represents an empty end box.

Reading the group sizes recovers exactly one allocation from every such string, so this is a bijection. There are $n+k-1$ positions and we choose the $k-1$ bar positions. Hence stars and bars givesNo extra factor for ordering the objects is present, because the objects are indistinguishable. For $k=1$ the string has no bars and gives the single allocation of all objects to that box; for $n=0$ all boxes are empty, also a single allocation.

The rule of product says that if a construction has $r$ stages, with exactly $a_j$ choices at stage $j$ after every permitted earlier history, then it has ${\prod }_{j=1}^r{a}_j$ possible outcomes. The later choices need not be identical sets after different histories; their numbers must have the stated values.

For a permutation of $n$ distinct objects, choose the first object in $n$ ways, the second in $n-1$ ways, and continue until only one remains. Thus the number isEvery ordered arrangement is produced exactly once by its successive choices, so this counts permutations without omissions or repetitions. For $n=0$, the unique empty arrangement agrees with $0!=1$.

Let $A$ and $B$ be the finite sets of objects satisfying the two properties. The rule of sum says that mutually exclusive alternatives have additive counts: if $A\cap B=\varnothing$, then $|A\cup B|=|A|+|B|$. Without disjointness, the corresponding inclusion-exclusion principle isThe rule of subtraction counts objects satisfying the first property but not the second:In particular, if the objects with the second property form a subset of those with the first, the count is $|A|-|B|$. These conditions prevent either double counting an overlap or subtracting objects that were not counted initially.

The printed expression has one unmatched closing parenthesis. Remove that final surplus parenthesis and read the first disjunct as $\exists xP(x)$; the other disjunct has outer universal quantification over the displayed implication. To distinguish the two independent bound uses of $x$, rename the first to $u$.

Push the outer negation through the logical disjunction and through the quantifiers. Negating the implication preserves its existential antecedent and negates its consequent. Applying De Morgan's laws and the quantifier negation rules gives the negation normal formEach negation is now directly before an atomic formula. No bound variable has been captured, and no original existential quantification in the antecedent has accidentally been negated twice.

Two unary predicates suffice. Require all four unary predicate types to be inhabited:There are no constants, no logical equality and no nonunary predicates. Any two of these conditions disagree on at least one predicate, so one domain element cannot witness both. Hence every satisfying first-order structure has at least four elements, by distinct witnesses from incompatible unary predicates. Conversely take domain $\{a,b,c,d\}$, $P=\{a,b\}$ and $Q=\{a,c\}$: the four elements realize the four displayed unary predicate types, respectively. These element names describe the example; they are not constants in the first-order sentence.