Tensorgami

Problem Set

Selected Problems in Discrete Mathematics and Analysis

A web edition of a compact exercise sheet, with the PDF retained as the printable version.

Summary

Problems and mechanisms

Six problems organized around counting, arithmetic structure, recurrences, asymptotic cancellation, and finite information.

Web edition

The page records the problem statements in a browsable form while keeping the original PDF available for printing and citation.

Contribution type
Problem set
Format
Web edition; PDF
Subjects
counting, covering systems, recurrences, asymptotic series, finite information encoding
Mechanisms
stars and bars, gap transformations, finite-state recurrences, asymptotic cancellation, ternary outcome coding
PDF TeX source Problem Sets

Web Edition

Problem statements

The statements are presented without solutions, matching the role of the PDF as a compact exercise sheet.

Problem 1 Counting

Nondecreasing sequences

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

Problem 2 Arithmetic structure

Covering the integers by progressions

For a nonzero integer a and an integer b, denote Pa,b = { an + b : n ∈ ℤ }. Is there a finite set of integers a1, b1, …, an, bn with ai ≠ aj for all i ≠ j such that ℤ = ⋃i=1n Paᵢ,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 (i1, i2, …, ik) such that {i1, i2, …, ik} ⊆ S and i1 < i2 < ⋯ < ik, with the additional separation condition i2 ≥ i1 + 2, i3 ≥ i2 + 2, …, ik ≥ ik-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

∑n=1∞ [(n+s) log(1 + 1/n) − 1]

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 2 log 2 + 1⁄2 log π − 1.

Problem 6 Finite information

The poisoned wine problem

Imagine a testing setting with 5000 bottles of wine, exactly one of which is poisoned, and a large number of prisoners available for testing. The goal is to identify the poisoned bottle by giving small amounts of wine to the prisoners.

  • If a prisoner consumes 5 mg of the poisoned wine, they become very sick.
  • If a prisoner consumes 10 mg of the poisoned wine, they die.
  • Each bottle has an essentially unlimited supply of wine.
  • The testing results take one hour to appear, and the poisoned bottle must be identified within one hour and ten minutes.

Given these conditions, what is the minimal number of prisoners needed to identify the poisoned wine bottle?