Question

A good one too, I guess.
Determine the number of positive integers x, where x is less than equal to 9,999,999 and the sum of the digits in x is 31.

Answer 1

4,869,117

Answer 2

there are many posibilities

Answer 3

Exactly. You have to find the exact number of such possibilities. :)

Answer 4

how ? too hard

Answer 5

Easy wouldnt have half the fun, would it? :P

Answer 6

two and three-digit numbers wouldn't add up to 31. so start with 4 digit numbers

Answer 7

And 9994000 is the highest it can go. So start counting! :) Though I guess the problem can be solved much more simply.

Answer 8

This is what python is for.

Answer 9

(or mathematica)

Answer 10

Haha.
Got to have an easier wayy guyss.

Answer 11

a+b+c+d+e+f+g<=31

Answer 12

No.
=31.

Answer 13

a<9
b<9
c<9
d<9
e<9
f<9

Answer 14

Oh. ok.

Answer 15

And then youd have to make cases.
4 digit.
5digit.
6digit.....

Answer 16

just linear programming to solve the problem

Answer 17

1000000a+100000b+10000c+1000d+100e+10f+g=9,999,999

Answer 18

a+b+c+d+e+f+g=31

Answer 19

And the Coeff. wouldnt be easy to calculate either because of restricted range.
@LoneDrifter - In a maths test- Tough luck.

Answer 20

a, b, c, d, e, f, and g, could equal zero(though not more than 3, obviously)

Answer 21

Simplex algorithm might be able to solve it but very long winded

Answer 22

Then, I'm not sure how to include the positive integers.

Answer 23

Inkyvoyd,,For the first condition <= 9999999

Answer 24

(number of possible sums that add up to 31)*(all possible permutations of the numbers)

Answer 25

Then, the problem reduces down to looking for sums that equal 31

Answer 26

@LoneDrifter No. s repitition in numbers will stop such a direct formula.
Youd have to do each case individually.

Answer 27

@siddhantsharan , am I even on track?

Answer 28

you can take out the repetition of digits when working out permutation of the numbers

Answer 29

I dunno myself. I dont have the solution.
And I havent figured out one.
Just figured out what we CANT do. :P

Answer 30

It may be easier to solve problem on paper if you solve by programming first.

Answer 31

1000000a+100000b+10000c+1000d+100e+10f+g<=9,999,999
a+b+c+d+e+f+g=31
999999a+99999b+9999c+999d+99e+9f<=9999968
divide both sides by 9
111111a+11111b+1111c+111d+11e+f<=1111107

Answer 32

@LoneDrifter
How?
For egs. while figuring out no. of numbers who give the sum of 31,
you may get a no. like
Say, aabcd And one with all unique digits, abcd --- How would you differentiate in permutations.
Maybe its easier. Not a programmer myself so :(. But if you could workout the answer - Would def. help.

Answer 33

Maybe play with the permutations that way.

Answer 34

when a=9, subtract both sides

Answer 35

Nice. Makes sense. Now to go further from here.

Answer 36

11111b+1111c+111d+11e+f<=111,108

Answer 37

This won't work.

Answer 38

We need to reduce the problem further before brute force.

Answer 39

We need to solve the probability probem that @LoneDrifter proposed.

Answer 40

knowing possible combination of numbers that add up to 31 if first task then split these combinations into separate list for the number of repeated digits they contain once we have this it is simple permutation problem

Answer 41

I do not mean real list obviously but so we know there are 15 with all unique digits, 23 with one repeated digit and so on

Answer 42

http://en.wikipedia.org/wiki/Subset_sum_problem
If i'm correct, this means that we have an NP hard problem.

Answer 43

I'm just going to try to write a computer program to brute force this.

Answer 44

that was my plan but i want to see if we can find an elegant solution first

Answer 45

Hmmmm.
Dinner time here. Will get back to this in a while. :)
I think an elegant solution must exist for this. Its an exam question, after all.

Answer 46

Well, I just found that it's most likely NP-hard unless you can find some special case

Answer 47

wait, tell me what subject this is.

Answer 48

Maths. Entrance exam question. :)

Answer 49

how long are you given?

Answer 50

No, is there a specific sub-subject?

Answer 51

Like, discrete, linear, calculus, etc

Answer 52

looks like a discrete problem

Answer 53

NP-hard. The good news just keeps coming. :P
Permutations and Combinations I guess. It can be discrete though.

Answer 54

1 hour for about 40-50 questions

Answer 55

so your suppose to solve it in around 2 minutes

Answer 56

Apparently.

Answer 57

seems we are missing something very obvious then

Answer 58

are the other questions this tricky?

Answer 59

Well, let's read up on wikipedia, for the knapsack problem.

Answer 60

http://en.wikipedia.org/wiki/Knapsack_problem

Answer 61

I'm going to stop here, because I"m completely useless. I haven't even taken trig, though I have read up to calc2

Answer 62

I could do this problem... but it's a nightmare.

Answer 63

Thanks that's so helpful

Answer 64

35

Answer 65

@siddhantsharan , want me to write a computer program to test? (*try to write a program*)

Answer 66

The only way I see to do this is to find how many ways can we partition 31 without exceeding 7 partitions, and each element of the partition is less than or equal to 9.

This is a rather difficult problem.

Answer 67

answer is 35

Answer 68

sahil, that is sort of hard to take without any form of work shown.

Answer 69

@inkyvoyd That would be great.

Answer 70

Excuse what I said above, we need to find how many ordered partitions of 31 that have exactly 7 partitions, and each element of the partition is less than or equal to 9.

So if we get one partition, switching two numbers within the partition would give us a different solution. I'm not sure if this is harder or easier.

Answer 71

This will take some time, because I forgot how to do most of the stuff. I should be able to do it though.

Answer 72

I got digit sum 31 in a case when there are 3 9's and 4 1's now ways to get this is 35 as
Fact(7)/(fact(3)*fact(4)) ie 35
no other possibility is there

Answer 73

What if there were 3 9's and one 4?

Answer 74

How bout 2 9's and 3 ones and one 2?

Answer 75

KingGeorge: I believe ordered partitions are known as compositions, which is what you need to find here. see here: http://en.wikipedia.org/wiki/Composition_%28number_theory%29

Answer 76

That is exactly what I was looking for, and it may be easier than ordinary partitions using some recursive steps.

Answer 77

I think it has a well known formula - look further down on that link I pasted above.

Answer 78

I think, in this case, the answer would be:\[2^{31-1}\]

Answer 79

but that doesn't /feel/ right as we have not considered the restriction of 7 digits.

Answer 80

But that number is including partitions such as \((30, 1)\) and we want to exclude it.

You would have to start with \((9, 9, 9, 4)\) and start breaking each digit up individually, and finding each combination of digits that doesn't repeat.

Answer 81

oh yes we can also get 3 9's 1 )4) and 3 0's
3 9's one 3 and one 1 and 2 zero
3 9's 2 two's and two zero also
answer is 805

Answer 82

ah yes - I think you have it KingGeorge!

Answer 83

He has it, and I'm far from done with this program -.-

Answer 84

But there are other restrictions we must consider too, and right now, we would still end up with about 30 different cases. For example, each number must not be divided up into anymore than 4 partitions, but if we partition 9 into 8+1, then we can add the 1 to the four and get (9,9,8,5), which means we can still partition any number into 4 different numbers.

There's just so many separate cases to consider, that I don't know where to start. So I will leave for the time and get food.

Answer 85

@KingGeorge
I tried that. But, first I checked how many mere unordered possibilities are possible. And that itself is 259185. So that method is pretty impractical.

Answer 86

It's running. Hopefully I wrote it correctly. View source code at: http://pastebin.com/KhRm2vNL

Answer 87

I should try writting it in C++, but I doubt I have the skills.

Answer 88

Written in both C++ and python now, because python wouldn't work.

Answer 89

http://pastebin.com/Wq4kaSB3

Answer 90

Please check my source code for errors. THank you.

Answer 91

Ok, my source code definitely has issues.

Answer 92

Haha. Frustrating this is.

Answer 93

@amistre64 , Help?

Answer 94

512365

Answer 95

My new source code.
http://pastebin.com/qSJCXiYC

Answer 96

and you can divide by 7, so it's looking good. I'm going to write another program to try to find it the smarter way, with just adding the numbers...

Answer 97

lol, it literally takes 3 seconds for it to finish running.