|
Smart? (pg. 5)
|
View this Thread in Original format
| DigiNut |
| quote: | Originally posted by drizzt81
question about this one:
what do you mean by "sum of elements?"
say we use this set:
SETA {1,2,3,4,5,6,7,8,9,10}
now we can create two subsets:
SUBA {2,3}
SUBB {5}
which both sum to be 5. Is that what you mean? Sorry, but I cannot go about solving the problem if I don't understand the lingo... :/ |
I'm pretty sure that's what it means. Those are both subsets, with the same sum, except that the set you picked has far *more* than two subsets with that some. You only need to prove that there's at least two. |
|
|
| Resnick |
| quote: | Originally posted by DigiNut
Res bud, that one's already been answered! Read back a few posts. |
ya i know, but they said the answer is 15...which i dont see how it can be
edit BWAHHAHA sorry ive done too much programming, the answer is 14, but thats because u can use elimination to say that u dont have to test the last case, because it has to be that..so u can just assume its that...where in, say java u still have to do it..my bad
but the answer is log[base 2] of 100, u just multiply by 2 since theere are 2 eggs |
|
|
| DigiNut |
| quote: | Originally posted by Resnick
ya i know, but they said the answer is 15...which i dont see how it can be |
I thought it was 14. The answer's been explained: drop the first egg at floor 14, then 27, 39, 50, 60, 69, 77, 84, 90, 95, 99. Then once it breaks, just count up from the last floor where it didn't break (or from 96 if it never broke). The max you'll ever have to do is 14. |
|
|
| Resnick |
| quote: | Originally posted by DigiNut
I thought it was 14. The answer's been explained: drop the first egg at floor 14, then 27, 39, 50, 60, 69, 77, 84, 90, 95, 99. Then once it breaks, just count up from the last floor where it didn't break (or from 96 if it never broke). The max you'll ever have to do is 14. |
nah too complicated, drop 1 at 50, if it breaks do it at 25...and so on...do it for both
edit* check my last post's edie..lol sorry too lazy to repost |
|
|
| Flyboy217 |
| quote: | Originally posted by Resnick
ok how is the first building one not log n??
first of all, is N unique to both eggs or each egg has its own different height? cuz it doesnt really say, if it is not unique, then its logn of each...
taking worse case, log[base2] n = 8 ..*2 = 16 which is the right answer |
First, the problem says that each breaks from the height N (i.e., they are the same). See DigiNut's reply for a solution requiring only 14 drops. Also, log2(100) = 7. This solution would work if you had 7 eggs, but you don't. Try actually devising a solution using binary search and you'll see why it fails (both of your eggs will be broken before you learn anything).
| quote: |
the genie one, u can just do anything and assume at inf it will work out???? i dunno
|
This is a tempting (but wrong) assumption. It is true that a random solution will work approaching 100% probability, but this is not a "guaranteed" solution. As an analogy, imagine the real number line. If I ask you to pick a point on it at random, you will with 100% probability choose a non-integer (or, for that matter, irrational) value. This does not preclude you from picking an integer though. Similarly, 100% of the integers contain the digit "3", but this doesn't mean that they all do. It's an interesting and widely-misunderstood point in mathematics...
| quote: |
and the coin one depends on the coins you choose.... it asks for the most expensive u can buy with exact change?? so if u pick coin A = 10^10 $ then thats more expensive than a lower denomination
edit* ok i read the question wrong, but it still depends on the coins, for instance, if u pick 2,3, then most expensive is 1$ cuz anything after that u have exact change for, now if u pick 10$ and 9$ u can buy 11$ and u wont have exact change, but 11>A>b , but in first case 1$ |
Yes, the value is dependent on A and B; I'm looking for a value in terms of A and B. (You may tell me, for example, that the value of the most expensive item you can't buy is A*B-3. But that's not right :-)) |
|
|
| Flyboy217 |
| quote: | Originally posted by Resnick
nah too complicated, drop 1 at 50, if it breaks do it at 25...and so on...do it for both
edit* check my last post's edie..lol sorry too lazy to repost |
You only have two eggs though. Suppose your first one breaks at 50, and then your next one breaks at 25. Now what? You're out of eggs... game over. That's the point of the problem. |
|
|
| Resnick |
| quote: | Originally posted by Flyboy217
First, the problem says that each breaks from the height N (i.e., they are the same). See DigiNut's reply for a solution requiring only 14 drops. Also, log2(100) = 7. This solution would work if you had 7 eggs, but you don't. Try actually devising a solution using binary search and you'll see why it fails (both of your eggs will be broken before you learn anything).
|
oh i though u had infinite eggs...k |
|
|
| Flyboy217 |
| quote: | Originally posted by DigiNut
I'm pretty sure that's what it means. Those are both subsets, with the same sum, except that the set you picked has far *more* than two subsets with that some. You only need to prove that there's at least two. |
This is correct. As a point of admission, I will say that "same subset sums" is completely nonstandard lingo. I'm sorry, that wasn't clear. |
|
|
| Resnick |
| quote: | Originally posted by Flyboy217
This is a tempting (but wrong) assumption. It is true that a random solution will work approaching 100% probability, but this is not a "guaranteed" solution. As an analogy, imagine the real number line. If I ask you to pick a point on it at random, you will with 100% probability choose a non-integer (or, for that matter, irrational) value. This does not preclude you from picking an integer though. Similarly, 100% of the integers contain the digit "3", but this doesn't mean that they all do. It's an interesting and widely-misunderstood point in mathematics...
|
wtf? why would it be 100% prob that i pick a non-integer? why cant i pick 3 or 4or 5?
| quote: | Originally posted by Flyboy217
Yes, the value is dependent on A and B; I'm looking for a value in terms of A and B. (You may tell me, for example, that the value of the most expensive item you can't buy is A*B-3. But that's not right :-)) |
but re-read my post, i just proved that u cant find a general solution in terms of A and B , so either someothings wrong with the questino, or with my proof |
|
|
| DigiNut |
I think I figured out the answer to number 2, it's 5 weights.
If you have a weight, there are 3 things you can do with it: put it on the left, put it on the right, or put it nowhere. This gives you 3^n (where n is the number of weights) possible options AT MOST. You also have to account for the fact that doing nothing with all weights gets you zero, which won't balance anything, and that for each setup there's also a mirror image setup. So the maximum number of different total weights you can get from n weights is (3^n - 1)/2. Obviously to get the maximum, you have to pick the proper weights...
For 4 weights, this gets 40; for 5, it gets you 121, which is enough.
Flyboy, you didn't say we had to actually identify the weights, and I'm not sure how to go about doing that... I'm pretty sure my answer above is correct, though.
Edit: actually, I think it would make sense to pick those weights as powers of 3, i.e. 1, 3, 9, 27, and 81... would that do it? |
|
|
| Resnick |
k flyboy i think i know what your saying about the irration number everytime, but thats the limit as u pick infinite random numbers...its not an actualy value, which is what im saying is the solution to the genie one...
but its different case, all im saying is at the end it will work at, and in fact it will
but ur saying 'the limit' or irrational / ration will go to infinite, so ur doesnt actually reach 100% irrational, where as mine does
forget it tho, tell us the answer :) |
|
|
| Flyboy217 |
| quote: | Originally posted by Resnick
wtf? why would it be 100% prob that i pick a non-integer? why cant i pick 3 or 4or 5? |
The point is that you *can* pick 3 or 4 or 5, but that if you're choosing truly randomly, then you will pick one of those with exactly 0% probability. I can direct you to some neat sites on this topic.
| quote: |
but re-read my post, i just proved that u cant find a general solution in terms of A and B , so either someothings wrong with the questino, or with my proof |
Not sure what your proof is meant to show. There are plenty of functions for which f(A,B) is less than A and B in some cases, while being greater than A and B in others. f(A,B) = A*B is one such example (although not for the natural numbers). |
|
|
|
|
