How many possibilities are there to get 144

[futb0l]

How many possibilities are there to get 144, from putting addition/substraction signs in between 1, 2, 3, 4, 5, 6, 7, 8, 9...

example: if the question is to find how many possibilities to get 27 then one of the possibility will be.. 1+2+3+4+5+6+7+8-9

 

[AKG]

Uh, where does the list end. If we only go up to 9, then we can only possibly reach 45, never 144. So I'm guessing the ellipsis after the 9 meant something, but how far up do we go? I would think if we could go on forever, we could have an infinite number of ways to get 144. Find all pairs of numbers, {x,143+x} for x = 4n, for natural n. Then, (143+x) - (x) + (1) = 144. Now, what do we do with the numbers 2, 3, ..., x-1, x+1, x+2, ..., x + 142? Well, since x is any multiple of 4, the number of pairs of numbers between 1 and x will be odd, i.e. the numbers 2, 3, ..., x-1 will form a set that contains an odd number of pairs. The numbers from x+1 to x+142 also forms an odd number of pairs, 71 pairs to be exact. So, we have two sets of odd numbers of pairs. In total, we have an even number of pairs. So, we can make half the pairs each sum to +1, and the other half to -1, so in total they have zero effect, and we're left with 144. I.e., half the consecutive pairs of numbers, a, a+1, will be written like this:

... + (a) - (a+1) + ..., giving -1, and the other half will be ... - (a) + (a+1) + ..., which is 1. All this work, I have the feeling this isn't what the question is asking.

 

[futb0l]

oh oops sorry, i meant to say division and multiplication sign as well...

 

[AKG]

Okay, here's how I'd do it. First of all, write the prime factors of 144:

2 x 2 x 2 x 2 x 3 x 3 x 1 x 1 x 1 x 1 x 1 x ...

Now, normally, we wouldn't write all those one, but we do in this case. Now, find out how many ways you can write 144 in terms of 1 factor, 2 factors, 3 factors, ... 9 factors.

1 factor
144

2 factors
144 x 1
48 x 3
16 x 9
8 x 18
4 x 36
2 x 72
6 x 24
12 x 12

3 factors
144 x 1 x 1
1 x (all the pairs for 2 factors)
(a whole bunch more)

Then, for each n, where n is the number of factors, find out how many ways you can place the n-1 "x"s (times symbol) between some pair of numbers in
1 2 3 4 5 6 7 8 9.

There are 8\choose {n-1} ways to place n-1 "x"s. Now, you'll have a huge list of ways to express 144 in terms of a number of factors, and a huge number of ways to place a number of "x"s between number 1 through 9. Now, for n factors, and n-1 "x"s, find out how many of those products you can turn into 144. That's unclear, let me clarify. Let's say n=2. Now, we have the numbers:

1 2 3 4 5 6 7 8 9

One of the 8 ways we can place n-1=1 "x"s is as follows:

1 2 3 4 5 x 6 7 8 9.

Now, using addition, subtraction, and division only, how many different numbers can you get out of 1 2 3 4 5?
You can get a few numbers, two if which are:
1 + 2 + 3 + 4 - 5 = 5
1 + 2 - 3 - 4 + 5 = 1
(Note, there are other combinations that give 5, and maybe more that give 1).
Now, with 5, for example, you know that no two numbers including 5 multiply to 144, i.e. 5 x something is not on the list of 2 factors. However, 1 is on the list. But that means that with 6 7 8 9, you have to make 144. Can you do it, and in how many ways? This will be a lot of work, I can't see this problem being easy or not requiring a lot of brute force, but this is one approach. You might be able to refine it further, this is a start at least.

 

[AKG]

One thing to notice is that the numbers you have to make is something in the set:
{1,2,3,4,6,8,9,12,16,24,36,48,72,144}. Oh wait, unfortunately, you can divide, so you might have to deal with the situation (1/3) x (3) x (144). Make it easy on yourself and start without division. So you really only have to deal with addition and subtraction. Note that with addition, you can't even make the number 48 or above. So that takes care of them. Only 1 set of numbers can be added to 36 (1 to 8) and multiplying that by 9 is useless (it doesn't give 144) so that's taken care of. So look, we've already limited the list under "2 factors" to 4 of the pairs. This will have a huge impact on reducing all further lists.

Oops, I made a big mistake, and I was kind of thinking that 1 2 3 x 4 5 6 7 8 9 would be (1 2 3) x (4 5 ... 9), of course, it won't be. So we might need a new approach.

 

[futb0l]

yeah, this problem is quite tricky, i am only 15, i am going to have a read at the number theory books in the maths napster.