On my Mind: AMM problem 12377

This is my first post (or second, depending on how you look at the world). For this, I decide to post the first AMM problem I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

We define a one-drop number as in problem 12377 from Problems and Solutions, The American Mathematical Monthly, Volume 130, 2023, Issue 3.

An integer is a one-drop number if its decimal digits $d_{1}, \dots, d_{n}$ satisfy

$1 \leq d_{1} \leq d_{2} \dots \leq d_{i} > d_{i + 1} \leq \dots \leq d_{n}$

for some $i$ , with $1 \leq i < n$ .

For example, the numbers $13802$ and $49557$ are one-drop numbers, while the numbers $12345$ and $352712$ are not.

We answer the following question: for $n \geq 2$ , how many $n$ -digit one-drop numbers are there?

Solution -

There are

$(\binom{n + 18}{18}) - (\binom{n + 9}{9}) - n \cdot (\binom{n + 8}{8})$

one-drop numbers of length $n \geq 2$ .

The digits of every $n$ -digit one-drop number $d_{1}, \dots, d_{n}$ can be uniquely split into two zero-drop blocks $A$ and $B$ , with digits $1 \leq d_{1} \leq \dots \leq d_{i}$ and $0 \leq d_{i + 1} \leq \dots \leq d_{n}$ . Here, is a zero-drop block consists of a sequence of non-decreasing decimal digits; we allow the leading digit to be $0$ .

Consider all $19$ -tuples $(a_{1}, \dots, a_{9}, b_{0}, b_{1}, \dots, b_{9})$ of non-negative integers such that

$a_{1} + \dots + a_{9} + b_{0} + b_{1} + \dots + b_{9} = n .$

Each tuple represents an $n$ -digit number obtained by concatenating two zero-drop blocks $A$ and $B$ , where $a_{d}$ and $b_{d}$ denote the number of occurrences of the digit $d$ in the respective blocks. Clearly, there are $(\binom{n + 18}{18})$ such tuples. Note that each tuple of this kind represents either a zero-drop or a one-drop number, and each $n$ -digit one-drop number is uniquely represented by such a tuple.

Discard all tuples where the block $A$ is empty, with all $a_{d} = 0$ ; the corresponding number is zero-drop. There are as many such tuples as there are non-negative integer solutions of

$b_{0} + b_{1} + \dots + b_{9} = n,$

that is, $(\binom{n + 9}{9})$ . This leaves $(\binom{n + 18}{18}) - (\binom{n + 9}{9})$ tuples; call this set of tuples $S$ . Note that for any element in $S$ , the block $A$ is non-empty. Thus, it represents a proper $n$ -digit number since the leftmost digit is non-zero.

Suppose that a tuple $(a_{1}, \dots, a_{9}, b_{0}, b_{1}, \dots, b_{9}) \in S$ represents a zero-drop number. Since some $a_{d} > 0$ , the digit $0$ cannot appear in block $B$ , hence the number consists only of digits $1$ through $9$ . There are $(\binom{n + 8}{8})$ such $n$ -digit zero drop numbers, via counting the non-negative integer solutions of

$c_{1} + \dots + c_{9} = n .$

Each of these numbers has been represented by precisely $n$ tuples from $S$ , because the first $i$ digits of such a number can be placed in block $A$ with the remaining digits in block $B$ for all $1 \leq i \leq n$ .

For example, the $5$ -digit zero-drop number $11234$ can be broken into blocks $A, B$ as $1, 1234$ or $11, 234$ or $112, 34$ or $1123, 4$ or $11234, \emptyset$ , each of which correspond to distinct tuples from $S$ .

Thus, precisely $n \cdot (\binom{n + 8}{8})$ tuples from $S$ represent zero-drop numbers. The remaining $(\binom{n + 18}{18}) - (\binom{n + 9}{9}) - n \cdot (\binom{n + 8}{8})$ tuples uniquely represent all $n$ -digit one-drop numbers. $◻$

On my Mind

Search

AMM problem 12377

No comments:

Post a Comment

Introduction to Sumsets II

Get new posts by email: