Le 4 mai 2021, la plateforme Yahoo Questions/Réponses fermera. Elle est désormais accessible en mode lecture seule. Aucune modification ne sera apportée aux autres sites ou services Yahoo, ni à votre compte Yahoo. Vous trouverez plus d’informations sur l'arrêt de Yahoo Questions/Réponses et sur le téléchargement de vos données sur cette page d'aide.
10-digit numbers divisible by 11111?
How many 10-digit numbers have all distinct digits and are multiples of 11111?
Very nice work, Jacob! Those were my thoughts exactly for the latter half of the problem!
I know of another way to start the problem up to the point where we show the sum of the first 5-digit part and the second 5-digit part must be 99999, but I'll leave that up for discussion.
Since no one else has posted yet, I'll offer an alternate partial solution:
We note that the sum of the digits of the 10-digit number must be 45 seeing how each digit appears once. Since 9|45 we determine that the 10-digit number is divisible by 9. Thus the number, n, is divisible by 99999. Breaking up n into its first 5 digits (x) and second 5 digits (y), we can write
n = (10^5)x + y
n = 99999x + (x + y).
Clearly, x+y must be a multiple of 99999. Since they are both 5-digit (or 4-digit in the case of y) numbers each less than 99999, they cannot equal any multiple of 99999 other than 99999 itself. Now we can finish in the way Jacob did.
Note that we could have also used a mod argument to deduce x+y is a multiple of 99999.
Since no one else has posted yet, I'll offer an alternate partial solution:
We note that the sum of the digits of the 10-digit number must be 45 seeing how each digit appears once. Since 9|45 we determine that the 10-digit number is divisible by 9. Thus the number, n, is divisible by 99999. Breaking up n into its first 5 digits (x) and second 5 digits (y), we can write
n = (10^5)x + y
n = 99999x + (x + y).
Clearly, x+y must be a multiple of 99999. Since they are both 5-digit (or 4-digit in the case of y) numbers each less than 99999, they cannot equal any multiple of 99999 other than 99999 itself. Now we can finish in the way Jacob did.
Note that we could have also used a mod argument to deduce x+y is a multiple of 99999.
2 réponses
- il y a 1 décennieRéponse favorite
Answer: 3456 (or 3840 if leading zeros are permitted)
I will begin by proving by induction that a 10-digit number (allowing leading 0s) is divisible by 11111 if the sum of the number formed by the first five digits and the number formed by the last five digits is divisible by 11111 (1).
Base case: this is clearly true for 0000011111.
Inductive step: suppose 10-digit number k = "abcdefghij" is divisible by 11111 and "abcde"+"fghij" is divisible by 11111.
Suppose k+11111 also has 10 digits and let k+11111 = "lmnopqrstu". Now either "fghij" <= 88888 or "fghij" >= 88889. If "fghij" <= 88888, "fghij"+11111 <= 99999 so "pqrstu" = "fghij"+11111 and thus "lnmop"+"qrstu" = "abcde"+"fghij"+11111 so "lnmop"+"qrstu" is divisible by 11111 since "abcde"+"fghij" is divisible by 11111. If "fghij" >= 88889, "fghij"+11111 >= 1000000 so "lmnop" = "abcde"+1 and "qrstu" = "fghij"-88889 and thus "lmnop"+"qrstu" = "abcde"+1+"fghij"-88889 = "abcde"+"fghij"-88888 so "lmnop"+"qrstu" is divisible by 11111 since "abcde"+"fghij" is divisible by 11111. So in either case "lmnop"+"qrstu" is divisible by 11111.
So statement (1) is true for the first multiple of 11111, and if it is true for one multiple of 11111 then it is true for the next multiple of 11111 if it still has 10 digits, therefore by induction statement (1) is true for all 10-digit numbers.
EDIT: See note at bottom
Now if a 10-digit number divsible by 11111, x = "abcdefghij" has all distinct digits, then it contains each of the digits 0-9 exactly once and so the sum of its digits is 45, so the sum of the digits of "abcde"+"fghij" is 45. Now a 10-digit number has its digits maximised when it is 9999999999 so "abcde"+"fghij" <= 99999+99999 = 18*11111. So "abcde"+"fghij" = 1*11111 or 2*11111 or ... or 18*11111. But the only 2 of these whose digits total 45 are 99999 and 199998. But it cannot be 199998 because then x = 9999999999 which does not have all distinct digits. So "abcde"+"fghij" = 99999.
This means that e+j = 9 so d+i = 9 so c+h = 9 so b+g = 9 so a+f = 9. Now consider how many ways there are of choosing each digit given these restrictions. Before the others are chosen, a can be any of the 10 digits. Then once a is chosen, b can be any of the remaining 9 digits but not the one digit x such that a+x = 9 because this must be one of f, g, h i or j, so there are 8 possible options for b. Continuing this process gives 10*8*6*4*2 = 3840 ways of choosing a, b, c, d and e. But once these are chosen f, g, h, i and j are given by the relationships above.
So there are a total of 3840 10-digit numbers which have all distinct digits and are multiples of 11111.
Not counting numbers with a leading zero, there are 9 rather than 10 options for a giving a total of 9*8*6*4*2 = 3456 10-digit numbers which have all distinct digits and are multiples of 11111.
EDIT: I have realised that I also need to show the converse of statement (1) for the rest of the proof to follow, since all the deductions must be *if and only if* the 10-digit number is divisible by 11111, so that all the numbers we are looking for are to be found, and all the numbers to be found are ones we are looking for. To do this I will prove a stronger version of statement (1) that a 10-digit number (allowing leading 0s) is congruent to the sum of the number formed by the first five digits and the number formed by the last five digits, modulo 11111, also by induction.
Base cases: clearly true for 0000000001, 0000000002, ... 0000011111 (i.e. each integer, modulo 11111).
Inductive step: following the same reasoning as in the inductive step in the proof above, if k = "abcdefghij" and k+11111 = "lmnopqrstu" then "lmnop"+"qrstu" = "abcde"+"fghij"+11111 or "abcde"+"fghij"-88888, so if k is congruent to "abcde"+"fghij" (mod 11111), then k+11111 is congruent to "lmnop"+"qrstu" (mod 11111).
This shows that if a 10-digit number "abcdefghij" is not divisible by 11111, then neither is "abcde"+"fghij", which is the converse of statement (1).
- Anonymeil y a 5 ans
No, iceman is physically powerful. After the 1st digit, you have honestly picked 2, on the grounds that the different digit is implied. So there at the instant are in basic terms 8 to choose from. At each and each p.c.., you're choosing a pair, it is why the kind of judgements is going down by utilising 2 at each and each step.
