BrainDen.com - Brain Teasers

mmiguel

Members

142

1

Posts posted by mmiguel

1. Tournament Kings

so it sounds like a round robin tourney.

if he was defeated by more than 1/2 of the players, we can eliminate him as a contender.

then for each person that beat him, again look at the number of losses.

keep on doing so untill you have eliminated all but a single player.

time complexity approximately n* log(2) n.

this is basically the same algorithm i came up with, for finding a single king.

I would use method II, which allows you to see who any given competitor defeated

{

pick a competitor at random.

delete everyone that this competitor defeated (this should be proportional to n operations)

if competitor is last one

{

he is king

}else{

delete him too

}

}

on average, deleting everyone a competitor is defeated reduces the number of competitors left by some proportion.

Thus the number of times this must be done is proportional to the log of n.

Each time this is done, there are something proportional to n operations due to deletions.

The time complexity is there for O(n*log(n)), as phil stated.

I don't think there is an algorithm with better time complexity for finding a single tournament king.

This algorithm does not find all tournament kings though.

Nice work phil!

2. Killville - The ultimate Survivor game

I think the main difference here is that you are the 11th person for whatever group you decide to be in.

I notice that when you register as a pacifist, you are not required to act like a pacifist (the promise they make registered killers make), but I think that this problem likely has more depth in its true solution than just this - not sure if this can even offer you much of an advantage any way.

I'll assume after you register, the game proceeds like the last problem, except there are now 11 people in your group and 10 in the other.

The only real way to survive is if all the killers kill each other (other than you) without any of them meeting you.

How to model the randomness of these meetings?

Assume each valid configuration of pairings is equally likely in each round.

What if there are an odd number of people?

Then I guess one person doesn't meet with anyone.

First assume n is even.

Number of possible pairings is given by multinomial formula (divided by (n/2)! to make ordering of pairings not matter):

n!/((n/2)!2!*2!*2!...)

where there are n/2 many 2!s on the bottom, and (n/2)! i.e.

n!/(2^(n/2)*(n/2)!)

If there are k killers (excluding you) of those n, then the chance of you meeting with one of them is....

well, how many possible ways can you meet with a killer?

need to choose 1 of the k killers

k possibilities for that

The other pairings need to happen now. The rest of the folks now number n-2 and there should be n/2-1 pairings now.

The probability of you dying is therefore

k*(n-2)!/((n/2-1)!2^(n/2-1))/(n!/((n/2)!2^(n/2)))

This simplifies to:

k/(n-1)

This is the chance of you meeting a killer.

The chance of you surviving is one minus this.

1 - k/(n-1)

If n is odd, the you have a 1/n chance of being selected as the odd man out.

The probability becomes:

1/n + (1-1/n)*(1-k/(n-1))

In the beginning, n = 21 and k=10, which gives you a 11/21 ~ 0.52 chance of surviving the first round.

The way you register does not affect your survival chances on the first round (k excludes you, so numerically your choice changes nothing).

Also, if you are a killer, it won't really help you, since you only get the opportunity to kill when you are dying.

In either case, your only hope is to never touch a killer.

If you are a killer and that happens, then each round you were either an odd man out or you killed some pacifists each round.

Are you better off with more pacifists or less pacifists?

Well, if we believe that at each round, if there are n people, the probability of you surviving is

given above, then it is better to have more pacifists around, since those equations increase with n (positive derivative).

Therefore, you don't want to kill pacifists, because they are protecting you by taking bullets for you.

You therefore want to be a pacifist to maximize the number of people who can take bullets for you in the hopes that the killers all kill eachother and other pacifists before ever meeting you.

man... nobody agrees with me lol

3. Killville - The ultimate Survivor game

I think the main difference here is that you are the 11th person for whatever group you decide to be in.

I notice that when you register as a pacifist, you are not required to act like a pacifist (the promise they make registered killers make), but I think that this problem likely has more depth in its true solution than just this - not sure if this can even offer you much of an advantage any way.

I'll assume after you register, the game proceeds like the last problem, except there are now 11 people in your group and 10 in the other.

The only real way to survive is if all the killers kill each other (other than you) without any of them meeting you.

How to model the randomness of these meetings?

Assume each valid configuration of pairings is equally likely in each round.

What if there are an odd number of people?

Then I guess one person doesn't meet with anyone.

First assume n is even.

Number of possible pairings is given by multinomial formula (divided by (n/2)! to make ordering of pairings not matter):

n!/((n/2)!2!*2!*2!...)

where there are n/2 many 2!s on the bottom, and (n/2)! i.e.

n!/(2^(n/2)*(n/2)!)

If there are k killers (excluding you) of those n, then the chance of you meeting with one of them is....

well, how many possible ways can you meet with a killer?

need to choose 1 of the k killers

k possibilities for that

The other pairings need to happen now. The rest of the folks now number n-2 and there should be n/2-1 pairings now.

The probability of you dying is therefore

k*(n-2)!/((n/2-1)!2^(n/2-1))/(n!/((n/2)!2^(n/2)))

This simplifies to:

k/(n-1)

This is the chance of you meeting a killer.

The chance of you surviving is one minus this.

1 - k/(n-1)

If n is odd, the you have a 1/n chance of being selected as the odd man out.

The probability becomes:

1/n + (1-1/n)*(1-k/(n-1))

In the beginning, n = 21 and k=10, which gives you a 11/21 ~ 0.52 chance of surviving the first round.

The way you register does not affect your survival chances on the first round (k excludes you, so numerically your choice changes nothing).

Also, if you are a killer, it won't really help you, since you only get the opportunity to kill when you are dying.

In either case, your only hope is to never touch a killer.

If you are a killer and that happens, then each round you were either an odd man out or you killed some pacifists each round.

Are you better off with more pacifists or less pacifists?

Well, if we believe that at each round, if there are n people, the probability of you surviving is

given above, then it is better to have more pacifists around, since those equations increase with n (positive derivative).

Therefore, you don't want to kill pacifists, because they are protecting you by taking bullets for you.

You therefore want to be a pacifist to maximize the number of people who can take bullets for you in the hopes that the killers all kill eachother and other pacifists before ever meeting you.

"

If n is odd, the you have a 1/n chance of being selected as the odd man out.

The probability becomes:

1/n + (1-1/n)*(1-k/(n-1))

"

should be

1/n + (k/n)*(1-(k-1)/(n-2)) + (n-k-1)/n*(1-k/(n-2))

need to account for odd man out being killer.

also denominator should be n-2, which is what i originally had before, but changed due to nonsensical answers for k=0 and/or k=20, without figuring out exactly what was wrong.

this simplifies to

(n-k)/n = 1 - k/n

amazingly

So survival if n is even is:

1 - k/(n-1)

survival if n is odd is:

1 - k/n

Conclusion from before remains the same.

Chance of surviving first round is still 11/21

haha, intuition could have given those probabilities from the beginning, but i tend to be paranoid with probability, and not try to go by intuition, unless problems are very simple.

4. Killville - The ultimate Survivor game

Subtle variation on the

You are transferred to Killville, by your employer, for a one-year temporary assignment.

Its population comprises 10 Killers and 10 Pacifists.

A Killer immediately guns down any other person he meets.

A pacifist never harms a soul.

When you arrive at Killville, you are required to register, either as a Killer or as a Pacifist.

If you register as a Killer, you are issued a gun and required to act as a Killer.

If you register as a Pacifist, you are given the town's best wishes for good luck and advised to careful.

You desire to live long and prosper. Which way do you register?

Assume all encounters are 1-on-1 and random.

I think the main difference here is that you are the 11th person for whatever group you decide to be in.

I notice that when you register as a pacifist, you are not required to act like a pacifist (the promise they make registered killers make), but I think that this problem likely has more depth in its true solution than just this - not sure if this can even offer you much of an advantage any way.

I'll assume after you register, the game proceeds like the last problem, except there are now 11 people in your group and 10 in the other.

The only real way to survive is if all the killers kill each other (other than you) without any of them meeting you.

How to model the randomness of these meetings?

Assume each valid configuration of pairings is equally likely in each round.

What if there are an odd number of people?

Then I guess one person doesn't meet with anyone.

First assume n is even.

Number of possible pairings is given by multinomial formula (divided by (n/2)! to make ordering of pairings not matter):

n!/((n/2)!2!*2!*2!...)

where there are n/2 many 2!s on the bottom, and (n/2)! i.e.

n!/(2^(n/2)*(n/2)!)

If there are k killers (excluding you) of those n, then the chance of you meeting with one of them is....

well, how many possible ways can you meet with a killer?

need to choose 1 of the k killers

k possibilities for that

The other pairings need to happen now. The rest of the folks now number n-2 and there should be n/2-1 pairings now.

The probability of you dying is therefore

k*(n-2)!/((n/2-1)!2^(n/2-1))/(n!/((n/2)!2^(n/2)))

This simplifies to:

k/(n-1)

This is the chance of you meeting a killer.

The chance of you surviving is one minus this.

1 - k/(n-1)

If n is odd, the you have a 1/n chance of being selected as the odd man out.

The probability becomes:

1/n + (1-1/n)*(1-k/(n-1))

In the beginning, n = 21 and k=10, which gives you a 11/21 ~ 0.52 chance of surviving the first round.

The way you register does not affect your survival chances on the first round (k excludes you, so numerically your choice changes nothing).

Also, if you are a killer, it won't really help you, since you only get the opportunity to kill when you are dying.

In either case, your only hope is to never touch a killer.

If you are a killer and that happens, then each round you were either an odd man out or you killed some pacifists each round.

Are you better off with more pacifists or less pacifists?

Well, if we believe that at each round, if there are n people, the probability of you surviving is

given above, then it is better to have more pacifists around, since those equations increase with n (positive derivative).

Therefore, you don't want to kill pacifists, because they are protecting you by taking bullets for you.

You therefore want to be a pacifist to maximize the number of people who can take bullets for you in the hopes that the killers all kill eachother and other pacifists before ever meeting you.

5. Hard to Resist

Wikipedia has a helpful elementary discussion of resistance [unit = Ohm] of an object as it relates to the resistivity [unit = Ohm-cm] of a material. The easy relationship is that the resistance in Ohms of a 1-cm cube of material is equal numerically to its resistivity in Ohm-cm. Resistance = resistivity x length / area in compatible units.

It thus makes sense to speak of a material having a resistivity that is [or, as in the case of the OP, is not] constant. Thus, in the formula R(p) = 2*sqrt(p), R refers to the resistivity of the material. After you've specified the material's shape, i.e. created an object, it's meaningful to speak of resistance.

Again, the distinction is that resistivity is a property of a material, independent of its shape; resistance is a property of an object. Resistance depends on the object material's resistivity and on the object's shape.

To analyze objects that are not electrically homogeneous [resistivity varies with position in the material], it us usual to break the object up into small, regular, near-homogeneous regions [cubes or near-cubes] and combine the resistances of these regions appropriately to get the resistance of the object.

I was attempting to recreate a problem from an EE final I had 1.5 years ago based on memory, but I realized after I submitted that I had some minor problems in the statement. One which causes the actual calculation to be slightly more difficult than I anticipated (harder integral), and now.... units.

I would argue that the differential volume elements have shape and are objects, but this would not be helpful, because integration involves more than just summing stuff together - it also involves a change in units due to multiplication of differential elements of whatever units belong to the variable of integration. Thus if you intend to use something as part of an integrand, such that after integration it becomes what you originally had, what's in the integrand is actually a density of the original quantity vs. being portions of the original quantity.

The way this is intended to be used is that it should be integrated in sheets perpendicularly to the x-axis. This double integral involves multiplying it by differential area components.

However, resistances do not sum when added in parallel. It is actually conductances that must be added together here.

The total conductance of a cross-sectional element (infinitesimal in the x-axis) is the integral of the reciprocal of R(p). The units of this are area/units of R.

The reciprocal of the entire double integral we just calculated is then taken to get another form of resistive "density". This may then be integrated along the x-axis. This is equivalent to multiplying each individual resistive slice value by length and summing together. The units of resistive slices are (units of R)/area.

Thus (units of R)/area*length = Ohms = units of R/length;

Thus units of R = Ohms * length = Ohm*cm.

These are units of resistivity.

Really, the reason I posted this problem, was because I found it very interesting that one needs to do two reciprocals in the middle of 3 integrals in order to get things to combine right. I was trying to come up with a similar math problem outside of the context of EE, where this is required, but couldn't come up with anything quick enough, so I just went with this one.

Anyway, R(p) is more of a resistive density (per area and times length). This is a well known, widely used concept called resistivity as bonanova pointed out.

In essence, bonanova is correct.

6. Batcave

You guys are funny.

9999

The question wasn't very hard or deceptive, but I thought it was interesting because, you only need to add the mutually exclusive sets of bats and realize that the left eye and right eye of each bat are independent.

This makes the problem straightforward if you stay focused on the important factors, however, I thought that people might make assumptions about correlating blindness in left eyes and right eyes, or attempt to calculate all the possible ways left eyes can go with right eyes with a large number of bats...etc

Out of the box solutions are technically valid, though maybe next time, I'll try to word questions in ways that make it harder to answer in this manner.

7. Tournament Kings

(1) "to quickly find any single tournament king": Does this mean you'll come to me and say, "find me a tournament king"? Or does it mean "Here is a single competitor: see if he/she is a tournament king"? I'm assuming the former.

