Jump to content
BrainDen.com - Brain Teasers
  • 0

the biggest self refrential number


BMAD
 Share

Question

3 answers to this question

Recommended Posts

  • 0

6210001000. A self-referential number can't have more than 10 digits, since there are only 10 digits to refer to in the decimal system. The sum of the digits in a self-referential number is always equal to the number of digits, which is 10 in this case. If the first digit is >5, there can be no other digit of that value, so the digit refering to that value must be 1. Then the digit refering to 1 must be >1, and the digit refering to that value must be >0. So we have at least six 0s, at least two 1s, one digit refering to the number of 0s, and one digit refering to the number of 1s. This is at least 10 digits, with equality only if we have exactly six 0s and exactly two 1s. This leads to 6210001000. Any other 10 digit self-referential number, if they exist (which I doubt), must have a first digit <6.

Link to comment
Share on other sites

  • 0

There are seven self-referential numbers in total (in the decimal system). They are 1210, 2020, 21200, 3211000, 42101000, 521001000, and 6210001000. (On a side note we could relax the definition to allow numbers with more than 10 digits if we defined exactly what the 11th and onward digits would represent.) Now for proving that these are the only self-referential numbers.

Notation: A self-referential number with N digits is written d0d1...dN-1. Let Sk be the number of instances of the digit k. By definition, a self-referential number satisfies dk=Sk for all k.

Observation 1: The first digit can never be 0. If d0=0, then the number contains at least one 0, meaning S0>0. But 0=d0=S0>0 is a contradiction.

Observation 2: Some digit must be 0. Otherwise S0=0, which means d0=0, which is impossible.

Observation 3: All digits can not be equal. Follows directly from observations 1 and 2.

Lemma A: A self-referential number d0d1...dN-1 has no digit larger than N-1.

Proof: Suppose dk>N-1 for some k. Then Sk=dk>N-1, which means there are at least N digits k. But there are only N digits total, so all digits are k. This contradicts observation 3.

Lemma B: The digit sum of a self-referential number equals the number of digits.

Proof: d0+d1...+dN-1 = S0+S1...+SN-1 = (number of digits)-(number of digits larger than N-1) = (number of digits) by Lemma A.

Observation 4: The maximal digit sum is 10. Follows from Lemma B and the fact that the maximal number of digits is 10.

Lemma C: No digit except d0 can be larger than 2. My proof for this is very long and ugly.*

Observation 5: Only one digit can be larger than 2. Follows directly from Lemma C.

Lemma D: After the third digit, there can be at most one non-zero digit.

Proof: Suppose dp and dq are both non-zero, where p and q are both larger than 2. Then Sp and Sq are both non-zero, meaning we have both a digit p and a digit q. This contradicts observation 5.

Corollary to Lemma D: If there is a non-zero digit after the third digit, that digit must be 1.

Proof: Suppose dp>1 where p>2. Then Sp>1, meaning there is more than one instance of the digit p. Again, this contradicts observation 5.

Observation 6: There are at most four non-zero digits. The first three digits can be non-zero, and at most one digit after that.

Lemma E: Either d1 or d2 is <2.

Proof: We know that neither is >2 by Lemma C. So we only need to prove that both aren't equal to 2. Suppose they were. Then S1=d1=2, meaning we have two 1s. Only one of them can appear after the third digit by Lemma D. The second and third digit are occupied by 2s. So the first digit must be 1. Now look at the other 1. It represents a single instance of another non-zero digit m>2. This makes five non-zero digits (two 1s, two 2s, and one m), which contradicts observation 6.

Now it's time to break it down:

  1. The case where d0=1. This makes d1=S1>0. Also, d1 can't be 1 since that makes S1>1 which contradicts d1=1. And d1 can't be >2 by Lemma C. So d1=2. We can't have d2=0, and we must have d2<2 by Lemma E. So d2=1. Since we already have the two 1s and the one 2, there can be no more non-zero digits. We only need to put one 0 at the end and we get 1210.
  2. The case where d0=2. This makes d2>0. If d2=1, we can't find a value for d1. It can't be 0 because we already have a digit 1, it can't be 1 because then we would have two digits 1, it can't be two because that would make two digits 2, and it can't be >2 by Lemma C. So d2=2. Now d1 could be either 0 or 1, bringing the solutions 2020 and 21200.
  3. The case where d0>2. Because d0=m for some m>2, we have dm=Sm>0. But by the corollary to Lemma D, such a digit can't be >1. So dm=1. Now d1 can't be 0 or 1, so it must be 2. Now d2 can't be 0 or 2, so it must be 1. This makes four non-zero digits (d0=m, d1=2, d2=1, and dm=1), all other digits must be 0 by observation 6. For m=3 we get 3211000, for m=4 we get 42101000, for m=5 we get 521001000, and for m=6 we get 6210001000.

We have now studied all cases and found seven possible self-referential numbers. Now I must present my proof for Lemma C to complete the solution.

