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 2)
(→‎Solution 4)
Line 5: Line 5:
 
instance, the number 258 is an upno and 8620 is a downno. Let 𝑈 equal the total
 
instance, the number 258 is an upno and 8620 is a downno. Let 𝑈 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 𝑑 equal the total number of <math>downnos</math>. What is |𝑈 − 𝐷|?
−
== Solution ==
+
== Solution 1 ==
 
<math>D</math> is greater than <math>U</math> because <math>upno</math> can't start with <math>0</math>.
 
<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>
 
So the differences are in the form <math>x0</math>
Line 13: Line 13:
 
~Technodoggo
 
~Technodoggo
  
−
== Solution ==
+
== 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].  
 
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].  
Line 34: Line 34:
  
  
−
== Solution 2 ==
+
== Solution 3 ==
  
 
Note that you can obtain a downo by reversing an upno (like <math>235</math> is an upno, and you can obtain <math>532</math>). So, we need to find the amount of downos that end with 0. We can use stars and bars to get: <cmath>\sum_{n=0}^9 \dbinom{9}{n} = \dbinom{9}{0} + \dbinom{9}{1} + \cdots + \dbinom{9}{9}</cmath> to get 512. However, 0 is not a valid case so we subtract 1. Our answer is 511.
 
Note that you can obtain a downo by reversing an upno (like <math>235</math> is an upno, and you can obtain <math>532</math>). So, we need to find the amount of downos that end with 0. We can use stars and bars to get: <cmath>\sum_{n=0}^9 \dbinom{9}{n} = \dbinom{9}{0} + \dbinom{9}{1} + \cdots + \dbinom{9}{9}</cmath> to get 512. However, 0 is not a valid case so we subtract 1. Our answer is 511.
Line 41: Line 41:
  
 
-ap246(LaTeX)
 
-ap246(LaTeX)
 +
 +
== Solution 4 (Educated Guess) ==
 +
 +
First, note that the only <math>downnos</math> that are not contained by the set of <math>upnos</math> is every <math>downno</math> that ends in <math>0</math>.
 +
 +
Next, listing all the two digits <math>downnos</math>, we find that the answer is more than 9, since there are more digits to be tested and there are 9 two digit <math>downnos</math>. This leaves us with <math>512</math> or <math>511</math>.
 +
 +
Next, we notice that all the possibilities for <math>2</math> through <math>9</math> digit <math>downnos</math> ending in <math>0</math> pair up with one another, as the possibilities are equal (e.g. possibilities for <math>2</math> digits = possibilities for <math>8</math> digits, etc.).
 +
 +
This leaves us with one last possibility, the ten digit <math>downno 9876543210</math>.
 +
 +
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 <math>[511, 512]</math>.
 +
 +
Our answer is 511.

Revision as of 18:54, 15 November 2023

Problem

Define an $upno$ to be a positive integer of 2 or more digits where the digits are strictly increasing moving left to right. Similarly, define a $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 𝑈 equal the total number of $upnos$ and let 𝑑 equal the total number of $downnos$. What is |𝑈 − 𝐷|?

Solution 1

$D$ is greater than $U$ because $upno$ can't start with $0$. So the differences are in the form $x0$ When x has length $k$ we have ${9 \choose k}.$ The number of possible $x = \sum_{k=1}^9 {9 \choose k} = \sum_{k=0}^9 {9 \choose k} - {9 \choose 0} = 2^9-1 = 511$.

~Technodoggo

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 $8$ 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.

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