(2) Method II has a list of lists. Each list operation counts as 1 operation. I assume that means stepping through the main list as well. How is it sorted? Do we get to declare as part of the solution how we wish it were sorted? Do we have to include any such sorting of that list as part of the algorithm's time? (Yes, Method III also has such a list--same questions applies)

(1) The Former

(2) Pulling out any element from any list is one operation (including the main list). For sorting, I didn't really specify a way of identifying competitors in order to sort. Say for example that, you uniquely assign a number from 0 to N-1 for each competitor. In the main list, you can access any element in constant time (O(1)). You can say the xth slot corresponds to competitor x. For the sublists, you can assume whatever sorting you want as long as you consistently assume it is the same way the whole algorithm (unless of course you spend operations to change it in some way).

8. Batcave

A number of bats are in a cave.

â€¢ 4563 bats can see out of their left eye.

â€¢ 3645 bats can see out of the right eye.

â€¢ At least 5436 bats cannot see out of their left eye.

â€¢ At least 6354 bats cannot see out of their right eye.

What is the smallest number of bats that can be in the cave?

9. Longest Increasing Subsequence

Same one I got.

I generated the 1000 numbers in the following manner:

While I have less than 1000 numbers{

Pick a random whole number between 1 and 100000

If I don't already have this number, add it to my list

}

In this case, the longest increasing subsequence was length 55.

Challenge:

Can you determine the probability distribution of the length of longest increasing subsequences for M distinct numbers ranging from 1 to N (generated in the way described above)?

(Cumulative or probability mass function would be good).

I have no idea what the answer to this might look like, but I'm curious if it would turn out to be a common distribution, or perhaps a very uncommon one.

If we can't come up with a good theory, we can get some empirical data.

Perhaps from empirical data, we could come up with a theory!!

If I say " This statement is a lie", it is a paradox. But nothing happens. The universe doesn't explode. Therefore, it is possible for paradoxes to exist. But a paradox by it's very definition defies the laws that govern our universe. Something that defies a universal law cannot exist. Therefore, a paradox existing is a paradox in itself. Sorry if I did something wrong, this is my first paradox I've thought of by myself.

I don't think that a paradox defies any law that governs our universe.

There are no physical laws that say that statements we make or thoughts we conceive are true or false.

There is no physical law saying that a statement has to be either true or false.

A paradox does not defy anything greater than itself --- it defies itself.

It implies something, then implies something else that cannot be true if the first thing it implied were true.

The result is either the first thing is true, or the second thing is, but we don't know which one, and due to symmetry in the way this was asserted, we can make no meaningful conclusion.

Example: A number, x, is equal to one, and it is equal to zero.

This is a paradox, but it is not an interesting one, since it is obvious where the self-inconsistency is.

Most likely, instead of thinking of this paradox as a universe destroying statement of pure contradiction, we would write it off as nonsense.

What attracts people to other paradoxes is that they are less obvious, the implications sound more familiar, and practical thinking builds up the confidence of the person thinking about the paradox, confidence that they understand what is going on. Then at the end, they come across an inconsistency, and are not sure what to believe.

There's my two cents.

here's kind of a depressing paradox.

now imagine creating an exact copy of the whole universe.

if a week from friday you do the exact same thing in both universes, then

what you do a week from friday is pre-determined by the state of the universe.

therefore free will is an illusion.

or if what happens a week form friday is different in both universes, then you have free will, but the principle of identity is invalid at the universal level.

so which would you perfer, free will but no identity, or identity, but no free will?

Essentially, the belief that everything in the future is determined by the state of the universe at any point in the past is called determinism.

This is a philosophical debate that no one can really prove or disprove.

I believe in determinism, but if you think about it, it shouldn't impact how you feel about the universe and carrying out your life.

It is different than the Greek concept of destiny.

The reason being, that no one can possibly predict the future without knowing everything at one point in time.

No physical creature could ever know everything at one point in time, because they would need a physical body to support the mental processes going on to model the external world --- and it would not be possible for them to model all of the information contained within such a physical body by storing that information in the same physical body.

Therefore, no one can tell you it is your destiny to fail or succeed or blah blah blah.

Another thing, is that the phrase "free will" refers to multiple things.

Under determinism, you can still make decisions, it's just that any decision you make is part of the unfolding of the future, and you made them for the deterministic reasons that influenced your mind, which may have been pre-determined, but so what.

What you cannot do, is make a decision which was not caused by anything.

You cannot do something with no motive, no impetus, no influencing factor to make you do that.

Essentially, you cannot be truly random.

Does that prevent you from making decisions you actually care about? No.

You can still choose to vote however you want, to buy what you want, to act like you want etc.

All you should realize is that there are reasons for you doing those things, be it derived from the way you were raised, your experiences in life, the culture around where you were born, etc.