*Proof of Lemma C: Assume dk=m for some m>2. We need to prove that k can only be 0.

  • if k>3, we have Sk=dk=m, that is m digits k, where m is at least 3 and k is at least 4. The sum of these digits is k*m, which is at least 4*3=12, higher than allowed maximum of 10.
  • if k=3, we have S3=m, that is m digits 3, where m is at least 3. The sum of these digits is 3m, which forces m=3 since the maximal digit sum is 10. Now we have d3=S3=3. But since S3=3, we have dp=3=Sp for some other non-zero number p. This yields another 3p towards the digit sum which was already 9, exceeding the maximum.
  • if k=2, we have d2=S2=m. So we have at least three digits 2, and the digit d2 which is at least 3. This already makes a digit sum of at least 9. Now look at the digit dm. It can't be 0 since then Sm would be 0, which contradicts d2=m. It can't be >1 because we can't afford another digit m. So dm=1, which makes S1>0, which means we need a digit 1 as well. This brings our digit sum up to the maximum of 10. Problem is there can't be another 1. Since we must have exactly one 1, and exactly one m, we have d1=1 and dm=1, which makes S1>1, contradicting that d1=1.
  • finally if k=1, we have d1=S1=m. Now look at m. We know it is at least 3. What if it were larger? Then we would have at least four digits 1, and the digit d1 which is at least 4, bringing the digit sum to at least 8. But each digit 1 refers to a single instance of some other digit. Besides a single 0 and a single m, we need at least two more single digits, the smallest being 2 and 3 which would bring our digit sum to at least 13. So m can only be 3. So d1=s1=3. The three 1s and the 3 representing them make a digit sum of 6, but we need more digits. Each 1 represents a single instance of some other digit. Look at d3. It can't be 0 because S3 is not 0. It can't be 2 because another digit 3 brings the digit sum to 9, and the digit 2 representing the two digits 3 brings it to 11. It can't be greater than 2 because another two digits 3 brings the digit sum from 6 to 12. Thus we have d3=1. We need two more 1s. Let dp=1 and dq=1, where neither p or q can be 1 or 3. This raises the digit sum by p+q, so either p or q must be 0. Otherwise they would be at least 2 and 4, raising the digit sum from 6 to at least 12. So d0=1. To recap this mess, we have d0=1, d1=3, d3=1. Current digit sum 6 since we have another 1 to place. dp=1 for some p other than 0,1, or 3. This represents a single instance of the digit p, which raises the digit sum by p, and also that digit p represents p instances of some other digit, raising the digit sum through the ceiling once again.

AND FINALLY IT IS DONE... this was A LOT easier to do in my head than to put down in text, and looking at all this text I wonder if an extensive breakdown of every number from 1 to 999999999 wouldn't have been just as fast. At least I can laugh evilly knowing that anyone who wants to proof-read my solution is in for a major headache, MUAHAHAHAHA *brain meltdown*

Link to comment
Share on other sites

  • 0

There are seven self-referential numbers in total (in the decimal system). They are 1210, 2020, 21200, 3211000, 42101000, 521001000, and 6210001000. (On a side note we could relax the definition to allow numbers with more than 10 digits if we defined exactly what the 11th and onward digits would represent.) Now for proving that these are the only self-referential numbers.

Notation: A self-referential number with N digits is written d0d1...dN-1. Let Sk be the number of instances of the digit k. By definition, a self-referential number satisfies dk=Sk for all k.

Observation 1: The first digit can never be 0. If d0=0, then the number contains at least one 0, meaning S0>0. But 0=d0=S0>0 is a contradiction.

Observation 2: Some digit must be 0. Otherwise S0=0, which means d0=0, which is impossible.

Observation 3: All digits can not be equal. Follows directly from observations 1 and 2.

Lemma A: A self-referential number d0d1...dN-1 has no digit larger than N-1.

Proof: Suppose dk>N-1 for some k. Then Sk=dk>N-1, which means there are at least N digits k. But there are only N digits total, so all digits are k. This contradicts observation 3.

Lemma B: The digit sum of a self-referential number equals the number of digits.

Proof: d0+d1...+dN-1 = S0+S1...+SN-1 = (number of digits)-(number of digits larger than N-1) = (number of digits) by Lemma A.

Observation 4: The maximal digit sum is 10. Follows from Lemma B and the fact that the maximal number of digits is 10.

Lemma C: No digit except d0 can be larger than 2. My proof for this is very long and ugly.*

Observation 5: Only one digit can be larger than 2. Follows directly from Lemma C.

Lemma D: After the third digit, there can be at most one non-zero digit.

Proof: Suppose dp and dq are both non-zero, where p and q are both larger than 2. Then Sp and Sq are both non-zero, meaning we have both a digit p and a digit q. This contradicts observation 5.

Corollary to Lemma D: If there is a non-zero digit after the third digit, that digit must be 1.

Proof: Suppose dp>1 where p>2. Then Sp>1, meaning there is more than one instance of the digit p. Again, this contradicts observation 5.

