3
$\begingroup$

In this puzzle, you have to place enough zeroes to make a number have a certain number of digits. For example you are expected to take the 3-digit number $123$ and are expected to make it 5 digits. So you have to place 2 zeroes in any part(except the beginning) of the number. Like,

$$12003$$ $$10023$$ $$10203$$ $$etc.$$

The thing is, the order of digit can also be changed. So these are also counted as a result. $$21003$$ $$30021$$ $$20103$$ $$etc.$$

The objective is to find the count of different positions(permutations) that this 5 digits number can have. So easy enough, This problem can be solved by the stars-and-bars method. First we find the number of permutations the 3 digit number can have. Then we use the stars and bars methods to find how many positions that the zeroes can be placed. Then multiplicate it. However there is a catch that makes this problem much harder. What if a there is a upper limit number that restricts you from using this easy method. For example if upper limit number is $28192$. The permutation $30021$ is no longer viable so must be taken off from the count. How would you solve this problem mathematically.?

Note1: First given number will not contain any zeroes.

Note2: The upper limit number will always be same digits as the target digit count.

$\endgroup$
7
  • $\begingroup$ You have too many variables to juggle. Try solving it for a particular case, then generalise. $\endgroup$ – Graham Kemp Aug 2 '16 at 4:24
  • $\begingroup$ That's the interesting part. This is a particular case of a much complex problem. $\endgroup$ – Rockybilly Aug 2 '16 at 4:25
  • $\begingroup$ More of a programming challenge than a math question, but you can write a recursive DP / state machine for this and convert it to a matrix and ultimately a linear recurrence $\endgroup$ – user51819 Aug 2 '16 at 4:52
  • $\begingroup$ I think you have to consider that the first digit is 1,2 or 3 with equal probability, so a third of answers is eliminated and a third are accepted, and third is pending. For the 2's in the first digit, you then have 0,1,3 with equal probability - all are accepted, So for this case, it is 2/3 of the combinations - you only care when you can get a 'tie' in a position in the compare digit, after that you can stop - so you can formalize a method, even if perhaps no write down an actual formula based on n $\endgroup$ – Cato Aug 2 '16 at 11:36
  • $\begingroup$ That's my answer, you'd work out the percentage that passed the test, based on the distribution of digits in the first digit, then for ties in first digit you would calculate for second digit, then for ties go onto the third digit. It depends on the initial distribution of digits given, for example 999 - 100% pass 111 - 100% fail (in your example) $\endgroup$ – Cato Aug 2 '16 at 11:40
0
$\begingroup$

I've written some code in python that I believe solves your problem.

The code is

import itertools

digits = [1,2,3,0,0]
minnum = 10000
maxnum = 28192

def list_to_int(ls):
    num = 0
    for digit in ls:
        num += digit
        num *= 10
    return num / 10

perm = map(list_to_int, itertools.permutations(digits))
perm2 = []

for i in perm:
    if (i > len(perm)):
        if (minnum<i<maxnum):
            perm2.append(i)

perm.sort()
perm2.sort()

print perm
print perm2
print len(perm2)

I wrote it such that you can edit the digits, minnum, and maxnum variables and it will operate the same. digits takes in the different digits you want to find the permutations of (in this case, 1, 2, 3, 0, and 0), minnum is the minimum value the number must have to be included in the number of permutations (used to remove permutations that start with a zero), and maxnum is the maximum value the number can have to be included in the number of permutations.

The package is used to calculate permutations, and the list_to_int function gets the sublists originally produced into integer format; this is then sorted and printed as the list perm. The second list, perm2, is created by iterating through each of the items in the list perm and checking if they fall within the range defined by minnum and maxnum. Finally, perm2 is sorted, printed, and the length of perm2 is calculated and printed.

I compiled it in an online compiler, repl.it, and the end result given was 48. There are 48 permutations that fulfill your requirements.

Hope this helps!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.