TranceAddict Forums (www.tranceaddict.com/forums)
- Chill Out Room
-- Smart?
Pages (6): [1] 2 3 4 5 6 »

Smart?

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.]

Re: Smart?

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

Re: Re: Smart?

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

Re: Re: Smart?

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.

Re: Re: Re: Smart?

quote:

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

ok then 7.....
im stupid

Re: Smart?

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.

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|

Re: Re: Smart?

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 :-)

Re: Re: Re: Smart?

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?

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.

Re: Re: Re: Re: Smart?

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).

Re: Smart?

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.]

log[base 2] of 100, think that is near 7...

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.]

um log[base2] of 100 again ? i think that is about 7 weights. 1,2,4,8,16,32,64

oops.. typo it's 16 of course

time to go back to my problem at work ... nice ones though!

quote:

Originally posted by biznology why are these all math questions? is math the only difficult academy?

not really, but the idea is that math is simple enough that you can 'theoretically' solve all problems by just THINKING about them. None of these involve any really complicated mathematics. They are all basic logic/ reasoning type questions.

Ok i didnt go through every single number but im sure if u pick the weights 1 2 5 10 20 50 100 u can guarentee a balance

quote:

Originally posted by drizzt81 not really, but the idea is that math is simple enough that you can 'theoretically' solve all problems by just THINKING about them. None of these involve any really complicated mathematics. They are all basic logic/ reasoning type questions.

but thats still not it...these are 'difficult' questions but they can be answered. not by everyone, necessarily, but still answered. what about everything else without an answer? sorry, im a philosophical asshole|

Re: Re: Smart?

quote:

Originally posted by drizzt81 log[base 2] of 100, think that is near 7... um log[base2] of 100 again ? i think that is about 7 weights. 1,2,4,8,16,32,64 oops.. typo it's 16 of course time to go back to my problem at work ... nice ones though!

Wrong and wrong . Thanks to modern-day CS, many people love thinking along the lines of log2. Get off your log2 horses and start THINKING, people! That's what's nice about these problems... they make you think in a way you're most likely not used to thinking.

C'mon, someone solve at least one!

Re: Re: Re: Re: Re: Smart?

quote:

Originally posted by Flyboy217 18 is not optimal for #1.

I suppose you could get it down to 17, if you used increments of 12. Once you hit floor 84 and it doesn't break, instead of going to 96, you go to 92. That way you only have to drop the next one 6 times.

This doesn't lower the worst case to 12, though, since this is no longer the worst case. The worst case will be when it does break at 84 (after 7 drops) and you need 10 to determine what's in between.

There is no possible way it can be lower unless there's a trick in the question. Here's the proof:

Assuming you drop the first egg at a regular interval n until it breaks, and I am sure that this is required, then the total number of drops required is going to be Floor[100 / n] + (n - 2). You can't make this lower than 18 for any value of n, unless you use the modification mentioned above, which nets you 17.

Flyboy, I'm bothered how you don't respond to any of my reasoning or proofs to tell me how the answers are wrong - I'm starting to wonder if you actually thought these questions through yourself or just dug them up somewhere along with the answers?

quote:

Originally posted by biznology but thats still not it...these are 'difficult' questions but they can be answered. not by everyone, necessarily, but still answered. what about everything else without an answer? sorry, im a philosophical asshole|

what biz said.

Re: Re: Re: Re: Re: Re: Smart?

quote:

Originally posted by DigiNut I suppose you could get it down to 17, if you used increments of 12. Once you hit floor 84 and it doesn't break, instead of going to 96, you go to 92. That way you only have to drop the next one 6 times. This doesn't lower the worst case to 12, though, since this is no longer the worst case. The worst case will be when it does break at 84 (after 7 drops) and you need 10 to determine what's in between. There is no possible way it can be lower unless there's a trick in the question. Here's the proof: Assuming you drop the first egg at a regular interval n until it breaks, and I am sure that this is required, then the total number of drops required is going to be Floor[100 / n] + (n - 2). You can't make this lower than 18 for any value of n, unless you use the modification mentioned above, which nets you 17. Flyboy, I'm bothered how you don't respond to any of my reasoning or proofs to tell me how the answers are wrong - I'm starting to wonder if you actually thought these questions through yourself or just dug them up somewhere along with the answers?

I apologize for not responding sooner. In general, I prefer to simply say "wrong" so that the person may figure out the solution entirely by himself. In this case, your proof was a good idea, but it is flawed. While I would normally just leave it at that, I'll go one step further and tell you that you make a faulty assumption in your first sentence. Any more and I'd be telling you the solution.

I've got plenty more where these came from, if anyone is interested. Yes, I'm a big math nerd :-). Served me damn well in school though ;-)

Re: Re: Re: Smart?

quote:

Originally posted by Flyboy217 Wrong and wrong . Thanks to modern-day CS, many people love thinking along the lines of log2. Get off your log2 horses and start THINKING, people! That's what's nice about these problems... they make you think in a way you're most likely not used to thinking. C'mon, someone solve at least one!

ok ok, i agree I am stupid, but seeing how i have been up since noon yesterday (irish time, it's now 4pm) i guess we all make mistakes

I have done it out.. logically and not the idiot blind, it's 3am and i don't want to program anymore way..:

i think it is do-able with 5 weights:
1,3,7,17,24 How about that?

Re: Re: Re: Re: Smart?

quote:

Originally posted by drizzt81 ok ok, i agree I am stupid, but seeing how i have been up since noon yesterday (irish time, it's now 4pm) i guess we all make mistakes I have done it out.. logically and not the idiot blind, it's 3am and i don't want to program anymore way..: i think it is do-able with 5 weights: 1,3,7,17,24 How about that?

How do you plan on balancing my 100 weight with those? They sum up to only 52 :-)

Re: Re: Re: Re: Re: Smart?

quote:

Originally posted by Flyboy217 How do you plan on balancing my 100 weight with those? They sum up to only 52 :-)

oops today isn;t my day, i was thinking that i had to DETERMINE the weight of yours.. not balance it..

with a sum of 52 i will be able to tell you how much your weight is :/

still not bad, if that had been teh question

try 1,3,7,17,31,79

Re: Smart?

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.]

What's the "worst case"?

Re: Re: Smart?

quote:

Originally posted by AndiH What's the "worst case"?

assume that you develop an algorithm that will test for the second floor at the very end. the worst case is the number of times you'd have to iterate to get to floor 2.

Powered by: vBulletin
Copyright © 2000-2021, Jelsoft Enterprises Ltd.