Question 1210714: For a nonnegative integer n, let r_9(n) stand for the remainder left when n is divided by 9. For example, r_9(25)=7.
What is the 22nd entry in an ordered list of all nonnegative integers n that satisfy r_9(5n)≤4?
(Note that the first entry in this list is 0.)
Found 2 solutions by ikleyn, greenestamps:
Answer by ikleyn(54057)   (Show Source):
You can put this solution on YOUR website! .
For a nonnegative integer n, let r_9(n)  stands for the remainder left when n is divided by 9.
For example, r_9(25)=7.
What is the 22nd entry in an ordered list of all nonnegative integers n that satisfy r_9(5n)≤4?
(Note that the first entry in this list is 0.)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In standard mathematical designations, r_9(n) is nothing else as n mod 9,
so r_9(5n) is precisely 5n mod 9.
Thus, in this problem, in the input, we have nonnegative integers n = 0, 1, 2, 3, . . . ,
and we mark in this list those numbers 'n', for which the remainders 5n mod 9 are between 0 and 4, inclusive.
+--------------------------------------------------------------+
| Now the problem asks which number is in 22-nd position |
| among marked numbers in the input list. |
+--------------------------------------------------------------+
For the solution, let's consider the input numbers as separate sets of 9 numbers each
set 1: 0, 1, 2, 3, 4, 5, 6, 7, 8;
set 2: 9, 10, 11, 12, 13, 14, 15, 16, 17;
set 3: 18, 19, 20, 21, 22, 23, 24, 25, 26;
and so on.
The numbers 'n' from set 1 produce the remainders 5n mod 9.
Since the factor 5 and the number 9 are mutually prime, the remainders 5n mod 9 are 9 different numbers
between 0 and 8 inclusive. Hence, these remainders represent all integer numbers from 0 to 8,
and each such number is presented precisely once by these remainders.
Hence, set 1 creates precisely 5 (five) remainders from 0 to 4 inclusive -
- so, set 1 has precisely 5 marked numbers in the input.
For us now, it does not matter what individual numbers are marked - the only thing that matters is that
set 1 contributes precisely 5 elements to the marked input set.
The same logic works for set 2. Let me reproduce it for clarity, word for word as above.
The numbers 'n' from set 2 produce the remainders 5n mod 9.
Since the factor 5 and the number 9 are mutually prime, the remainders 5n mod 9 are 9 different numbers
between 0 and 8 inclusive. Hence, these remainders represent all integer numbers from 0 to 8,
and each such number is presented precisely once by these remainders.
Hence, set 2 creates precisely 5 (five) remainders from 0 to 4 inclusive -
- so, set 2 has precisely 5 marked numbers in the input.
For us now, it does not matter what individual numbers are marked - the only thing that matters is that
set 2 contributes precisely 5 elements to the marked input set.
So far, we have 5 + 5 = 10 marked numbers in the union of set 1 and set 2.
OK, very good.
Now it is clear how to proceed further with this problem.
Due to the same logic, set 3 contributes 5 marked numbers,
making the total marked numbers 15 in the union set 1 U set 2 U set 3.
Due to the same logic, set 4 contributes 5 marked numbers,
making the total marked numbers 20 in the union set 1 U set 2 U set 3 U set 4.
So, now we should analyze what numbers are 21-th and 22-nd marked numbers in set 5.
Set 5 is {36, 37, 38, 39, 40, 41, 42, 43, 44}.
5*36 mod 9 is 0 (zero). It is between 0 and 4, so 36 is the 21-th marked number in the input list.
5*37 mod 9 is 5 (five). It is not between 0 and 4, so 37 is an unmarked number in the input list.
5*38 mod 9 is 1 (one). It is between 0 and 4, so 38 is the 22-nd marked number in the input list.
At this point, the solution is complete.
ANSWER. The 22-nd marked number in the input list is 38.
//////////////////////////////////////
comment from student: Thanks for helping me. You are making a difference in the world. :)
My response: Thanks for your comment.
Comments like this work well, they're encouraging, and they give volunteers like me the energy to keep educating others.
But you regularly post your positive comments to me in private (invisible) mode.
In this mode, only I can see them; for all others, they are invisible.
So, these comments would work even better if you posted them in visible mode.
It does not make sense to hide positive comments/reviews.
Answer by greenestamps(13390)  (Show Source):
You can put this solution on YOUR website!
The required condition is that (5n) mod 9 is less than or equal to 4.
Consider the value of (5n) mod 9 for values of n of the forms 9k, 9k+1, ..., and 9k+8 where k is a whole number.
form of n value of (5n) mod 9
---------------------------------
9k 0
9k+1 5
9k+2 1
9k+3 6
9k+4 2
9k+5 7
9k+6 3
9k+7 8
9k+8 4
We see that the condition is satisfied for values of n of any of the 5 forms 9k, 9k+2, 9k+4, 9k+6, and 9k+8.
We are looking for the 22nd smallest value of n that satisfies the condition.
In each set of 9 consecutive values of 9, 5 of the 9 numbers satisfy the condition. So the first 4*9 = 36 values of n (corresponding to k=0, 1, 2, and 3) will contain 4*5 = 20 numbers that satisfy the condition. That means the 2nd number with k=4 will be the 22nd number in our list.
So the number we are looking for is 9k+2 when k is 4.
ANSWER: 9(4)+2 = 38
| |
|
