Frobenius coin problem (Sylvester's theorem)

[6/83%]

Show

LaTeX

Show LaTeX

Problem 1.26 from Pólya G., Szegő G. "Problems and Theorems in Analysis" [PóSz98]More problems in Section 1 "Additive Number Theory, Combinatorial Problems, and Applications"

Let $a$ , $b$ and $n$ be positive integers, $a$ and $b$ relatively prime to each other. The number of non-negative integral solutions of the equation

ax+by=n

is equal to $\left[\frac{n}{ab}\right]$ or $\left[\frac{n}{ab}\right]+1$ .

Remark.

More may be less: to prove a more general or a more precise theorem may be less trouble. [Proposition by P. Paoli; cf. Intermédiaire des mathématiciens Vol. 1, p. 247-248 (1894). Ch. Hermite, Problem: Nouv. Annls Math. Ser. 1, Vol. 17, p. 32 (1858). Solved by L. Rassicod: Nouv. Annls Math. Ser. 1, Vol. 17, p. 126-130 (1858).]

Problem 1.27 from Pólya G., Szegő G. "Problems and Theorems in Analysis" [PóSz98]More problems in Section 1 "Additive Number Theory, Combinatorial Problems, and Applications"

Let $a_1, a_2, \ldots , a_l$ be positive integers without a common factor different from 1 and $A_n$ be the number of non-negative integral solutions of

a_1 x_1 + a_2 x_2 + a_3 x_3 + \cdots + a_l x_l = n .

Then we have

\lim _{n \rightarrow \infty } \frac{A_n}{n^{l-1}} = \frac{1}{a_1 a_2 \cdots a_l (l-1)!} .

Remark.

Cf. Laguerre: Oeuvres, Vol. 1. Paris: Gauthier-Villars 1898, pp. 218-220.

Problem 1.27.1 from Pólya G., Szegő G. "Problems and Theorems in Analysis" [PóSz98]More problems in Problem 1.27 "[NO TITLE]"

(continued). We suppose more: we assume that $a_i$ and $a_j$ are relatively prime whenever $i \neq j$ . Then we can assert more:

A_n = P(n) + Q_n ,

where $P(x)$ is a polynomial with rational coefficients of degree $l-1$ and the sequence $Q_n$ is periodical with the period $a_1 a_2 \cdots a_l$ :

Q_{n+a_1 a_2 \cdots a_l} = Q_n .

Remark.

Cf. E. Netto: Lehrbuch der Combinatorik, 2nd Ed. Leipzig and Berlin: B. G. Teubner 1927, pp. 319-320.

Problem 1.27.2 from Pólya G., Szegő G. "Problems and Theorems in Analysis" [PóSz98]More problems in Problem 1.27 "[NO TITLE]"

(continued). In the particular case 26 where $l=2$ , $a_1=a$ , $a_2=b$

A_n \leq 1, \quad \text{when } n < ab ,

A_n \geq 1, \quad \text{when } n > ab-a-b ,

$A_{ab}=2$ , $A_{ab-a-b}=0$ and generally

A_{n+ab} = A_n + 1 .

Problem 0.32 from Gallian J.A. "Contemporary Abstract Algebra" [Gal21]More problems in Chapter 0 "Preliminaries"

What is the largest bet that cannot be made with chips worth $7.00 and $9.00? Verify that your answer is correct with both forms of induction.

Problem 2.8.9 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 2.8 "Pumping Lemmas"

(a)(b)

(a)

Is the language $\left\{ 0^{3 m+4 n} \mid m, n \geq 0\right\}$ regular? Prove your answer.

(b)

Let $L$ be a language over alphabet $\left\{ 0\right\}$ . Show that $L^{*}$ is regular. [Hint: Prove and use the fact that if $a$ and $b$ are relatively prime natural numbers, then for any integer $n \geq a b$ , there exist nonnegative integers $u$ and $v$ such that $n=u a+v b$ .]

References

[PóSz98] Pólya G., Szegő G. Problems and Theorems in Analysis. Springer, 1998.

[Gal21] Gallian J.A. Contemporary Abstract Algebra. 10th ed., CRC Press, 2021.

[DuKo01] Du D., Ko K. Problem Solving in Automata, Languages, and Complexity. John Wiley & Sons, 2001.