That isn't so depressing, and in many senses of the word "free will", you still have it. You are free to be what you are, even if what you are is a deterministic, evolving process of incredible complexity (just like all life).

Think about it, even these thoughts, and the conclusions you draw from them are part of that evolving process, and your conclusions may influence future decisions. I think that this was determined at the start of the universe, but unknowable by any part of the universe until now.

Essentially, I think that believing in determinism means that randomness doesn't really exist. What we mistake for randomness, is actually just complexity. Both of them are explanations for unpredictability, but I think randomness is more of a superstitious one (and false).

Some folks might say quantum mechanics and stuff proves randomness, but I'm not really convinced - all it shows is that a model that ideally assumes randomness is consistent with experimentation to a high degree of accuracy. It doesn't mean that an explanation that unveils a further degree of complexity in a deterministic way does not exist.

So yeah.

12. Hard to Resist

Does R(p) give me rho?

p is radius from x axis

R(p) is resistance in ohms as a function of radius from x-axis

13. Giant Jelly

That will be correct, right ?

Yup!

14. Longest Increasing Subsequence

I had to write a little program to get:

This 55-long sequence: 42 1318 2259 2339 5355 5709 9393 11299 12230 12641 14000 14289 17990 18498 18638 19218 21861 24351 25846 27141 28105 33535 35597 37723 38410 38833 38994 39295 45392 46268 46480 47318 47877 48856 50628 56087 57163 59481 60292 60868 65793 67511 67635 70066 75993 78289 79572 85182 87577 92362 94360 94963 95425 97491 97684

Same one I got.

15. Which treatment

B for the first 2, A for the third. (weird!)

So which treatment deserves further investment by the charities supporting people with this disease?

16. Giant Jelly

That taking away one measly percentage point in the water proportion corresponds to losing 50 pounds of water?

17. Removing Numbers

9 32 34 35 37 41 55 66 72 73 77 83 84

Nice!

That is a different one than what I had in mind, but it is the same length.

Did you use a general purpose algorithm?

18. Which treatment

You are a doctor in charge of a large hospital, and you have to decide which treatment should be used for a particular disease. You have the following data from last month: there were 390 patients with the disease. Treatment A was given to 160 patients of whom 100 were men and 60 were women; 20 of the men and 40 of the women recovered. Treatment B was given to 230 patients of whom 210 were men and 20 were women; 50 of the men and 15 of the women recovered.

A.) Which treatment is better for men?

B.) Which treatment is better for women?

C.) Which treatment is better for any person, regardless of gender?

19. A simple Monty Hall variant

It's not equally probable that Monty picks all of the remaining doors in the second round as the goat door, even assuming he's attempting to be fair and impartial. If he's being fair, he picks one of the remaining doors which has a goat with equal opportunity to open. You have received information from the first round which should be taken into account.

I'm not following.

I think that is only true if we assume that Monty is making certain assumptions about our strategy, and incorporate that into our strategy.

My strategy does not make that assumption, and I think provides an accurate winning chance.

Does your strategy result in a winning chance greater than 2/5?

I think I do incorporate information from each round, whenever we are in scenarios where Monty's choice modifies probabilities of remaining doors in a meaningful way.

If my selection of 2 doors initially did contain the car, then Monty's choice in first round does not impact further probability calculations.

However, if my selection of 2 doors did not initially contain the car, then Monty's choice in first round increases the chance of one of the two doors in Monty's initial group of 2 of having a car. Previously, given my knowledge, each of those 3 doors had prob 1/5. Now that Monty removed a goat, each of the remaining two doors has prob 3/10. This is info from Monty which I gladly take.

Next I pick one door of the remaining four, and Monty removes another goat from the 3 I didn't pick.

If the car is not behind the door I picked, then Monty's choice communicates useful info, otherwise it does not.

There is no way of knowing whether it does or not at this point, but I'm working around that fact by doing an exhaustive analysis of all cases.

The strategy is to make choices which make it more likely that Monty communicates useful info at each step, and then to act on what door (or set of doors) is most likely to have the car at the final step.

Quote:

"It's not equally probable that Monty picks all of the remaining doors in the second round as the goat door, even assuming he's attempting to be fair and impartial."

Actually, I don't think my strategy even assumes that he selects equiprobably.

It only makes assumptions about what he is allowed to select, and my strategy proceeds forward with whatever selection he makes, regardless of whether he has tendencies to select certain doors more likely due to his belief in my strategy.

For example, if he always chose the lowest numbered door of those he were allowed to select, then my strategy wouldn't change.

etc.etc.

