For those who enjoy brainteasers, I thought I'd post a few problems I've come across over the years. They are in no particular order. Following each problem is a time limit; solving within this time is impressive. Enjoy!

1) There is a 100-story building. You have two identical eggs, each of which will break if dropped from some integer story N (or greater). You are allowed to drop each egg from any height you wish, until it breaks. By the time both eggs are broken, you must determine N. What is the fewest number of drops needed in the worst case? [10 min.]

2) There is a balance in front of you. I will first ask you to choose a set of integer weights. You will then be given a block of unknown integer weight from 1 to 100, and asked to balance it using only weights from your set. You will be allowed to place your weights on one or both pans at your discretion, until it balances. What is the fewest number of weights you need in your set to guarantee that you can balance the given weight? [15 min.]

3a) You are blindfolded with a round table in front of you. It is marked with 4 positions (1, 2, 3, and 4), one in each quadrant. There are 4 cups on the table, one per quadrant, each initially randomly either face up or face down (which you cannot see). On each turn, you may instruct the genie to flip the cups in whichever numbered positions you wish. He will oblige, and then rotate the cups around the table as he wishes, so that the cups are (potentially) all in new positions, but in the same rotational order. Your goal is for all the cups to be face up. The genie will tell you if you've won. Can you give a solution that will always win the game, regardless of his sneaky rotations? [30 min]
b) For what values of N is this possible (in part a, N=4)? [No limit.]

4a) Prove that any set of 10 integers from [1, 100] must contain two distinct subsets each with the same sum of elements. [5 min]
b) Find the smallest n for which this does not hold for a set of 10 integers from [1, n]. [2 hrs.]
c) First solve A and B, then we'll talk :-P [Open problem]

5) You walk into a candy store in a foreign land that has only 2 types of coins. The coins are worth A and B, where A and B are relatively prime (share no common factors other than 1). Assuming you have an infinite number of each coin, what is the price of the most expensive candy that you cannot buy with exact change? That is, find the largest price such that you will require change to purchase it exactly. [20 min.]

Last edited by Flyboy217 on Oct-11-2003 at 20:44

quote:

Originally posted by Flyboy217 5) You walk into a candy store in a foreign land that has only 2 types of coins. The coins are worth A and B, where A and B are relatively prime (share no common factors other than 1). Assuming you have an infinite number of each coin, what is the price of thet most expensive candy that you cannot buy without needing change from the cashier? [20 min.]

If there's only two types of coins, and you have an infinite number of each, I don't understand how you can get change back. Seems as though the problem is missing something.

the answer to number 2 is 6 i think but i might be wrong as i came up with that in about 10 seconds, but i think im right

edit: deleted other edit, 6 is right

quote:

Originally posted by Omegasox If there's only two types of coins, and you have an infinite number of each, I don't understand how you can get change back. Seems as though the problem is missing something.

imo, these r badly worded mostly

quote:

Originally posted by Omegasox If there's only two types of coins, and you have an infinite number of each, I don't understand how you can get change back. Seems as though the problem is missing something.

Suppose the coins are valued 3 and 5. You cannot buy a candy of value 2 with exact change. You would pay 5 and get back 3. If you try to buy a candy of value 4, you could give 3*3 and get back 5. There are finitely many prices for candies which you cannot buy exactly. I want you to find the most expensive of these.

The answer to problem 2 is not 6, but good try.

I apologize for the wording. Because of their conciseness, they probably sound more challenging than they are. I assure you that all required information is available in each problem though.

quote:

Originally posted by Flyboy217 The answer to problem 2 is not 6, but good try.

ok then 7.....
im stupid

quote:

Originally posted by Flyboy217 1) There is a 100-story building. You have two identical eggs, each of which will break if dropped from some integer story N (or greater). You are allowed to drop each egg from any height you wish, until it breaks. By the time both eggs are broken, you must determine N. What is the fewest number of drops needed in the worst case? [10 min.]

Seems to me like the answer should be 18. If you start at 11 and go up in steps of 11, the highest number of drops in between any two "big" tests would be 9 (there are 10 stories in between, but if we try 9 and the egg doesn't break then we've discovered the 10th by process of elimination). Worst case: floor 98. Take 9 drops up to the 99th floor to break the first egg, then start with the second egg from 89 all the way up to 97, making 18.

quote:

2) There is a balance in front of you. I will first ask you to choose a set of integer weights. You will then be given a block of unknown integer weight from 1 to 100, and asked to balance it using only weights from your set. You will be allowed to place your weights on one or both pans at your discretion, until it balances. What is the fewest number of weights you need in your set to guarantee that you can balance the given weight? [15 min.]

Unless I'm missing something, the answer to this is simple ceiling-ed binary division - i.e. a 50, 25, 13, 7, 4, 2, and 1 weight, making 7 weights in total. I suppose it might be possible to eliminate one or two of those, for example you could get the same result as a 13 weight by putting 25 on the left and 7+4+1 on the right, but if you needed that 13 to get all the way up to 99, this wouldn't work. I say 7, it might be possible to optimize some of them away but figuring out which ones would just be a ridiculously time-consuming process to the point of resembling work.

I'll look at the other ones later... I kind of don't like these because they aren't very meaningful, just cleverly worded mathematical optimization problems that don't involve any special thinking, just a lot of time and patience.

