7
$\begingroup$

Part (a): How many positive integers are there whose digits strictly increase from left to right? (For example, $28$, $13589$, and $4$ are all such integers. "Strictly" means no two digits can be equal, so $15668$ wouldn't count.)

Part (b): Among the positive integers whose digits strictly increase from left to right, how many have at most one even digit?

I don't know how to start part (a) but for part (b) I think I can just choose 1 of the digits to be even and there are 5 choices (0, 2, 4, 6 ,8), unless the first digit is even, then there is no 0.

$\endgroup$
  • 3
    $\begingroup$ For part (b) I think you also need to consider where to place the even digit $\endgroup$ – 132479 Jul 12 at 18:04
  • 1
    $\begingroup$ If 0 is the first digit, then it will be omitted in the standard form of the number. If 0 appears elsewhere, then all the digits to the left of it must be smaller than 0. $\endgroup$ – Acccumulation Jul 13 at 3:11
  • $\begingroup$ What have you tried explicitly for (a)? Where are you stuck? See How to ask a good question. $\endgroup$ – Saad Jul 14 at 2:40
5
$\begingroup$

Selecting a positive integer whose digits increase strictly from left to right is the same thing as selecting a non-empty subset $A$ of $\{1,\dots, 9\}$. Simply arrange the elements of $A$ in increasing order. So the answer to your first question is $2^9 - 1 = 511$.

For the second part, selecting a number of the required form is the same thing as selecting a subset $A$ of $\{1, 3, 5, 7, 9 \}$ and a subset $B$ of $\{2, 4, 6, 8\}$, subject to the conditions $\operatorname{Card}(B) \leq 1$ and $A \cup B \ne \varnothing$. Thus we find that there are $5 \cdot 2^5 - 1 = 159$ numbers that answer the question.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

The maximum length of such a number is $9$ (why?), so you can answer the first question by figuring out how many such numbers there are of each length from $1$ through $9$. HINT: For a given set of, say, $5$ different digits, how many ways are there to arrange those digits to form a number whose digits increase from left to right?

The second part is a bit trickier: you’ll have to take into account not only which even digit you’re using, but also where in the number it occurs. And where it can’t occur: can $2$ be anything but the first or second digit, for instance?

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ While summing the binomial coefficients can get to the right answer, it's overly complicated. $\endgroup$ – Acccumulation Jul 13 at 2:50
  • $\begingroup$ @Acccumulation: Of course. And if one actually thinks about that hint, one will realize that it is not in fact necessary to make a division into cases based on length. But I think that the hint is more likely to be helpful if the OP does first think about specific lengths, and in this case I did not want to offer more than a hint. $\endgroup$ – Brian M. Scott Jul 13 at 3:03
3
$\begingroup$

So for part (a), you just need to know the number of nonempty subsets of $\{1,\ldots,9\}$, which is $2^9-1$. For part (b), it is sufficient to first count the number of subsets of $\{3,5,7,9\}$ from which you subtract $1$ from one of the numbers. This is $$\binom{4}{1}+2\binom{4}2+3\binom 43+4\binom 44$$ Then, allowing $1$, we have $1$ as the first digit and subtract $1$ from one of the following digits. To get the total we just double the preceding number, to get $$2\binom 41+4\binom 42+6\binom 43+8\binom 44$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.