Perhaps I would agree with your answer if I saw it, but right now, I think I'm sticking with mine.

20. Giant Jelly

A giant jelly weighs 100 pounds and is 99% water by weight.

It is set out in the sun and water evaporates until it is 98% water by weight.

How much does the jelly now weigh?

21. Longest Increasing Subsequence

This may need the help of a computer.

Find the longest increasing subsequence of the following 1000 distinct integers.

For a sequence of distinct integers, x_1, x_2, ... x_n,

A subsequence of length k is an ordered group of integers from the above sequence x_i_1, x_i_2, ... x_i_k, which retains order from original sequence, i.e. i_1 < i_2 < ... < i_k.

Note this does not require anything to be consecutive.

An increasing subsequence is a subsequence that increases i.e. x_i_1 < x_i_2 < ... < x_i_k.

The longest increasing subsequence is the increasing subsequence with the longest length.

Good luck!

75004, 56991, 47082, 19635, 42, 89416, 84822, 18366, 8364, 40699, 23120, 7706, 33866, 37458, 86632, 81435, 52136, 3743, 99783, 54643, 62785, 53908, 22213, 85048, 58919, 16044, 71291, 11096, 59245, 56845, 74161, 56308, 23503, 19719, 29656, 86735, 44249, 50773, 14885, 34940, 35646, 3160, 60678, 41299, 59937, 63207, 29450, 89997, 58911, 72711, 64902, 68401, 16899, 4501, 1318, 39683, 66480, 38689, 35095, 80701, 44054, 92075, 33988, 84671, 77537, 8839, 79523, 97433, 8391, 92759, 24585, 89033, 92547, 96080, 26073, 25745, 87630, 73072, 3266, 93177, 93474, 28759, 41164, 2305, 13755, 75280, 2259, 79239, 15564, 27736, 54375, 46184, 3033, 68422, 206, 83226, 8360, 78954, 17911, 37711, 92022, 39688, 66587, 16693, 2339, 92043, 58894, 94182, 93325, 55418, 59121, 57753, 83252, 53228, 68183, 23544, 89165, 57872, 57644, 24952, 22655, 23713, 61634, 68070, 58226, 29503, 71317, 70499, 61070, 9764, 62770, 13522, 36014, 65168, 20298, 43841, 34994, 25063, 86785, 52194, 70311, 81444, 11232, 88436, 83271, 50301, 18761, 29847, 6141, 57699, 61747, 65283, 79193, 80955, 36628, 70822, 66120, 77500, 80812, 18704, 24394, 62520, 15265, 68518, 57144, 69129, 89394, 63356, 5355, 78864, 43417, 22656, 27494, 77278, 19023, 96999, 73467, 68113, 76376, 70153, 95341, 26452, 60308, 25357, 808, 87635, 11781, 92324, 9737, 5709, 2360, 9393, 26000, 5525, 66538, 46059, 11299, 68012, 94219, 20545, 49775, 12230, 38787, 42187, 13954, 79224, 38397, 12641, 18491, 27646, 60193, 43950, 80949, 90488, 93327, 29476, 69194, 83723, 18315, 9124, 82261, 56942, 49866, 14000, 90370, 3396, 77977, 85948, 68664, 60297, 84844, 53267, 67547, 54998, 82753, 3496, 38235, 8761, 3958, 69268, 69156, 24947, 78750, 46293, 23810, 52238, 19946, 44903, 81118, 76939, 82285, 84902, 74667, 26038, 63344, 26064, 51882, 62396, 92332, 71340, 57031, 68813, 21653, 11169, 45501, 3257, 76192, 97946, 20814, 35897, 14289, 91788, 71387, 44558, 83180, 2647, 93610, 96951, 47531, 27440, 47218, 11286, 52915, 93140, 3246, 3433, 39289, 33040, 87405, 79325, 71823, 50094, 30705, 17990, 85064, 81540, 59265, 27807, 62779, 55603, 18992, 59418, 23469, 88774, 23189, 45086, 60996, 10533, 33384, 31671, 42096, 39391, 96782, 84041, 66203, 25541, 37887, 97948, 42245, 93682, 8423, 70414, 53152, 69561, 66511, 28690, 73268, 45783, 59991, 43532, 79262, 3537, 11824, 61333, 94830, 64856, 53646, 59199, 89931, 11691, 86182, 91830, 67544, 51331, 77435, 68866, 44869, 44133, 87167, 22813, 59897, 18498, 46753, 56559, 25556, 86163, 7, 99422, 92240, 88075, 36062, 94790, 63981, 31121, 93567, 21313, 18638, 70913, 10363, 81772, 89573, 19218, 82300, 67325, 68429, 94999, 47454, 271, 78843, 7864, 37438, 13609, 43965, 80713, 56972, 48789, 8213, 52201, 27, 99917, 90747, 85131, 85191, 88148, 68718, 21861, 48539, 76163, 61870, 72247, 6328, 77510, 85161, 25671, 72616, 1494, 69915, 6554, 545, 95768, 37429, 66219, 86730, 47812, 69958, 15057, 95984, 82951, 85727, 4871, 49055, 2670, 87984, 52839, 1390, 24351, 34921, 28927, 8073, 4050, 70171, 85043, 3888, 84466, 27613, 52344, 81876, 41264, 75722, 13727, 78878, 2151, 31297, 19708, 58176, 25846, 47132, 58684, 15779, 43179, 96985, 94527, 50770, 48819, 64608, 51588, 4126, 2349, 11697, 40969, 23669, 18253, 33731, 48139, 88237, 70099, 27141, 55890, 61625, 71161, 73823, 7413, 84892, 8336, 20848, 68198, 44231, 67412, 52152, 99178, 42452, 35439, 63439, 90645, 99836, 39082, 20436, 10443, 7534, 7308, 56095, 78778, 80929, 50848, 4734, 81855, 71427, 49395, 25020, 66462, 13295, 24367, 24077, 29723, 79883, 95739, 51912, 8202, 55787, 71631, 90593, 7549, 52322, 28105, 75281, 94227, 85491, 86745, 14201, 71018, 33535, 35597, 93171, 16611, 39463, 32185, 3766, 41114, 10756, 89390, 48987, 19558, 78031, 61062, 99330, 66976, 51138, 96108, 4417, 13389, 19419, 9359, 97062, 26579, 72817, 12401, 83340, 46928, 20740, 54991, 3744, 28769, 64999, 9641, 17251, 1117, 4656, 37723, 38410, 68597, 72258, 19024, 52105, 75443, 67881, 41368, 39165, 42547, 82381, 9538, 40546, 7034, 56061, 26456, 50629, 53180, 1819, 22409, 3833, 11855, 58669, 27778, 10663, 79657, 38833, 12714, 46197, 21632, 10778, 21247, 38994, 25892, 44301, 55788, 3232, 91229, 75892, 50093, 47105, 59594, 32454, 18488, 25106, 43564, 97242, 28572, 25663, 70039, 91706, 97061, 23416, 29455, 47052, 10566, 12143, 26216, 76453, 29371, 52863, 67569, 58398, 19473, 80787, 57301, 6821, 19269, 14382, 85683, 55428, 1711, 87501, 13629, 33064, 69783, 77117, 43023, 64628, 20502, 93203, 82528, 74892, 26203, 88761, 88038, 46496, 35584, 94159, 64423, 61958, 66594, 53304, 10172, 76705, 56290, 35347, 53466, 15360, 47748, 76041, 32612, 56078, 54272, 78187, 39832, 9834, 16764, 65969, 20091, 66682, 98199, 86121, 8412, 33017, 61921, 63269, 51421, 82766, 39295, 81130, 5731, 46723, 38277, 46094, 45392, 26417, 77154, 92349, 3104, 28788, 97644, 86701, 77673, 93956, 10113, 6253, 46268, 75770, 77218, 7318, 82262, 43967, 64407, 78133, 46480, 12561, 22850, 16789, 16129, 66381, 23275, 86098, 78141, 96486, 22257, 46046, 43321, 81526, 39600, 70788, 75764, 31406, 9363, 94082, 68919, 73381, 12959, 67194, 42059, 95390, 56476, 91971, 47480, 7679, 951, 47318, 31896, 79076, 40517, 83064, 45687, 76070, 98892, 75615, 30432, 44716, 42029, 92085, 11992, 47877, 31085, 48856, 62469, 25805, 58986, 41969, 66607, 9650, 19730, 60892, 1891, 45233, 64014, 27531, 50628, 58999, 25691, 22573, 18814, 56087, 16281, 43278, 70701, 88716, 72662, 8998, 37160, 57163, 53597, 75790, 47438, 13103, 18399, 16465, 85715, 84749, 36760, 59481, 68031, 73626, 39941, 99556, 48286, 631, 22187, 20672, 60292, 13294, 55728, 42836, 60868, 57542, 65793, 67511, 80985, 22778, 3118, 67635, 62144, 537, 60887, 36394, 18717, 1329, 15206, 51603, 76202, 70066, 89487, 58899, 16514, 14226, 83030, 75993, 57830, 6729, 12395, 60987, 6978, 78289, 69405, 81122, 65066, 38164, 4680, 23383, 68997, 39291, 74106, 79572, 66198, 45202, 63754, 314, 61671, 85182, 29085, 70065, 79251, 51533, 27482, 21828, 24281, 98349, 17770, 47250, 87577, 73692, 68513, 11779, 84333, 22388, 92362, 41332, 20732, 42300, 17794, 39118, 98820, 27239, 57836, 61284, 7438, 94360, 21918, 92132, 16495, 76257, 72770, 98012, 56210, 94963, 13159, 64244, 47544, 86650, 85170, 73094, 84045, 87091, 11321, 30070, 24693, 30661, 10754, 65326, 95425, 71842, 86623, 69595, 18271, 53478, 66871, 65051, 51952, 61675, 56902, 38295, 93632, 1422, 67653, 3823, 39370, 37089, 85086, 21651, 34279, 50938, 21553, 66385, 22009, 80771, 49446, 78005, 98473, 24097, 60795, 39608, 48406, 8878, 23676, 93051, 40222, 48557, 76866, 92950, 14235, 47887, 72266, 17844, 84939, 56057, 70925, 25003, 87227, 49456, 51275, 73926, 75899, 21522, 27319, 27803, 37639, 48036, 13770, 64662, 50456, 47995, 2545, 4404, 99938, 27323, 49744, 50772, 61467, 3524, 85916, 3089, 11310, 73870, 61462, 32734, 14100, 55427, 6236, 97491, 61637, 62180, 18231, 10939, 40795, 39273, 37057, 80598, 97684, 38541, 5465, 68441, 31373, 45814, 10120, 20062, 51881, 74221, 2725, 23346, 35000, 61254, 77930, 273, 50381

