Very clever and difficult number theory puzzle (with generalization)

In summary: Oh yeah... and apart from having 10 digits, which is not allowed.In summary, the conversation discusses the determination of the number of 10 digit natural numbers that meet the criteria of having the first digit correspond to the total number of 1's, the second digit correspond to the total number of 2's, and so on until the tenth digit corresponds to the total number of 0's. The conversation also explores the extension of this problem to any numerical base and provides possible solutions for different bases. It is concluded that for base 7 and higher, the general solution is b-4 zeros, one b-4, one 2, and two 1s.
  • #1
mathwizarddud
25
0
For any 10 digit natural number [tex]N[/tex] in which

the first digit corresponds to the total no of 1's.
the 2nd digit corresponds to the total no of 2's.
.
.
.
the 10th digit corresponds to the total no of 0's.

determine, with proof, if the number of such natural number [tex]N[/tex] is finite, and if proved true, find them all.

A generalization of
http://answers.yahoo.com/question/i...lB5DIp8Cxgt.;_ylv=3?qid=20080628051813AA0p296

Also, extend this to any numerical base [tex]M[/tex] such that the [tex]M^{th}[/tex] digit corresponds to the total number of 0's and [tex](M - 1)^{th}[/tex] digit corresponds to the total number of [tex](M - 1)[/tex]'s for any natural number [tex]M[/tex], etc.
 
Physics news on Phys.org
  • #2
The first part seems quite trivial, as the number of 10 digit natural numbers is finite, so certainly the number of such special 10 digit natural numbers is finite. The question is, how to construct them all? And are numbers like "0100000000" a valid example (because technically, this is a nine digit number).
 
  • #3
I suspect the constraints are so tight that no combination will succeed (find a working example!).

This is the case for base 2, where none of the 4 possible combinations 00, 01, 10 or 11 match the requirements.

P.S.: Also, since the sum of digits must be exactly M, and all individual digits must be <M, there remain few cases to verify for bases 3 and 4, being readily visible that those bases do not work either.
 
Last edited:
  • #4
And I take back the example I gave, as there should be a number in the last slot to indicate the number of zero's. In fact, I can't think of an example at all at the moment.
 
  • #5
CompuChip said:
And are numbers like "0100000000" a valid example (because technically, this is a nine digit number).
Whether "0100000000" counts is a bit irrelevant in the case of base 10 because 0100000000 not a solution to the problem. It is relevant to the general problem because 0202 is a solution for base 4.
Dodo said:
I suspect the constraints are so tight that no combination will succeed (find a working example!).
2100010006 is a solution for base 10, and is the only solution for base 10. One way to reduce the complexity of the problem is to focus on the number of zeros. This can't be
  • 0 because there is at least one 0 in abcdefghi0.
  • 1, 2, or 3 because 5+6=11>10.
  • 9, 8, or 7 because there aren't enough non-zero digits left to make any of these three cases work.
  • 4 or 5. These are a bit tougher, but there cannot be 4 zeros or 5 zeros.
That leaves the case of 6 zeros. There is only one solution that works, and this is 2100010006.
 
  • #6
Dodo said:
P.S.: Also, since the sum of digits must be exactly M, and all individual digits must be <M, there remain few cases to verify for bases 3 and 4, being readily visible that those bases do not work either.
There are no solutions for bases 2 and 3, but there are either one or two solutions for base 4, depending on whether numbers with leading zeros count. The two base 4 solutions are 0202 and 2101.
 
  • #7
There are one or two solutions for base 4, depending on whether 0202 counts as a solution. These are the only solutions up to but not including base 7. There is a general solution for base b=7 and up: b-4 zeros, one b-4, one 2, and two 1s: 2110003, 21010004, 210010005, 2100010006, etc. Without proof, I posit that this general solution is the only solution for base 7 and up.
 
  • #8
2100010006 b10
1000000008 b10
8111111110 b10

These came from the Yahoo! thread...

1o57
 
  • #9
1o57 said:
2100010006 b10
1000000008 b10
8111111110 b10

These came from the Yahoo! thread...

1o57
1000000008 is not a solution. This number has one 8 in it, but has a zero as the eighth digit.

8111111110 is not a solution. This number has one 0 in it, but has a zero as the tenth digit.

2100010006 is a solution.
 
  • #10
D H said:
8111111110 is not a solution. This number has one 0 in it, but has a zero as the tenth digit.

Apart from not having a 2, 3, 4, 5, 6, 7 or 9.
 

1. What is number theory?

Number theory is a branch of mathematics that deals with the properties and relationships of integers, or whole numbers. It involves studying patterns and structures in numbers and solving problems related to them.

2. What makes a number theory puzzle difficult?

A number theory puzzle can be difficult for a variety of reasons, including the complexity of the problem, the need for advanced mathematical knowledge and techniques, and the level of creativity and critical thinking required to solve it.

3. Can number theory puzzles be generalized?

Yes, number theory puzzles can often be generalized to include a broader range of numbers or to solve similar problems with different parameters. This allows for a deeper understanding of the underlying principles and patterns in number theory.

4. How can I improve my skills in solving number theory puzzles?

Practicing regularly and studying fundamental concepts in number theory such as prime numbers, divisibility, and modular arithmetic can help improve your skills in solving number theory puzzles. It is also helpful to approach problems with a logical and analytical mindset.

5. What are some real-world applications of number theory?

Number theory has many practical applications, including cryptography, data encryption, coding theory, and computer algorithms. It is also used in fields such as physics, engineering, and economics to model and solve complex problems related to numbers and patterns.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
32
Views
2K
  • Programming and Computer Science
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
1K
Replies
4
Views
285
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
456
  • Linear and Abstract Algebra
Replies
4
Views
995
Back
Top