___________________
My party schedule:
2009-02-21 - DJ Attention @ I'm So Popular
2009-06-18 - DJ Annoying @ People Need To Know Where I'll Be
2012-11-32 - DJ Insufferable ɸ Or At Least the Stalkers I Complain About
2048-06-66 - Spastic & Whocares ¶ Although I'm Actually Flattered
9999-45-81 - Tweaker Gimp ☼ I Probably Won't Even Go To This But I Have To Make Sure I Fill Up All The Available Space Here

why are these all math questions? is math the only difficult academy?

tho i think i have answers for all except 4. i didnt need the time for the prev and im not wasting 2 hrs on that|

___________________
'That's like telling a Kodiak bear to stop fcking older men.'

quote:

Originally posted by DigiNut Seems to me like the answer should be 18. If you start at 11 and go up in steps of 11, the highest number of drops in between any two "big" tests would be 9 (there are 10 stories in between, but if we try 9 and the egg doesn't break then we've discovered the 10th by process of elimination). Worst case: floor 98. Take 9 drops up to the 99th floor to break the first egg, then start with the second egg from 89 all the way up to 97, making 18. Unless I'm missing something, the answer to this is simple ceiling-ed binary division - i.e. a 50, 25, 13, 7, 4, 2, and 1 weight, making 7 weights in total. I suppose it might be possible to eliminate one or two of those, for example you could get the same result as a 13 weight by putting 25 on the left and 7+4+1 on the right, but if you needed that 13 to get all the way up to 99, this wouldn't work. I say 7, it might be possible to optimize some of them away but figuring out which ones would just be a ridiculously time-consuming process to the point of resembling work. I'll look at the other ones later... I kind of don't like these because they aren't very meaningful, just cleverly worded mathematical optimization problems that don't involve any special thinking, just a lot of time and patience.

Try again on the first problem. You can do better than 18.
The balance one is also wrong, but good try.

The beauty of these problems is that, while they may look like time-consuming drudgery problems on the outside, each actually has an elegant solution which requires little work. The balance problem is especially elegant when you discover it, and requires no work at all if you can see the solution.

So far, no right answers. Keep trying though :-)

Okay so 4B isn't super elegant, but it has an amazing pattern underlying it. 4C is an open problem posed by Erdos, and it's a toughie :-)

Last edited by Flyboy217 on Oct-10-2003 at 05:16

quote:

Originally posted by Flyboy217 The beauty of these problems is that, while they may look like time-consuming drudgery problems on the outside, each actually has an elegant solution which requires little work. The balance problem is especially elegant when you discover it, and requires no work at all if you can see the solution.

Meh, I've seen problems like these before (not these particular ones), and I always hear this. The answers look elegant once you can see them, but there is no elegant way to come up with them.

I think you can do the first one with 18, by using a 12 or 13 step increment, just wasn't thinking too clearly on the first go. Hard for me to see how the answer could be any lower, though.

As for #3... this question doesn't make any sense. You haven't specified what the "game" is in the first place, but I'm assuming that the "game" is to get them all either face up or face down - okay, so even if this "genie" never rotates them at all, you haven't specified any point in time where you can actually see what the cups look like, so without knowing what state they started in, it's completely impossible to get them all either face up or face down. You must have omitted something from the question.

Can you just post the original questions, instead of trying to paraphrase them so they're concise but verbally confusing?

___________________
My party schedule:
2009-02-21 - DJ Attention @ I'm So Popular
2009-06-18 - DJ Annoying @ People Need To Know Where I'll Be
2012-11-32 - DJ Insufferable ɸ Or At Least the Stalkers I Complain About
2048-06-66 - Spastic & Whocares ¶ Although I'm Actually Flattered
9999-45-81 - Tweaker Gimp ☼ I Probably Won't Even Go To This But I Have To Make Sure I Fill Up All The Available Space Here

for the egg one tell the owner of the building that youll smash two eggs on your face if he tells you how tall his building is. more later.

or y9ou can just tie a string to the egg and lower it to the ground and measure the string.

quote:

Originally posted by DigiNut Meh, I've seen problems like these before (not these particular ones), and I always hear this. The answers look elegant once you can see them, but there is no elegant way to come up with them. I think you can do the first one with 18, by using a 12 or 13 step increment, just wasn't thinking too clearly on the first go. Hard for me to see how the answer could be any lower, though. As for #3... this question doesn't make any sense. You haven't specified what the "game" is in the first place, but I'm assuming that the "game" is to get them all either face up or face down - okay, so even if this "genie" never rotates them at all, you haven't specified any point in time where you can actually see what the cups look like, so without knowing what state they started in, it's completely impossible to get them all either face up or face down. You must have omitted something from the question. Can you just post the original questions, instead of trying to paraphrase them so they're concise but verbally confusing?

Ouch, you got me on #3. It didn't make any sense. I've since edited it. You were correct in assuming that they must all become face up. You still never see them, but he'll tell you if you've won. There is a winning strategy.

18 is not optimal for #1.

There is a somewhat elegant way to come up with the solution for the balance problem. But if, after a few minutes of thinking, you don't see the solution, then you're correct... it's probably not worth the time to solve "the hard way." (Hint: remeber, you can use *both* pans).