22. Removing Numbers

Consider the following list of numbers. Your job is to erase as few of those numbers as possible such that the remaining numbers appear in increasing order.

9 44 32 12 7 42 34 92 35 37 41 8 20 27 83 64 61 28 39 93 29 17 13 14 55 21 66 72 23 73 99 1 2 88 77 3 65 83 84 62 5 11 74 68 76 78 67 75 69 70 22 71 24 25 26

23. Tournament Kings

There are a set of N competitors in a tournament.

For every possible pairing of competitors, a battle was fought, with one competitor triumphing over another.

A tournament king is a competitor for which it is true that when comparing to any other competitor,

the king either triumphed over that competitor directly, or the king directly triumphed over another competitor who directly triumphed over that competitor.

Given such a tournament, give an efficient algorithm to quickly find any single tournament king.

You may choose one of three data storage methods:

Method I

You have at your disposal a look-up table which given any pair of competitors, will tell you who won.

Such a look-up is considered one operation.

You may also remove entries from this table, and each removal is considered an operation.

You may simultaneously look-up and remove the entry that is looked up, and that is considered a single operation.

You can make a copy of the initial table, which is N*(N-1)/2 operations (roughly N^2).

Method II

You have a list of N smaller lists, where each of the smaller lists corresponds to a competitor, and the contents of the smaller lists are those the competitor defeated. Looking up/modifying/creating an element from any list is 1 operation.

