Register to reply

Pigeon hole principle used for derived strings

by diana.hole
Tags: derived, hole, pigeon, principle, strings
Share this thread:
Mar31-12, 02:09 AM
P: 8
1. The problem statement, all variables and given/known data
Consider this string of digits:


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


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.









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.

2. Relevant equations

[b]3. The attempt at a solution[/b
i know that the pigeon hole principle should be used but im not quite sure how to apply it, or word the answer correctly.
Phys.Org News Partner Science news on
'Office life' of bacteria may be their weak spot
Lunar explorers will walk at higher speeds than thought
Philips introduces BlueTouch, PulseRelief control for pain relief
Mar31-12, 09:04 AM
P: 361
Do you have a "near-miss" solution that would help illustrate what your thinking is with this currently?
Mar31-12, 10:55 AM
P: 8
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:
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 im really bad at explaining things, and i dont know whether my writing is comprehensible or not.

Mar31-12, 04:00 PM
P: 361
Pigeon hole principle used for derived strings

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?
Apr1-12, 12:52 AM
P: 8
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?
Apr1-12, 09:49 AM
P: 361
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?
Apr3-12, 06:00 AM
P: 8
well according to my method, if the original string had 29 digits, then the derived string would at most have 12 digits.
Apr3-12, 08:14 AM
P: 361
Yes, so you see how quickly a starter string will shorten down to 10 digits.
Apr8-12, 01:39 AM
P: 1
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?
Apr8-12, 01:26 PM
P: 361
The existence proof would use the fact that there are only a finite number of strings possible.
Apr14-12, 01:30 AM
P: 3
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)
Apr14-12, 02:29 AM
P: 3
Joffan, is there any other way to contact you! i desperately need this answer!
Apr14-12, 06:52 AM
P: 361
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.
Apr14-12, 11:29 PM
P: 3
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!
Apr25-12, 11:42 AM
berkeman's Avatar
P: 41,320
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.

Register to reply

Related Discussions
Pigeon hole principle Precalculus Mathematics Homework 3
Pigeon Hole Principle problem Precalculus Mathematics Homework 3
A question that should use pigeon hole principle. Linear & Abstract Algebra 15
Need some help with a proof (using the pigeon hole principle) Introductory Physics Homework 4
Pigeon Hole Principle General Math 10