A Number That Likes To Grumble
How many four digit numbers are there such that each digit is not larger than the previous digit?
Notes: The number "that likes to grumble" is consisted of only natural numbers (0 is not included)
Examples of numbers that likes to grumble:
4321 - each digit is smaller than the neighbouring left digit
4444 - each digit is smaller or is the same as the digit to the left
Number 9788 is not satisfying only because 788 (7 is smaller than eights to the right)
Number 3210 is not satisfying as well, because of 0 (non-natural number)
Bonus: Generalize for n -digit numbers. Special thanks to Jon Haussmann.
The answer is 495.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
First of all, a very nice method!!
But, I don't see how this method counts the numbers that have a zero in them.
For example the number 6530 satisfies the given properties but is not counted in your method.
Actually you could have started with 13 rectangles and fill a red dot in 9 of them. In this case the number in an empty rectangle would be the number of red dots to the right of it.
So the answer should be,
( 9 1 3 ) − 1 = 7 1 4
(1 is subtracted because the number 0 0 0 0 is not a 4 digit number.)
Log in to reply
it can easily be solved by using dynamic programming when you dont get that kind of idea ^_^
but i got 714 .__.
The problem maker's intention is to construct the number from right to left(unit digit to the forth), but I agree that the problem is a bit ambiguous without specifying this.
Log in to reply
But in the solution given by the problem maker, he has considered the number 6 5 3 3 as an acceptable number. This means he is constructing the number from left to right.
Anyway you are right, if the numbers were to be constructed from right to left we would get 495 as the answer.
Log in to reply
@Nitish Joshi – Ah..I see. I have already filed a report for the problem. Let's hope that gets the problem maker's attention. It does appear that he/she ignored 0 .
@Nitish Joshi firstly, you are completely right. For some reason, I think the text of my problem was much longer. Very much longer indeed. But now, somehow my problem only has two paragraphs. I think I wrote the problem with 5 or 6 of them.
Therefore, brilliant problem solvers, take my sincerest apologies. I now added the part where it is specified that zero shall not be included.
Now after editing, my problem seems a little bit like it used to be, with 10+ rows of text and explanation.
Log in to reply
What about those who entered 714 as the answer but did not get the points for correct answer because of your previously incorrect question?
Log in to reply
@Asad Bhai – At first, my problem stated everything clearly. After some time, the text of the problem has changed (I am not the one who changed it, I guess that brilliant staff or someone with that kind of authority did it). After that, this happend. I do not know how to solve this appropriately.
One way is to delete this problem and write it again, with the updated text, so that everyone can do it again. As I imagined it. With this current text.
Other option is to write another problem, similar to this one, where null is included. Of course, with the text that will explain what is asked.
Third option, do option one and two. Since problems with null and without null are different and both are good. So it is not a bad idea to give both, perhaps.
Fourth option (don't know if it is possible), that I and others ask from brilliant to take certain number of my points and give it to brilliant members that did not solve this problem due to its temporary incorrectness.
I am ready to solve this complication if that is possible.
Why not do it this way? First assume that all the digits are distinct. Total 10C4 numbers and each number can be arranged in only one way possible. eg: 4,9,6,7-these digits can be arranged in only one way possible i.e. 9674. Hence, such 10C4 numbers are possible. Now assume that one of the digit is repeated i.e. 3 digits are distinct. Hence 10C3 numbers possible and each set of 4 numbers can only be arranged in one way possible. eg: 1,2,2,9 can be arranged only in one way possible i.e. 9221. Similarly if two digits are repeated i.e. two digits are distinct there will be 10C2 numbers and if only one digit is used then 10C1 numbers. The answer should hence be 10C4+10C3+10C2+10C1=385 which is not the answer given. Can you please tell me what is wrong in my method?
Log in to reply
some numbers can be arranged as 2 different arrangement , you only count them as 1
Very nice way of thinking @Rohit Gilbert . Using your method I have managed it to get to the solution. I must say that I am not sure what 10C4 stands for, but I suppose it is the same as: ( 1 0 4 )
To begin with, you should have done that with 9 up instead of 10 (numbers from 1 to 9, zero is not included).
Now when zero is not included, you have skipped few steps.
When all 4 digits are distinct, number of "grumbling numbers" is: ( 9 4 ) = 1 2 6
When we have 3 distinct numbers (meaning, one number will appear twice, other two only once). There are: ( 9 2 ) × 7 = 2 5 2 . - because, two one-time-showing-digits can be chosen on ( 9 2 ) (it is totally the same if we have chosen 1, 2 or 2, 1 for digits that appear once) and the digit that appears twice can be chosen from the rest, which is 7.
When we have 2 distinct digits we have two cases:
FIRST: both digits appear twice (number 2211). There are ( 1 0 4 ) = 3 6
SECOND: One digit appears three times, other one once (number 3331). Three-time-showing can be chosen on 9 ways, other one can be chosen from the remaining, which is 8. ( 7 2 combinations)
Lastly, one digit appears 4 times (numbers 1111, 2222....). 9 numbers are like that.
Conclusion: 1 2 6 + 2 5 2 + 3 6 + 7 2 + 9 = 4 9 5
Log in to reply
Thank you very much Milan Milanic . I understood my mistake
My solution is a little bit different from Milan's method.
The idea for a generic n -digit number is: a Grumble's number has x 1 digits 1 , x 2 digits 2 , . . . , x 9 digits 9 from right to left.
So, the number of Grumble's numbers of length n is the same as the number of natural solutions of
x 1 + x 2 + . . . + x 9 = n and that number is ( 8 n + 8 )
For n = 4 we have the solution 4 9 5
Solution:
This problem can be seen from a little different perspective. As the image above suggests, we have 12 rectangles, in which we will put either a number or a red dot (it is very important that the colour is red). Also, it is crucial that we put exactly four numbers (to get a four digit number) and the rest are red dots (8 of them). We can only choose position of a number, but not a number itself (e.g. we can decide to place a number on position no. 2, but we cannot choose a number itself to be 3 or any other).
That is because number will be calculated by certain formula: 1 + N u m b e r O f R e d D o t s R i g h t
So, we can place 8 identical red dots in 12 places in ( 1 2 8 ) different ways. After placing dots, numbers will be calculated by the formula. Solution is: 4 9 5
If anything is left unclear, write a comment.
Example:
On position 8 and 9, a number 3 will be placed (1 + 2 dots on positions 10 and 11).
On position 5 number 5 will be placed (1 + 2 dots right + 2 dots at the rightmost)
On position 3 number 6 will be placed.
In this manner we will get the number 6 5 3 3 and this way, we will surely receive only numbers that satisfy all the given conditions.