Method III

You have a list of N smaller lists, where each of the smaller lists corresponds to a competitor, and the contents of the smaller lists are those the competitor was defeated by. Looking up/modifying/creating an element from any list is 1 operation.

What is the time complexity of operations in your algorithm (an estimate of the number of operations as a function of N, where any proportional constant on the whole expression, or constant terms can be ignored)?

What about finding all tournament kings?

Who can give the algorithms with the lowest time complexity?

24. 2 Aces

Remove all cards form a standard deck except for the Aces and Kings.

Randomly select 2 cards from this and deal them to a friend.

She looks at the two cards and says: "After counting the number of red Aces in my hand, I can tell you that this number is greater than zero."

What is the probability that both of her cards are Aces of any color?

25. Hard to Resist

A funky looking piece of electrical material has a length of 2 cm on the x-axis, which is the axis of current flow.

Assume a coordinate system where the object is sitting between x = -1 cm and x = 1 cm.

The cross-sectional shape of the object is circular, with radius varying as a function of x like so:

r(x) = 0.04 + 0.4*x^2+x^4

r(x) is in cm

A differential volume of this material has a resistance of R ohms in the the direction of current flow, where R varies with distance from the x-axis. If the distance of the differential element from the x-axis is p, then R(p) = 2*sqrt(p)

R(p) is in ohms

What is the total resistance of the whole object for current flowing along the x-axis?

Let me know if you want any hints

×

• Activity

• Riddles
×
• Create New...