A Surprisingly Difficult Problem

Why not try your hand at this innocuous looking challenge?

Using each of the numbers 1,3,4,6 create an expression which evaluates to 24. You may use any of the four standard arithmetic operations *,+,-,/ and parenthesis. You must use each of the numbers exactly once. You need not use any other numbers.

"Elementary" needn't mean easy ...

PS: Feeling cocky 'cause you knocked this one off in a flash? Then how about tackling the following?

Determine, with proof, the number of ordered triples of sets which have the property that

1. , and
2. 

where denotes the empty set. Express the answer in the form , where ,,, and are nonnegative integers.

Ain't so tough now, is ya?

Comments

[dsquared]

I did knock the first one off pretty quickly, but I'd seen a similar one before, so I'll hold off.

The answer to the second one looks like it ought to be 45 (a=0, b=2, c=1, d=0), because it looks like the question is asking how many ways there are of putting two lines between the numbers 1 to 10. But I daresay that the question isn't asking that, because I don't really know what the sets language means and can't be bothered to look it up. Oh hang on, the sets might be empty, so it can't mean that. Well in that case I definitely can't be bothered.

[Abiola Lapite]

The second problem isn't quite as bad as it looks, at least once you have the crucial insight required to solve it. All it's asking for is the number of partitions of {1,2,..,10} into 3 not totally-overlapping sets, with a little book-keeping required (hence the "ordering" bit).

[eoin]

My feeling is 55, assuming null sets, without a formal working out. As for expressing it any other way than 55, I run.

have not solved the first one yet.

[Nicholas Weininger]

I've solved the second one but not yet the first; shows what being a combinatorialist does for you, I guess.

[Bruce Cleaver]

OK, got the first one *two* different ways.

Still on the second problem.

[dsquared]

No, it's clearly much, much more than 45. 45 is the number of not-overlapping-at-all sets with no empties. Not-totally-overlapping has to be a much bigger number than not-overlapping-at-all by a combinatorial magnitude.

So ...

anything you can prove, you can prove by induction[1]

you can't partition the empty set into three not-totally overlapping sets at all ... not helpful.

You can't partition {1} either ... unless you are allowed empty sets. {0},{0},{1} satisfies the criteria above (I think). [2]

So does {0},{1},{1}, but {1},{1},{1} and {0},{0},{0} don't. So (this is presumably what Abiola means by bookkeeping), there are six ways (2^3, minus the two special cases) of arranging the ones and zeros into the numbered buckets.

Now for the difficult bit. What happens when you add 2?
um ...

you've got each of your six previous arrangements, and you can put a 2 into one of the buckets (which gives you eighteen ways) or you can put a 2 into any two buckets (gives you another eighteen ways), but you can't put the 2 into none of the buckets (or the union condition would obviously not work) or into all of them (or the intersection would have a 2 in it). So that's 36 ways of partitioning {1,2}.

Peano's theorem suggests that I have now done the difficult bit, but I'm blowed if I can see what to do now ... what happens when you add 3?

same thing, shurely? you've got 36 arrangements, but not 36 places to put a 3; in each of those 36 arrangements, it's got to go in one bucket or two. So {1,2,3} goes into 36*3 partitions.

Therefore I guess that the general rule is 6^(highest number in the list) and the answer is 6^10 which would suggest ...a=10, b=10, c=0, d=0. A little bit worried that 6^0 ought to be one and it's zero ... or is it? I think Abiola's "not totally overlapping" is a bit misleading in that case. A partion of {0}{0}{0} looks like it satisfies both criteria. So I think I'm right.

[1]I cannot prove this statement by induction
[2]Using {0} for the empty set because life's too short for Unicode.

[dsquared]

Ach, "36*3" above should be "36*6". Unless I am wrong, in which case it shouldn't.

[dsquared]

Presumably the psychoeducational pathology which caused me to forget that "{}" would be a better way to denote the empty set than "{0}" is linked to the reason that I will never be a mathematician. I did once grind out the first few chapters of an elementary combinatorics textbook in the woefully misplaced belief it would help me with statistics though, and there was lots of stuff like this in it.

[Nicholas Weininger]

dsquared: you are correct, the answer is 6^10. And you have the germ of what I think is the "right" proof in your argument. (You can also do something lengthy with symmetric differences and generating functions and stuff; this is what I did before I realized the following was simpler).

In general, suppose we want the number of ways to get an ordered k-tuple of sets A_1,...,A_k so that the union of all the A_i's is {1,...,n} and the intersection is empty. I claim there are
(2^k - 2)^n such ways.

To prove this, represent the A_i's as strings of bits, n bits each, where a 1 in the jth place means that element j is in the set and a 0 means it isn't. Arrange these as the rows of a k-by-n matrix. Now the jth column of that matrix says which of the sets contain element j.

The condition that the union of the A_i's is {1,...,n}, then, says that the column can't be all zeroes. The condition that their intersection is empty says that it can't be all ones. So there are 2^k - 2 possible bit strings that the jth column can be. This is true for each column independently, so you have
(2^k - 2)^n ways in all to construct your sets.

[David B]

OK, cleverclogs, what's the solution to the first problem? I can get just about every number *except* 24, and I've got tired of trying!

[Abiola Lapite]

"OK, cleverclogs, what's the solution to the first problem?"

Think *fractions* ...

[David B]

I don't see how that helps. Just give us the *&$^ing solution!

[Abiola Lapite]

Alright, I figure it's time to put you out of your misery.

6/(1-(3/4)) = 24.

[David B]

Thanks!