Pigeon hole principle used for derived strings

[diana.hole]

Homework Statement

Consider this string of digits:

A=03161011511417191111

It has two 0s, twelve 1s, zero 2s, and so on.

We construct another string of digits, called B, as follows: write the number of zeros in A, followed by the number of 1s, followed by the number of 2s, and so on until we write the number of 9s. Thus

B=21201111101

String B is called the derived string of A. We now repeat this procedure on B to get its derived string C, then get the derived string of C, and so on to produce a sequence of derived strings.

A=03161011511417191111

B=21201111101

C=2720000000

D=7020000100

E=7110000100

F=6300000100

G=7101001000

H=6300000100

Notice that the last string equals a previous string so the sequence of derived strings will now repeat.

show that if a string has less than 1000 digits, then its derived string has at most 29 digits.

Homework Equations

N/A


3. The Attempt at a Solution [/b
i know that the pigeon hole principle should be used but I am not quite sure how to apply it, or word the answer correctly.

 

[Joffan]

Do you have a "near-miss" solution that would help illustrate what your thinking is with this currently?

 

[diana.hole]

well, so far my explanation is as follows;
lets take the largest possible number under 1000, which is 999, for the amount of digits in the original string.
the derived string is divided into 10 "segments"(zeros, ones, twos, threes etc.)
if all the digits in the original string containing 999 digits were the same, then the derived string would have three digits representing the number that was repeated, and a singular digit representing all the other numbers that weren't, thus creating a derived string containing a maximum of 12 digits altogether.
e.g. 3+(1*9)=12
then, in order to get a larger amount of digits for the derived string, you split it up, where 999 is made up of two digits of equal/similar amounts. meaning that in the derived string there will be 2 sets of three digits representing the numbers that were repeated, and a singular digit for all the numbers that weren't.
e.g. 3+3+(1*8)=14
henceforth you continue the trend until you reach the pinnacle/climax.
the continued trend would look like this:
3+3+3+(1*7)=16
3+3+3+3+(1*6)=18
3+3+3+3+3+(1*5)=20
3+3+3+3+3+3+(1*4)=22
3+3+3+3+3+3+3+(1*3)=24
3+3+3+3+3+3+3+3+(1*2)=26
until we reach the point where the derived string consists of;
9 digits which are repeated 100 times each, and one digit which is repeated 99 times, therefore in the derived string there will be 9 sets of three digits representing the numbers that were repeated 100 times each, and two digits representing the number that was repeated 99 times. hence making a total of 29 digits in the derived string.
e.g. (9*3)+2=29
therefore reaching the pinnacle, and proving that 29 is the maximum amount of digits a derived string can have if the initial string had less than 1000 digits.
is this a sufficient argument? tell me if there is something wrong with it, because I am really bad at explaining things, and i don't know whether my writing is comprehensible or not.

 

[Joffan]

Your argument is sound, if a little long-winded. The pigeonhole principle is kind-of reversed here to say that there must be one digit that appears less than 100 times, therefore the total digit count is 29 rather than 30. Of course there are a great many ways that 29 digits can be achieved.

What does your method say about starting with a string of 29 digits?

 

[diana.hole]

im not quite sure what you mean by "starting a string with 29 digits"

and i also have another question to do with derived strings.

find all the strings that have 1000110001 as their derived string.

my approach to this was since it has 10 digits, that means that every digit represents the amount for each digit in the string that was previous this one. which means that there is; 1 zero digit, 1 four digit, 1 five digit, and 1 nine digit.
therefore this is the original string since it doesn't have a total of 10 digits, and all the combinations for the original string includes;
0459, 0495, 0549, 0594, 0945, 0954, 4059, 4095, 4509, 4590, 4905, 4950 etc.
is this correct?

 

[Joffan]

To clarify my earlier question: how many digits might the derived string have if the starting string has 29 digits?

On strings that generate 1000110001 - correct. What is the total number of possibilities?

 

[diana.hole]

well according to my method, if the original string had 29 digits, then the derived string would at most have 12 digits.

 

[Joffan]

Yes, so you see how quickly a starter string will shorten down to 10 digits.

 

[mathshugger]

I have a related question as well.
How can you prove that if the starting string has only two digits, then the sequence of strings will eventually repeat?

 

[Joffan]

The existence proof would use the fact that there are only a finite number of strings possible.

 

[massive]

Hi, i have the same question, shown below: 'How can you prove that if the starting string has only two digits, then the sequence of strings will eventually repeat?' Joffan, could you please elaborate and help me solve this equation! thankyou (could you reply as soon as possible)

 

[massive]

Joffan, is there any other way to contact you! i desperately need this answer!

 

[Joffan]

If the starting string has two digits - say 52 - then the derived string will have 10 digits, 0010010000 in this case. Then depending only on whether the initial two digits were the same or different, there are only two possibilities for the next string, and you can track both of those until they repeat, for a direct demonstration in very few steps.

More generally, if the starting string is 1-9 digits, the next string will be 10 digits not all the same, and every following string will be 10 digits not all the same that sum to 10 (you'd need to explain why this is true). There are only a finite set of such strings so repetition must occur eventually.

 

[massive]

thankyou very much joffan! i have already seen the pattern and made connections! However, an actual proof as to why the strings eventually repeat is turning to be extremely difficult. i am missing a connection! could you please, reply as this is due in tomorrow giving a proof! it can be brief! thankyou very much, already!
regards massive!

 

[berkeman]

This thread is locked. We do not give help to users who show zero work.

And this was posted by a user who wishes now to remain anonymous...

Are you all doing Math Challenge Stage? You're not supposed to get external help.