Selected Problems in Discrete Mathematics and Analysis

Problem 1 / Counting

Nondecreasing sequences

For positive integers 1 ≤ k ≤ n, show that the number of nondecreasing sequences a₁ ≤ a₂ ≤ ⋯ ≤ a_k, where a₁, a₂, …, a_k are chosen from {1, 2, …, n}, is exactly n+k−1 k .

Problem 2 / Arithmetic structure

Partitioning the integers by progressions

For integers a > 1 and b, let P_a,b = { an + b : n ∈ ℤ }. Can ℤ be partitioned into finitely many pairwise disjoint progressions P_aᵢ,bᵢ, with pairwise distinct common differences a_i > 1, so that ℤ = ⨆_i=1^r P_aᵢ,bᵢ?

Problem 3 / Counting

Separated k-tuples

Given a finite set S = {1, 2, …, n} and a positive integer k, determine the number of k-tuples (i₁, i₂, …, i_k) such that {i₁, i₂, …, i_k} ⊆ S and i₁ < i₂ < ⋯ < i_k, with the additional separation condition i₂ ≥ i₁ + 2, i₃ ≥ i₂ + 2, …, i_k ≥ i_k-1 + 2.

Problem 4 / Recurrences

Binary strings avoiding 1011

Determine the number of binary strings of length n, where n is a positive integer, that do not contain the substring 1011.

Problem 5 / Asymptotic analysis

A logarithmic series

Determine the real value s such that the series

converges absolutely. Additionally, analyze the rate of convergence and investigate the limit to which the series converges. Bonus points if you can show that, for the particular value of s, the series equals exactly 1 − ¹⁄₂ log(2π).

Problem 6 / Information and observation

One round, three outcomes

In an idealized testing puzzle, there are 5000 bottles of wine, exactly one of which is poisoned. Determine the minimum number of prisoners needed to identify that bottle with certainty under the following rules.

• There is one simultaneous round of testing, at time zero. For each prisoner and each bottle, choose an amount of 0, 5, or 10 mg. Samples may be mixed, and there is no limit on the total volume consumed.
• Exactly one hour later, each prisoner's recorded outcome depends only on the amount received from the poisoned bottle: 0 mg means healthy; 5 mg means sick but alive; 10 mg means dead. All other wine has no effect in this model.
• These three outcomes are the only observations available. No onset times or other measurements can be used, and no further testing round is allowed.

Give both a strategy and a proof that fewer prisoners cannot suffice.

Timing variant

Keep the same 5000 bottles and exactly one poisoned bottle, but replace the testing and observation rules by the following.

• Each bottle is tested exactly once: assign it to a prisoner and administer exactly 5 mg at a chosen time within the first ten minutes. A prisoner may receive samples from many bottles, with no limit on the total volume consumed. All unpoisoned wine has no effect.
• The prisoner who receives the poisoned sample becomes sick exactly sixty minutes after receiving that sample, and not earlier. The onset time is observed exactly. Sample times may be arbitrary real numbers, with no minimum spacing.
• All sample times and assignments are chosen before testing starts. The poisoned bottle must be identified with certainty by seventy minutes after the start.

Determine the minimum number of prisoners in this model, giving a strategy and a matching lower bound. Compare the two models and explain why the bound of at most 3^r outcome vectors for r prisoners does not apply to the timing variant.