Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 AMC 10B Problems/Problem 16"

(→‎Solution 1)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Define an <math>upno</math> to be a positive integer of 2 or more digits where the digits are strictly
+
Define an <math>\textit{upno}</math> to be a positive integer of <math>2</math> or more digits where the digits are strictly
−
increasing moving left to right. Similarly, define a <math>downno</math> to be a positive integer  
+
increasing moving left to right. Similarly, define a <math>\textit{downno}</math> to be a positive integer  
−
of 2 or more digits where the digits are strictly decreasing moving left to right. For
+
of <math>2</math> or more digits where the digits are strictly decreasing moving left to right. For
−
instance, the number 258 is an upno and 8620 is a downno. Let 𝑈 equal the total
+
instance, the number <math>258</math> is an upno and <math>8620</math> is a downno. Let <math>U</math> equal the total
−
number of <math>upnos</math> and let 𝑑 equal the total number of <math>downnos</math>. What is |𝑈 − 𝐷|?
+
number of <math>upnos</math> and let <math>d</math> equal the total number of <math>downnos</math>. What is <math>|U-D|</math>?
 +
 
 
== Solution 1 ==
 
== Solution 1 ==
−
<math>D</math> is greater than <math>U</math> because <math>upno</math> can't start with <math>0</math>.
+
 
−
So the differences are in the form <math>x0</math>.
+
First, we know that <math>D</math> is greater than <math>U</math>, since there are less upnos than downnos. To see why, we examine what determines an upno or downno.
−
When <math>x</math> has length <math>k</math> we have  <math>{9 \choose k}.</math>
+
 
−
The number of possible <math>x = \sum_{k=1}^9 {9 \choose k} = \sum_{k=0}^9 {9 \choose k} - {9 \choose 0} = 2^9-1 = \textbf{511}</math>.
+
We notice that, given any selection of unique digits (notice that "unique" constrains this to be a finite number), we can construct a unique downno. Similarly, we can also construct an upno, but the selection can not include the digit <math>0</math> since that isn't valid.
 +
 
 +
Thus, there are <math>2^{10}</math> total downnos and <math>2^9</math> total upnos. However, we are told that each upno or downno must be at least <math>2</math> digits, so we subtract out the <math>0</math>-digit and <math>1</math>-digit cases.  
 +
 
 +
For the downnos, there are <math>10</math> <math>1</math>-digit cases, and for the upnos, there are <math>9</math> <math>1</math>-digit cases. There is <math>1</math> <math>0</math>-digit case for both upnos and downnos.
 +
 
 +
Thus, the difference is <math>\left(\left(2^{10}-10-1\right)-\left(2^9-9-1\right)\right)=2^9-1=\textbf{(E) }511.</math>  
  
 
~Technodoggo ~minor edits by lucaswujc
 
~Technodoggo ~minor edits by lucaswujc

Revision as of 20:26, 15 November 2023

Problem

Define an $\textit{upno}$ to be a positive integer of $2$ or more digits where the digits are strictly increasing moving left to right. Similarly, define a $\textit{downno}$ to be a positive integer of $2$ or more digits where the digits are strictly decreasing moving left to right. For instance, the number $258$ is an upno and $8620$ is a downno. Let $U$ equal the total number of $upnos$ and let $d$ equal the total number of $downnos$. What is $|U-D|$?

Solution 1

First, we know that $D$ is greater than $U$, since there are less upnos than downnos. To see why, we examine what determines an upno or downno.

We notice that, given any selection of unique digits (notice that "unique" constrains this to be a finite number), we can construct a unique downno. Similarly, we can also construct an upno, but the selection can not include the digit $0$ since that isn't valid.

Thus, there are $2^{10}$ total downnos and $2^9$ total upnos. However, we are told that each upno or downno must be at least $2$ digits, so we subtract out the $0$-digit and $1$-digit cases.

For the downnos, there are $10$ $1$-digit cases, and for the upnos, there are $9$ $1$-digit cases. There is $1$ $0$-digit case for both upnos and downnos.

Thus, the difference is $\left(\left(2^{10}-10-1\right)-\left(2^9-9-1\right)\right)=2^9-1=\textbf{(E) }511.$

~Technodoggo ~minor edits by lucaswujc

Solution 2

Since Upnos do not allow 0s to be in their first -- and any other -- digit, there will be no zeros in any digits of an Upno. Thus, Upnos only contain digits [1,2,3,4,5,6,7,8,9].

Upnos are 2 digits in minimum and 9 digits maximum (repetition is not allowed). Thus the total number of Upnos will be (9C2)+(9C3)+(9C4)+...+(9C9), since every selection of distinct numbers from the set [1,2,3,4,5,6,7,8,9] can be arranged so that it is an Upno. There will be (9C2) 2 digit Upnos, (9C3) 3 digit Upnos and so on.

Thus, the total number of Upnos will be (9C2)+(9C3)+(9C4)+...+(9C9) = 2^9-(9C0)-(9C1) = 512 - 10 = 502.

Notice that the same combination logic can be done for Downnos, but Downnos DO allow zeros to be in their last digit. Thus, there are 10 possible digits [0,1,2,3,4,5,6,7,8,9] for Downnos.

Therefore, it is visible that the total number of Downnos are (10C2)+(10C3)+(10C4)+...+(10C10) = 2^10-(10C0)-(10C10) = 1024 - 11 = 1013.

Thus abs(#Upno-#Downno) = abs(1013-502) = 511.


~yxyxyxcxcxcx


Solution 3

Note that you can obtain a downo by reversing an upno (like $235$ is an upno, and you can obtain $532$). So, we need to find the amount of downos that end with 0. We can use stars and bars to get: \[\sum_{n=0}^9 \dbinom{9}{n} = \dbinom{9}{0} + \dbinom{9}{1} + \cdots + \dbinom{9}{9}\] to get 512. However, 0 is not a valid case so we subtract 1. Our answer is 511.

-aleyang

-ap246(LaTeX)

Solution 4 (Educated Guess)

First, note that the only $downnos$ that are not contained by the set of $upnos$ is every $downno$ that ends in $0$.

Next, listing all the two digits $downnos$, we find that the answer is more than 9, since there are more digits to be tested and there are 9 two digit $downnos$. This leaves us with $512$ or $511$.

Next, we notice that all the possibilities for $2$ through $9$ digit $downnos$ ending in $0$ pair up with one another, as the possibilities are equal (e.g. possibilities for $2$ digits = possibilities for $9$ digits, etc.).

This leaves us with one last possibility, the ten digit $downno 9876543210$.

Since all the previous possibilities form an even number, adding one more possibility will make the total odd. Therefore, we need to choose the odd number from the set $[511, 512]$.

Our answer is 511.

~yourmomisalosinggame (a.k.a. Aaron)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AMC_10B_Problems/Problem_16&oldid=203661"