Question

Show that if a string has less than 1000 digits, then it's derived string has at most 29 digits.

Answer 1

Assuming there are 1000 digits in the string, max. length of derived string is 30, if there are 100 1s, 2s, 3s etc. If there are less than 1000, there would be less than 100 of one digit, meaning that the derived string will only have at most 29 digits.

By the way, is this from MCS? haha.

Answer 2

I dont understand what u mean by max length of derived string is 30?

Answer 3

btw does anyone not know what a derived string is?

Answer 4

if you have 1000 digits, you cannot get a derived string of 31 digits or more, unless there is at least 1000 of one digit. but if you have 1000 1s, for example, you wouldn't have any other digits, your derived string would be 4. So max. length possible is when you have 100 of each digit...

Answer 5

because when you have 100 of each digit, your derived string would be 100100100100100100100100100100, 30 digits long :)

Answer 6

okay
but then one must be 99 times because 100 times 10 is 1000 so the max digits will be 29 is that rite?

Answer 7

yes :)

Answer 8

tx!

Answer 9

welcome!

Answer 10

can i explain it like this?:
the derived string of a string has 10 segments: 0s 1s 2s 3s 4s 5s 6s 7s 8s ansd 9s. Since the original string has less than 1000 digits , one digit (0-9) must occur less than 100 times or else there would be at least 10*100=1000 digits. Therefore, one 'segment" at most can occur 99 time if the original string has less than 1000 digits. This means in the derived string there could be at most 2 digits for one "segment' and the other 9 "segments" can result in at most 3 digits. Therefore the derived string must have at most 3*9+2=29 digits

Answer 11

yeah should be fine!

Answer 12

thanks so much!