Observation 6: There are at most four non-zero digits. The first three digits can be non-zero, and at most one digit after that.

Lemma E: Either d1 or d2 is <2.

Proof: We know that neither is >2 by Lemma C. So we only need to prove that both aren't equal to 2. Suppose they were. Then S1=d1=2, meaning we have two 1s. Only one of them can appear after the third digit by Lemma D. The second and third digit are occupied by 2s. So the first digit must be 1. Now look at the other 1. It represents a single instance of another non-zero digit m>2. This makes five non-zero digits (two 1s, two 2s, and one m), which contradicts observation 6.

Now it's time to break it down:

  1. The case where d0=1. This makes d1=S1>0. Also, d1 can't be 1 since that makes S1>1 which contradicts d1=1. And d1 can't be >2 by Lemma C. So d1=2. We can't have d2=0, and we must have d2<2 by Lemma E. So d2=1. Since we already have the two 1s and the one 2, there can be no more non-zero digits. We only need to put one 0 at the end and we get 1210.
  2. The case where d0=2. This makes d2>0. If d2=1, we can't find a value for d1. It can't be 0 because we already have a digit 1, it can't be 1 because then we would have two digits 1, it can't be two because that would make two digits 2, and it can't be >2 by Lemma C. So d2=2. Now d1 could be either 0 or 1, bringing the solutions 2020 and 21200.
  3. The case where d0>2. Because d0=m for some m>2, we have dm=Sm>0. But by the corollary to Lemma D, such a digit can't be >1. So dm=1. Now d1 can't be 0 or 1, so it must be 2. Now d2 can't be 0 or 2, so it must be 1. This makes four non-zero digits (d0=m, d1=2, d2=1, and dm=1), all other digits must be 0 by observation 6. For m=3 we get 3211000, for m=4 we get 42101000, for m=5 we get 521001000, and for m=6 we get 6210001000.

We have now studied all cases and found seven possible self-referential numbers. Now I must present my proof for Lemma C to complete the solution.

*Proof of Lemma C: Assume dk=m for some m>2. We need to prove that k can only be 0.

  • if k>3, we have Sk=dk=m, that is m digits k, where m is at least 3 and k is at least 4. The sum of these digits is k*m, which is at least 4*3=12, higher than allowed maximum of 10.
  • if k=3, we have S3=m, that is m digits 3, where m is at least 3. The sum of these digits is 3m, which forces m=3 since the maximal digit sum is 10. Now we have d3=S3=3. But since S3=3, we have dp=3=Sp for some other non-zero number p. This yields another 3p towards the digit sum which was already 9, exceeding the maximum.
  • if k=2, we have d2=S2=m. So we have at least three digits 2, and the digit d2 which is at least 3. This already makes a digit sum of at least 9. Now look at the digit dm. It can't be 0 since then Sm would be 0, which contradicts d2=m. It can't be >1 because we can't afford another digit m. So dm=1, which makes S1>0, which means we need a digit 1 as well. This brings our digit sum up to the maximum of 10. Problem is there can't be another 1. Since we must have exactly one 1, and exactly one m, we have d1=1 and dm=1, which makes S1>1, contradicting that d1=1.
  • finally if k=1, we have d1=S1=m. Now look at m. We know it is at least 3. What if it were larger? Then we would have at least four digits 1, and the digit d1 which is at least 4, bringing the digit sum to at least 8. But each digit 1 refers to a single instance of some other digit. Besides a single 0 and a single m, we need at least two more single digits, the smallest being 2 and 3 which would bring our digit sum to at least 13. So m can only be 3. So d1=s1=3. The three 1s and the 3 representing them make a digit sum of 6, but we need more digits. Each 1 represents a single instance of some other digit. Look at d3. It can't be 0 because S3 is not 0. It can't be 2 because another digit 3 brings the digit sum to 9, and the digit 2 representing the two digits 3 brings it to 11. It can't be greater than 2 because another two digits 3 brings the digit sum from 6 to 12. Thus we have d3=1. We need two more 1s. Let dp=1 and dq=1, where neither p or q can be 1 or 3. This raises the digit sum by p+q, so either p or q must be 0. Otherwise they would be at least 2 and 4, raising the digit sum from 6 to at least 12. So d0=1. To recap this mess, we have d0=1, d1=3, d3=1. Current digit sum 6 since we have another 1 to place. dp=1 for some p other than 0,1, or 3. This represents a single instance of the digit p, which raises the digit sum by p, and also that digit p represents p instances of some other digit, raising the digit sum through the ceiling once again.

AND FINALLY IT IS DONE... this was A LOT easier to do in my head than to put down in text, and looking at all this text I wonder if an extensive breakdown of every number from 1 to 999999999 wouldn't have been just as fast. At least I can laugh evilly knowing that anyone who wants to proof-read my solution is in for a major headache, MUAHAHAHAHA *brain meltdown*

Damn, Rainman. :blink:

Well done.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...