| Forum Index > General Forum |
|
gyth
657 Posts
Given a 3-regular graph that has a Hamiltonian circuit, we want to show it has to have at least one more... ...sum{X(H)} = 0. Q.E.D. This is a classic result in graph theory. What was the result? Did that mean it did or didn't have at least one more? P.S. BOLD THE QUESTIONS + Show Spoiler [the solutions/guesses] + spoiler the solutions/guesses | ||
|
Alventenie
United States2147 Posts
On April 11 2011 12:22 hacklebeast wrote: + Show Spoiler + #2 knows. If 2 and three had the same color, then 1 would know and would shout out his (the opposite of what both of them have). but because 1 is silent, 2 and 3 are different. So 2 can look at three and say the opposite. Trying to think of some that fall under a "math" category... easy: + Show Spoiler + You have a jar filled with 100 black marbles and a jar filled with 100 white marbles. You can rearrange the marbles any way you like as long as all of the marbles are in jars. After sorting, you randomly select one jar and then randomly select one marble from the jar. If the marble is white you win. What are your maximum odds for winning? harder (not math related): + Show Spoiler + You are blind folded and presented with 100 coins. You are told that 50 are heads and 50 are tails. How can you split them into two piles so that the two piles contain an equal amount of heads? You can not distinguish the orientation of the coins by touch. harder: + Show Spoiler + You have two cups with 10 teaspoons of tea in one and 10 teaspoons of coffee in the other. You take one teaspoon from the tea cup and put it in the coffee cup, then take a teaspoon of the coffee-tea mix and put it in the tea cup. Is there more coffee in the tea cup, or tea in the coffee cup? Easy: + Show Spoiler + put 99 white ones in the jar with 100 black and leave 1 white one by itself harder (not math related): + Show Spoiler + Move 50 coins to a separate pile, flip them all over i dont know about the last one =/, i would guess but that defeats the purpose =P | ||
|
gyth
657 Posts
W in one jar, 99W 100B in the other. (1/2)(1)+(1/2)(99/199) ~74.87% | ||
|
Murderotica
Vatican City State2594 Posts
+ Show Spoiler + You add 1 teaspoon of pure tea. You take out 1/11th tsp of tea and 10/11ths of coffee. You initially put in 11/11th of tea so you have 10/11ths of tea left over. It's equal. | ||
|
LastPrime
United States109 Posts
On April 11 2011 12:24 gyth wrote: graph theory.+ Show Spoiler + Given a 3-regular graph that has a Hamiltonian circuit, we want to show it has to have at least one more... ...sum{X(H)} = 0. Q.E.D. This is a classic result in graph theory. What was the result? Did that mean it did or didn't have at least one more? If there was only one H, sum{X(H)} would not equal 0. So there has to be another one at least. In fact, there has to be two more at least since it is not possible to have sum{X(H)} equal to 0 mod 2 with two H's either. | ||
|
RandomAccount139135
40 Posts
| ||
|
Reason
United Kingdom2770 Posts
On April 11 2011 12:22 hacklebeast wrote: harder: + Show Spoiler + You have two cups with 10 teaspoons of tea in one and 10 teaspoons of coffee in the other. You take one teaspoon from the tea cup and put it in the coffee cup, then take a teaspoon of the coffee-tea mix and put it in the tea cup. Is there more coffee in the tea cup, or tea in the coffee cup? On April 11 2011 12:36 Murderotica wrote: Harder math: + Show Spoiler + You add 1 teaspoon of pure tea. You take out 1/11th tsp of tea and 10/11ths of coffee. You initially put in 11/11th of tea so you have 10/11ths of tea left over. It's equal. Well, you take 1 teaspoon of pure tea and put it into the coffee cup. You then take a contaminated mix that is roughly 10 parts coffee to 1 part tea from the coffee cup and put that into the tea cup. There is clearly more tea in the coffee cup than there is coffee in the tea cup. Problem ? This is the easiest thing in the world lol.. you seemed halfway there Murderotica.. unless I'm missing something? | ||
|
xxpack09
United States2160 Posts
On April 11 2011 11:53 gyth wrote: + Show Spoiler + Sound travels faster than nerve impulse. http://www.braingle.com/brainteasers/19579/madadian-assassin.html Not that an assassin wouldn't silence their shot. And even hearing a shot doesn't imply you were the one hit. That's REALLY dumb Especially because that time difference is negligible unless you're the flash... | ||
|
Aequos
Canada606 Posts
On April 11 2011 12:22 hacklebeast wrote: + Show Spoiler + #2 knows. If 2 and three had the same color, then 1 would know and would shout out his (the opposite of what both of them have). but because 1 is silent, 2 and 3 are different. So 2 can look at three and say the opposite. Trying to think of some that fall under a "math" category... easy: + Show Spoiler + You have a jar filled with 100 black marbles and a jar filled with 100 white marbles. You can rearrange the marbles any way you like as long as all of the marbles are in jars. After sorting, you randomly select one jar and then randomly select one marble from the jar. If the marble is white you win. What are your maximum odds for winning? harder (not math related): + Show Spoiler + You are blind folded and presented with 100 coins. You are told that 50 are heads and 50 are tails. How can you split them into two piles so that the two piles contain an equal amount of heads? You can not distinguish the orientation of the coins by touch. harder: + Show Spoiler + You have two cups with 10 teaspoons of tea in one and 10 teaspoons of coffee in the other. You take one teaspoon from the tea cup and put it in the coffee cup, then take a teaspoon of the coffee-tea mix and put it in the tea cup. Is there more coffee in the tea cup, or tea in the coffee cup? Easy: + Show Spoiler + Put one white marble in 1 jar, put all the other marbles in the other. You have either a 0.5 + 99/100 % chance of winning, which is maximal. Harder: (Not math related) + Show Spoiler + Divide the pile into two smaller ones of 50. One pile will contain n heads, the other will contain 50-n heads. Flip all the coins in one pile, which will reverse it to being n heads in both. Harder: + Show Spoiler + My god, this one is so annoying. I hate working with it - but the solution is as follows: First Step: A  T B:10C1TSecond Step: A T B:100/11C, 10/11T TEASPOON: 1/11th T, 10/11ths CThird Step: A:100/11T,10/11C B:100/11C, 10/11T It is identical. Edit: Fixed the numbers in the first one. | ||
|
RandomAccount139135
40 Posts
| ||
|
Murderotica
Vatican City State2594 Posts
On April 11 2011 12:52 Reason wrote: Well, you take 1 teaspoon of pure tea and put it into the coffee cup. You then take a contaminated mix that is roughly 10 parts coffee to 1 part tea from the coffee cup and put that into the tea cup. There is clearly more tea in the coffee cup than there is coffee in the tea cup. Problem ? This is the easiest thing in the world lol.. you seemed halfway there Murderotica.. unless I'm missing something? Lol let me explain it this way. Let's say that there are 1100x in one cup and 1100y in the second. You take 1/10th of the 1100x and add it to the 1100y. This means your cups have: (1100-110)x and 1100y + 110x So, then you take 1/11th (remember there are now 11 teaspoons in the y cup so taking 1 out will be taking out 1/11th of the total inside of it) of the y/x mixed cup and add it to the x cup. So you have: (1100-110)x + (1100y + 110x)/11 and (1100y + 110x) * 10/11 This gives us: 1100x - 110x + 100y + 10 x = 1100x - 100x + 100y = 1000x + 100y And (1100y + 110x)*10/11 = (11000y + 1100x)/11 = 1000y + 100x So there is 100x in the y cup and 100y in the x cup. Equal amounts of each. Rofl problem? This is the easiest thing in the world, remember? | ||
|
jackknight
United States51 Posts
+ Show Spoiler + For Question 3, At beginning 1) Start 7 minute and 11 Minute 2) As 7 minute end, re-flip it Total Time: 7 Minute 3) As 11 minute end, re-flip the 7 minute at THAT MOMENT Total Time: 11+4 = 15 Minute | ||
Seeker
Where dat snitch at?37027 Posts
| ||
|
Earll
Norway847 Posts
You have to walk into 1 of 2 doors, where one will lead to certain instantenous death, and the other will lead to a life full of starcraft 2 and happy things. Each door is guarded by an all knowing all powerfull zergling(A crackling, if you will). One of the zerglings will always lie and the other will always tell the truth. You can ask One of them, 1 question. What do you ask to figure out what door to take? (You obviously do not know what zergling lies, and what door the zergling guards holds no relation to him lying or telling the truth.) | ||
|
aznagent
Hong Kong166 Posts
On April 11 2011 14:26 Earll wrote: This might be something everyone knows the answer to and might already have been posted(though I cant say I have seen it and I think i have read all of the 16 pages) But here goes. You have to walk into 1 of 2 doors, where one will lead to certain instantenous death, and the other will lead to a life full of starcraft 2 and happy things. Each door is guarded by an all knowing all powerfull zergling(A crackling, if you will). One of the zerglings will always lie and the other will always tell the truth. You can ask One of them, 1 question. What do you ask to figure out what door to take? (You obviously do not know what zergling lies, and what door the zergling guards holds no relation to him lying or telling the truth.) I heard this question b4... but not in the form of starcraft, you are awesome ^_^ + Show Spoiler + You ask either zergling which door the other zergling considers to be starcraft heaven | ||
|
Zeroes
United States1102 Posts
On April 11 2011 14:26 Earll wrote: This might be something everyone knows the answer to and might already have been posted(though I cant say I have seen it and I think i have read all of the 16 pages) But here goes. You have to walk into 1 of 2 doors, where one will lead to certain instantenous death, and the other will lead to a life full of starcraft 2 and happy things. Each door is guarded by an all knowing all powerfull zergling(A crackling, if you will). One of the zerglings will always lie and the other will always tell the truth. You can ask One of them, 1 question. What do you ask to figure out what door to take? (You obviously do not know what zergling lies, and what door the zergling guards holds no relation to him lying or telling the truth.) + Show Spoiler + If I ask the other Zergling which is the door to starcraft heaven, which will he tell me? and then take the opposite door | ||
|
stepover12
United States175 Posts
40. Suppose that 20 starcraft pros played in a tournament where each player competed against every other player exactly once. The result of each game is only win/lose, no draw. Is it always possible (regardless of results) to name the players 1,2,3,...,20 so that player 1 defeated player 2, player 2 defeated player 3,... player 19 defeated player 20? Give a proof or a counterexample. | ||
|
YejinYejin
United States1053 Posts
On April 11 2011 09:47 Akari Takai wrote: BTW, I hate you OP. I've wasted my whole day figuring out each and every one of these.  I guess I'm the kind of person described in this comic strip... ![[image loading]](http://imgs.xkcd.com/comics/nerd_sniping.png) HERE ARE THE ANSWERS TO ALL OF THE QUESTIONS POSTED! (hopefully they're all right...) + Show Spoiler + Problem 1+ Show Spoiler + + Show Spoiler + you have a 5-liter jug and a 3-liter jug and a pool of water. How can you produce exactly 4 liters of water? (a classic one, appeared in a "die hard" movie lol) 1. Fill the 3-liter bottle and pour it into the empty 5-liter bottle. 2. Fill the 3-liter bottle again, and pour enough to fill the 5-liter bottle. (This leaves exactly 1 liter in the 3-liter bottle.) 3. Empty the 5-liter bottle; pour the remaining 1 liter from the 3-liter bottle into the 5-liter bottle. 4. Fill the 3-liter bottle and pour it into the 5-liter bottle. The 5-liter bottle now has exactly 4 liters. Problem 2+ Show Spoiler + + Show Spoiler + Suppose we have 10 bags, each bag contains 10 coins. One of the bags contains counterfeit coins, the other 9 bags contain real coins. Each counterfeit coin weighs 0.9 grams. Each real coin weighs 1.0 grams. If we have an accurate scale that give exact weight of whatever is placed on, could we determine which bag contains the counterfeit coins with just _one_ weighing? Place 1 coin from the first bag, 2 coins from the second bag, 3 coins from the third bag, etc. on the scale. If each coin were authentic, the total weight should be 55 grams. If the counterfeit coin is in bag #1, the total weight will be 54.9 grams. If the counterfeit coin is in bag #2, the total weight will be 54.8 grams. If the counterfeit coin is in bag #3, the total weight will be 54.7 grams. etc... Problem 2b+ Show Spoiler + + Show Spoiler + Suppose we have 4 bags, each bag contains 10 coins. Some of the bags contains counterfeit all coins, some contain all real coins. We don't know how many bags of counterfeit coins there are. Each counterfeit coin weighs 0.9 grams. Each real coin weighs 1.0 grams. If we have an accurate scale that give exact weight of whatever is placed on, could we determine which bag(s) contains the counterfeit coins with just _one_ weighing? Place 1 coin from the first bag, 2 coins from the second bag, 4 coins from the third bag, and 8 coins from the fourth bag. If all coins were authentic, the total weight should be 15 grams. Bag 1 only - 14.9 grams Bag 1,2 only - 14.7 grams Bag 1,3 only - 14.5 grams Bag 1,4 only - 14.1 grams Bag 1,2,3 only - 14.3 grams Bag 1,2,3,4 only - 13.5 grams Bag 2 only - 14.8 grams Bag 2,3 only - 14.4 grams Bag 2,4 only - 14.0 grams Bag 2,3,4 only - 13.6 grams Bag 3 only - 14.6 grams Bag 3,4 only - 13.8 grams Bag 4 only - 14.2 grams etc. Problem 3+ Show Spoiler + + Show Spoiler + You have 2 hour-glasses, one measuring 7 minutes and the other 11 minutes. You want to boil an egg for exactly 15 minutes. Can you use the 2 hour-glasses to measure exactly 15 minutes? Note: your hands are so high APM it takes infinitely small amount of time to flip an hour glass. Start with both hourglasses running. When the 7 minute hourglass runs out, invert it. 4 minutes later the 11 minute hourglass will run out. At this point 11 minutes will have elapsed and if you turn over the 7 minute hourglass now, it will be 4 minutes until it runs out, exactly 15 minutes. 11 + 4 = 15. Note: FUCK YEAH, INFINITE APM FTW. Time to go play zerg and burrow roach micro like a BOSS! Problem 4+ Show Spoiler + + Show Spoiler + A very accurate clock has an hour hand and a minute hand. Both hands are (infinitely) thin. At 12 noon, the two hands coincide exactly. What is the next (exact) time at which the two hands will again coincide? In t hours, the minute hand completes t revolutions. In the same amount of time, the hour hand completes t/12 revolutions. The first time the minute hand and the hour hand overlap, the minute hand would have completed 1 lap more than the hour hand. So we have t = t/12 + 1. This implies that the first overlap happens after t = 12/11 hours (~1:05 pm). Problem 5+ Show Spoiler + + Show Spoiler + Suppose a rectangle can be (in some way) entirely covered by 25 circular disks, each of radius 1. Can the same rectangle be covered by 100 disks of radius 1/2? Prove your answer. Note: overlaps allowed of course. Let's take the simplest example of this form. Let's take a square (just another kind of rectangle ^^) with a diagonal of 2 (each side of the square is the square root of 2). This circle is fully covered by one circle with radius of 1. Can this rectangle be covered by 4 times as many circles of half the radius? First break up the square into 4 quarters. This forms 4 more squares with a diagnoal of 1. Each of our 4 circles with a radius of 1/2 will cover each of the 4 squares. So the answer to the brainteaser is yes. Problem 6+ Show Spoiler + + Show Spoiler + A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph. On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes. The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following: "I can see someone who has blue eyes." Who leaves the island, and on what night? There are no mirrors or reflecting surfaces, nothing dumb. It is not a trick question, and the answer is logical. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something silly like creating a sign language or doing genetics. The Guru is not making eye contact with anyone in particular; she's simply saying "I count at least one blue-eyed person on this island who isn't me." And lastly, the answer is not "no one leaves." On the 100th day, all 100 blue-eyed people will leave. If there is only one blue-eyed person, he will see that there is no other blue-eyed person and then will leave the island, knowing he is the one being referred to. If there are 2 blue-eyed people, they will see the other and know if they are the only blue-eyed person that they will leave that night. If they do not, then both of them leave on the 2nd night. This process repeats until on the 100th day, all 100 blue-eyed people leave. The process is difficult to understand intuitively and it relies on common knowledge ordered logic. http://en.wikipedia.org/wiki/Common_knowledge_(logic) Problem 7+ Show Spoiler + + Show Spoiler + Suppose we have 9 coins that look the same and feel the same. But exactly one of them is counterfeit and it weighs less than a real coin. Can we identify the counterfeit coin among the 9 coins with just two weighings on an accurate balance scale? Take any eight of the nine coins, and load the scale up with four coins on either side. If the two sides are equal, then the remaining coin is the fake. If the two sides are not equal, then the remaining coin is a real coin and the fake one is on one side or the other of the scale. Now unload at the same time a single coin from each of the scales. If the scales balance, the bad coin is one of the two which you just withdrew. If the scales remain unbalanced, the fake is still on the scales. As you remove good coins, you can add them to the "good coin pile" which began with the first isolated coin. Once you have found the two coins which when removed balance the scales, or if they are the final two and the scales are still unbalanced, you take one of those two and weigh it against a known good coin. If they balanced on the second loading of the scales, or if they don't, you have now with only two loadings of the scales CORRECTLY IDENTIFIED THE FAKE COIN. Problem 8+ Show Spoiler + + Show Spoiler + If you have 2 pieces of string that when you light in fire take an hour to burn how do you measure 45 minutes? Lift both ends of String 1 on fire and one end of String 2 on fire. String 1 will burn out in 30 minutes and 30 minutes will have burned up on String 2. Light the other end of String 2 on fire. String 2 will finish burning up in 15 minutes, which will be at 45 minutes exactly. 30 + 15 = 45. Problem 9+ Show Spoiler + + Show Spoiler + When a prime number greater than 32 is divided by 30, you get a remainder R. If R is not equal to 1, must the remainder R be a prime number? Why or why not? First let's identify remainders of 30 that are prime and non-prime. Non-Prime - 2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28 Prime - 7,11,13,17,19,23,29 We should then strive to identify why a prime number greater than 32 divided by 30 (with a non-1 remainder) will NOT result in a remainder that is non-prime. First, we should remove any remainder that has a mulitple of 2, as 32/30, 34/30, 36/30, 38/30, could not be a prime number as it has a common factor of 2. Non-Prime - 3,5,9,15,21,25,27 Prime - 7,11,13,17,19,23,29 Second, we should remove any remainder that has a multiple of 5, as 35/30, 40/30, 45/30, could not be a prime number as it has a common factor of 5. Non-Prime - 3,9,15,21,27 Prime - 7,11,13,17,19,23,29 Third, we should remove any remainder that has a multiple of 3, as 33/30, 36/30, 39/30, could not be a prime number as it has a common factor of 3. Non-Prime - Prime - 7,11,13,17,19,23,29 Thus, because we are using prime numbers as our dividend, the remainder must always be prime. Problem 10+ Show Spoiler + + Show Spoiler + Sultan summons all of his viziers. He says "Tomorrow I am going to put all of you in a line and place a hat on each of your heads. The hat will either be red or blue. You will not be able to see the hat on your head. However, because you are my royal viziers, you must be able to tell me what color hat is on your head. Only one of you may be wrong - otherwise, you all die. You can tell me the color of your hat in any order, and you are only allowed to say the color and nothing else - no communication with other viziers." How do the viziers keep their jobs and their lives (what is their strategy)? The viziers can use a binary code where each blue hat = 0 and each red hat = 1. The prisoner in the back of the line adds up all the values of the hats he sees before him and if the sum is even he says "blue" and if the sum is odd he says "red". This prisoner has a 50/50 chance of having the hat color that he said, but each subsequent prisoner can calculate his own color by adding up the hats in front (and behind after hearing the answers) and comparing it to the initial answer given by the prisoner in the back of the line. Problem 11+ Show Spoiler + + Show Spoiler + Can a convex 13-gon be tiled (partitioned) by parallelograms? (A 13-gon is a solid polygon of 13 sides. "Convex" means the straight line segment connecting any 2 points of the polygon lie inside the polygon. "Tile" meaning the overlaps between parallelograms can only happen at their edges.) The answer is no. Let us choose one side of the 13-gon, and consider the parallelogram it belongs to (it is clear that there are not two such parallelograms). The opposite side of this parallelogram is also a side of a second parallelogram. This second parallelogram has another side parallel to the first, and we can continue this "chain" of parallelograms until we arrive at a side of the 13-gon. This side is therefore parallel to the side with which we started and since a convex polygon cannot have three mutually parallel sides it is parallel to no other side of the convex 13-gon. Problem 12+ Show Spoiler + + Show Spoiler + You are in the final round of a game show and are shown 3 doors. You will win whatever is behind the door you eventually choose. Behind 1 door is a car, and behind the other 2 are goats. You make your original choice and the presenter opens one of the other 2 doors to reveal a goat. He then gives you the chance to switch to the other remaining closed door, or to open your original choice. Should you switch? Assuming the host behavior is that the car is placed randomly behind any door, and the host must open a door revealing a goat regardless of the player's initial choice, and if two doors are available the host chooses randomly. It is advantageous to switch because there is a 2/3rds probability of winning the car when you switch. http://en.wikipedia.org/wiki/Monty_Hall_problem#Solutions Problem 13+ Show Spoiler + + Show Spoiler + Can every natural number (e.g.1,2,3,...) be expressed as a sum of distinct powers of 2 (e.g.1,2,4,8,...)? If so, is that expression unique (ignoring order of the terms in the sum)? Every natural number can be expressed as a sum of distinct powers of 2. The expression is unique if written out in the form 2^x + 2^x+1 + 2^x+2, etc. regardless of order. But if order is disregarded other forms of expression a sum of distinct powers of 2 (binary) would not be unique. Problem 14+ Show Spoiler + + Show Spoiler + What is the maximum number of intersection points between 10 distinct lines on a plane? You get the maximum number of points of intersection when there are no parallel lines. You can solve this problem by a recursion. Let a(n) be the maximum number of points of intersection of n lines. Clearly a(2) = 1. Suppose you known a(n) for some integer n, then if you add another line, not parallel to any other lines, you get N more points of intersection: a(n+1) = a(n) + n So, a(n) = n(n-1)/2 for n ≥ 2 a(10) = 45. So, 45. Problem 15+ Show Spoiler + + Show Spoiler + Let A be a collection of 100 distinct integers. Can you select 15 integers from A so that the difference of any two numbers from this selected subset is divisible by 7? The answer is yes if the collection of 100 distinct integers is consecutive. As you could start with the largest number in the set, and set up the recursion A(n+1) = n - 7, such that you fill a set of 15 numbers that have a difference of seven between terms in the set. If the collection of 100 distinct integers is for example multiples of 3s (3,6,9,12,15,18,21,etc.) then no pair of numbers subtracted will be divisible by 7. Problem 16+ Show Spoiler + + Show Spoiler + A room has 100 boxes labeled 1 thru 100. The names of 100 prisoners have been placed in these boxes by the warden. The prisoners shall visit the room one by one. Each prisoner is allowed to inspect the contents of at most 50 boxes, one after the other and leave the room with no communication with other prisoners. If the prisoner discovers his own name in the boxes he inspects, he is released. The prisoners are allowed to collude before hand and devise a strategy to maximize the chances of releasing each and every prisoner. What is their strategy? The prisoners must agree on a random labeling of the boxes by their own names. When admitted to the room, each prisoner inspects his own box (that is, the box with which his own name has been associated). He then looks into the box belonging to the name he just found, and then into the box belonging to the name he found in the second box, etc. until he either finds his own name, or has opened 50 boxes. P.S. Here's how that ~30% probability is calculated. Let k > n and count the permutations having a cycle C of length exactly k. There are (2n k) ways to pick the entries in C, (k-1)! ways to order them, and (2n-k)! ways to permute the rest; the product of these numbers is (2n)!/k. Since at most one k-cycle can exist in a given permutation, the probability that there is one is eactly 1/k. It follows that the probability that there is no long cycle is 1 - 1/(n+1) - 1/(n+2) - ... - 1/(2n) = 1 - H(2n) + H(n) where H(n) is the sum of the reciprocals of the first n postivie integers, aproximately ln n. Thus our probability is about 1 - ln 2n + ln n = 1 - ln , and in fact is always a bit larger. For n = 50 we get that the prisoners survive with probability ~31%. Problem 17+ Show Spoiler + + Show Spoiler + You are the most eligible bachelor in the kingdom, and as such the King has invited you to his castle so that you may choose one of his three daughters to marry. The eldest princess is honest and always tells the truth. The youngest princess is dishonest and always lies. The middle princess is mischievous and tells the truth sometimes and lies the rest of the time. As you will be forever married to one of the princesses, you want to marry the eldest (truth-teller) or the youngest (liar) because at least you know where you stand with them. The problem is that you cannot tell which sister is which just by their appearance, and the King will only grant you ONE yes or no question which you may only address to ONE of the sisters. What yes or no question can you ask which will ensure you do not marry the middle sister? Clarification: The answer you get wil ONLY be “yes” or “no” and you cannot ask a question that seeks a different answer or communicate with the daughters in any other way. Ask princess A "Is princess B older than princess C?" If princess A is the middle princess, it doesn't matter which of the other two we choose. If princess A is the eldest, we marry the one she indicates is younger. If princess A is the youngest, we want to marry the elder of the other two, which means marrying the one she says is younger. So if the answer is yes, we always marry princess C, and if it's no, we always marry princess B. Problem 18+ Show Spoiler + + Show Spoiler + A ship had distributed the crew names on the many lifeboats onboard. Each lifeboat had equally many men, and there were exactly the same amount of men in each boat as there were boats in all. During a storm the ship began to sink, and 10 lifeboats were destroyed by the waves with an unknown amount of men. The remaining crew pulled an additional 10 men into each of the remaining lifeboats. How many drowned? Let x be the number of boats/men. There are x^2 people in total. 10 lifeboats sank which each have x men; however, we saved 10 men in each of the remaining boats 10(x- 10). So this brings our expression to x^2 - 10x + 10(x-10) or x^2 - 10x + 10x - 100 or x^2 - 100. Since x^2 is the number of people we started with and x^2 - 100 is the total number of survivors, we know that we have lost 100 people. Problem 19+ Show Spoiler + + Show Spoiler + 10 pirates found a loot of 100 gold pieces, and decided to split it the following way: the captain offers how to split it, then they hold a vote and if at least half of them agree that is the split, else (more than half disagree) they kill him and the next in command tries, they vote again, and so on. the pirates want to stay alive, get the most gold, and kill the most of the other pirates in that order * a pirate will offer a split where he gets 0 gold if he knows that any other split will not get the votes and he will die * a pirate will not vote for a split if he knows he can get the same gold from the next pirate to offer how do they split the money and how many pirates die? This problem can be solved by working backwards. Let's assume all but pirates 9 and 10 have been thrown overboard. Pirate 9 proposes all 100 gold coins for himself and 0 for Pirate 10. Since when he votes, he is at least 50% of the vote, he gets all the money. If there are 3 pirates left (8, 9, and 10) 8 knows that 9 will offer 10 in the next round; therefore, 8 has to offer Pirate 10 1 coin in this round to make Pirate 10 vote with him, and get his allocation thorugh. Therefore when only three are left the allocation is Pirate 8: 99 Pirate 9: 0 Pirate 10: 1 If four pirates remain (7, 8, 9, and 10), 7 can offer 1 to pirate 9 to avoid being thrown overboard. He cannot offer the same deal to pirate 10 as pirate 10 would just as well get the gold from pirate 8, so would eagerly kill off pirate 7. Ultimtely this cycle of common knowledge occurs until: Pirate 1: 96 Pirate 2: 0 Pirate 3: 1 Pirate 4: 0 Pirate 5: 1 Pirate 6: 0 Pirate 7: 1 Pirate 8: 0 Pirate 9: 1 Pirate 10: 0 Problem 20+ Show Spoiler + + Show Spoiler + In a far away land, it was known that if you drank poison, the only way to save yourself is to drink a stronger poison, which neutralizes the weaker poison. The king that ruled the land wanted to make sure that he possessed the strongest poison in the kingdom, in order to ensure his survival, in any situation. So the king called the kingdom's pharmacist and the kingdom's treasurer, he gave each a week to make the strongest poison. Then, each would drink the other one's poison, then his own, and the one that will survive, will be the one that had the stronger poison. The pharmacist went straight to work, but the treasurer knew he had no chance, for the pharmacist was much more experienced in this field, so instead, he made up a plan to survive and make sure the pharmacist dies. On the last day the pharmacist suddenly realized that the treasurer would know he had no chance, so he must have a plan. After a little thought, the pharmacist realized what the treasurer's plan must be, and he concocted a counter plan, to make sure he survives and the treasurer dies. When the time came, the king summoned both of them. They drank the poisons as planned, and the treasurer died, the pharmacist survived, and the king didn't get what he wanted. What exactly happened there? The treasurer's plan was to drink a weak poison prior to the meeting with the king, and then he would drink the pharmacist's strong poison, which would neutralize the weak poison. As his own poison he would bring water, which will have no effect on him, but the pharmacist who would drink the water, and then his poison would surely die. When the pharmacist figured out this plan, he decided to bring water as well. So the treasurer who drank poison earlier, drank the pharmacist's water, then his own water, and died of the poison he drank before. The pharmacist would drink only water, so nothing will happen to him. And because both of them brought the king water, he didn't get a strong poison like he wanted. Problem 21+ Show Spoiler + + Show Spoiler + The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another. "In the prison there is a switch room which contains two light switches labeled A and B, each of which can be in either the 'on' or the 'off' position. The switches are not connected to anything. "After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell." "No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back." "But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time any one of you may declare to me, 'We have all visited the switch room.' "If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators." *note - the only difference from Scenario B, the original position of the 2 switches are known. Assuming that: A) There is no restriction on the amount of time the prisoners could take before sending the notice to the warden that everyone has been to the switch room at least once. B) There is no restriction on the number of time each prisoner can visit the switch room C) The warden will not attempt any foul moves, such as intentionally not bringing a certain prisoner to the switch room forever. The team nominates a leader. The leader is the only person who will announce that everyone has visited the switch room. All the prisoners (except for the leader) will flip the first switch up at their first opportunity, and again on the second opportunity. If the first switch is already up, or they have already flipped the first switch up two times, they will then flip the second switch. Only the leader may flip the first switch down, if the first switch is already down, then the leader will flip the second switch. The leader remembers how many times he has flipped the first switch down. Once the leader has flipped the first switch down 44 times, he announces that all have visited the room. It does not matter how many times a prisoner has visited the room, in which order the prisoners were sent or even if the first switch was initially up. Once the leader has flipped the switch down 44 times then the leader knows everyone has visited the room. If the switch was initially down, then all 22 prisoners will flip the switch up twice. If the switch was initially up, then there will be one prisoner who only flips the switch up once and the rest will flip it up twice. Problem 22+ Show Spoiler + + Show Spoiler + A young zergling hero from Zerus wants to explore the land his race has conquered. To do this, he wants to visit every zerg planet exactly once using nydus canals and return to his home planet. Every one of these planets is connected to exactly three other planets by nydus canals. He has already planned a route but does not like it for some reason. Is there another route he can take? If so prove its existence. *Note the new route cannot just be the reverse of the original route. My solution to this problem was fundamentally wrong. Luckily, someone much smarter than me was able to figure it out. As such, we should consider him a gentleman and a scholar.  On April 11 2011 12:15 LastPrime wrote: I don't think anyone is going to get #22 so I'll post the solution here. It is quite long and "mathy" so be warned. + Show Spoiler + Let's rephrase the problem. Given a 3-regular graph that has a Hamiltonian circuit, we want to show it has to have at least one more. First some definitions: Let a T-coloring of the graph be defined as a set of three disjoint classes of edges (which we will call T-classes) such that every edge in the graph belongs to one of the three classes and also such that every vertex is connected to one edge from each of the three classes. A T-coloring shall be unordered. Let a S-subset be the union of simple cycles (A simple cycle is a cycle with no repeated vertices) such that each cycle contains an even number of edges and such that every vertex in the graph belongs to one of the cycles. Let n(S) be the number of cycles in S. When n(S)=1, we get a Hamiltonian cycle. For each edge in N, let its coefficient in X(S) be 1 if that edge belongs in S and 0 otherwise. X(S) shall be calculated mod 2. Now onto the proof. We will prove that the sum of X(H) for all Hamiltonian circuits in N = 0 (mod 2). If there was only one Hamiltonian circuit, then that value will obviously not be 0. For every T-coloring, we can associate 3 different S-subsets to it. This is what I mean by associate: take two T-classes and let their union form a S-subset. The third T-class is comprises of the edges that do not belong in that S-subset. It is easy to see that X(S_1)+X(S_2)+X(S_3) for the three subsets associated with the particular T-coloring = 0 (mod 2), as each edge occurs in two of the subsets. Call this result (1). For every S-subset of N, there are 2^(n(S)-1) different T-colorings that associate with it. That is because in each cycle of the S-subset, the two T-classes that form it will alternate, and so each cycle can be colored in two ways. Note it is 2^(n(S)-1) not 2^(n(S)) because the T-coloring is unordered. Now, the sum of 2^(n(S)-1) * X(S) over every S of N is equivalent to summing (1) over all T-colorings which equals 0 (mod 2). 2^(n(S)-1) * X(S) is naturally 0 (mod 2) for all S for which n(S) >1. Thus it follows that sum{2^(n(S)-1) * X(S)} = 0 for when n(S) = 1, i.e. sum{X(H)} = 0. Q.E.D. This is a classic result in graph theory. Feel free to ask for any clarifications. Problem 23+ Show Spoiler + + Show Spoiler + For the people that found this one here is the harder version, suppose u have 12 coins now, one of them is still conterfeit but u don't know if it's heavier or if it weight less than the others. U have 3 weighings on an accurate balance scale, find the counterfeit coint? Arbitrarily label the coins A-L First weighing: Left A,B,C,D Right E,F,G,H If they balance, the counterfeit is in I,J,K,L. If the left is heavier, the counterfeit coin is one of A,B,C,D and it is heavier or the counterfeit coin is one of E,F,G,H and it is lighter If the right is heavier, the counterfeit coin is one of A,B,C,D and it is lighter or the counterfeit coint is one of E,F,G,H and it is heavier Second weighing: Case 1: Left I,J,K Right A,B,C (if known good) If they balance, coin L is counterfeit. If the left is heavier, counterfeit coin is one of I,J,K and it is heavier If the right is heavier, counterfeit coin is one of I,J,K and it is lighter Case 2: Left A,B,C,E Right D,I,J,K If they balance, counterfeit coin is one of F,G,H and it is lighter If the left is heavier, counterfeit coin is one of A,B,C and it is heavier If the right is heavier, counterfeit coin is D and it is heavier or counterfeit coin is E and it is lighter Third weighing: If counterfeit coin is known, but not whether it is heavy or light, compare the coin with any of the others. If counterfeit coin is X and heavy or Y and light, compare X with a good coin. If X is heavier then X is the counterfeit, else it is Y. If counterfeit coin is heavy and one of 3 coins (X,Y,Z) Compare X with Y. If X is heavier, then X is the coin. If Y is heavier, then Y is the coin. If they are equal, then Z is the coin. Problem 24+ Show Spoiler + + Show Spoiler + 4 people cross the bridge, Number one crosses in 1 min, Number two crosses in 2 min, Number 3 croses in 5 mins, Number 4 crosses in 10 mins. Now it's really dark and their scared of the dark, they have only one flashlight so they decide to go 2 by 2 to cross the bridge then one persons comes back and gives the flashlight to the others. What order must they go to cross the bridge in 17 minutes. No. 1 and No. 2 go across: 2 minutes No. 2 returns with the flashlight: 2 minutes No. 3 and No. 4 go across: 10 minutes No. 1 returns with the flashlight: 1 minute No. 1 and No. 2 go across: 2 minutes 2 + 2 + 10 + 1 + 2 = 17 minutes Problem 25+ Show Spoiler + + Show Spoiler + 3 guys are in a hotel, they rent a room 30$ so they each pay 10 $. In the middle of the night the manager thinks 30$ is too expensive so he gives his son 5$ and tells him to go give it to the three men. The son puts 2 $ in his pocket and gives 3$ back to the three guys. So resuming this it's like if the guys paid 9X3$=27$ and their is a 2$ in the boy pocket so thats 29 in total, where did that 1$ pass from the beggining. The equation 9x$3 = $27 is misleading. Here is an accounting of the $30 over time. Starting Time Man 1: $10 Man 2: $10 Man 3: $10 Manager: $0 Son: $0 $10+$10+$10+$0+$0 = $30 After Giving the Manager the Money Man 1: $0 Man 2: $0 Man 3: $0 Manager: $30 Son: $0 $0+$0+$0+$30+$0 = $30 After Giving the Son the Money Man 1: $0 Man 2: $0 Man 3: $0 Manager: $25 Son: $5 $0+$0+$0+$25+$5 = $30 After the Son takes $2 and Gives the Men Each $1 Man 1: $1 Man 2: $1 Man 3: $1 Manager: $25 Son: $2 $1+$1+$1+$25+$2 = $30 There is no missing dollar. Problem 26+ Show Spoiler + + Show Spoiler + suppose you have a chess board with 2 opposite corners cut. there would be 62 squares in this cut out board. you have a set of domino pieces, each piece can cover exactly 2 adjacent squares of the chess board. Is it possible to cover (tile) the cut out chess board with exactly 31 pieces of dominos? if yes, how? if not, why not? Since two diagonally opposite squares are the same color, it leaves 30 squares of a color and 32 of another. Since a domino only covers two squares of opposite colors, only 15 dominos at most can be fitted on the board. Problem 27+ Show Spoiler + + Show Spoiler + In the Protoss Lore, every time an Archon is merged, their soul is also merged [BS]. Everytime that archon dies, that souls reincarnates into a new templar following these rules: -A High Templar + High Templar archon reincarnates into a High Templar -A Dark Templar + Dark Templar reincarnates also into a High Templar -A High Templar + Dark Templar reincarnates into a Dark Templar In the begining of Templar Time there was a known amount of each type of templar and no archons. They will merge until there is only one left. How do you determine which type of Templar will be the last remaining. If two high templar merge, we are -1 high templar. If two dark templar merge, we are +1 high templar -2 dark templar. If one of each templar merge, we are -1 high templar. If we have an even number of dark templar to begin with, we will have an even number of dark templar at the end. So our last templar will be a high templar. If we have an odd number of dark templar to begin with, we will end with one dark templar at the end. Problem 28+ Show Spoiler + + Show Spoiler + Here's what you have: -Two 8-liter jugs, filled with water -One 3-liter jug, empty -Four infinite size, empty pools Here's what your objective is: Fill each of the four pools with exactly 4 liters of water. Let's label the jugs A, B, and C such that the first 8-liter jug is Jug A, the second 8-liter jug is Jug B, and the 3-liter jug is Jug C. Let's also label the pools pool 1, 2, 3, and 4. I was able to get a solution in 24 steps. A->C C->1 A->C A->2 C->A B->C C->A B->C C->A C->3 B->C A->C C->B A->C C->B A->C A->4 C->B C->1 B->C C->3 B->C C->4 B->2 And now all the jugs are empty and each pool has 4 liters of water. Problem 29+ Show Spoiler + + Show Spoiler + Typical "stars" are drawn in connected, but not repeated, line segments. For example, a 5-point star is drawn as such - line segments AC, CE, EB, BD, DA. The segments must always alternate a constant number of points (in the above case, skipping 1 point in between). Given the information that there is only 1 way to draw a 5-point star, and that there is NO way to draw a 6-point star (in continuous lines, that is), and there are 2 ways to draw a 7-point star, how many different ways are there to draw a 1000-point star? The vertices of an n-pointed star are the vertices of a regular n-gon, numbered 0 through n-1 in clockwise order. The star is determined by choosing a vertex m and drawing the line segments from 0 to m, from m to 2m, from 2m to 3m, and (n-1)m to 0, where all numbers are reduced modulo m. In order for the figure to satisfy our conditions, m must be relatively prime to n and not equal to 1 or m-1. There are 400 positive numbers below 1000 that are relatively prime to 1000. Since the same star results from choosing the first edge to go from 0 to k as when it goes from 0 to n-k, there are (400-2)/2 = 199. So 199 different ways. Problem 30+ Show Spoiler + + Show Spoiler + In Madadia, a rather strange and misguided assassin, from his hidden position, uses a high-powered rifle to shoot someone in the foot from 50 feet away. The bullet travels at 1300 feet per second. Both the person being shot at and the assassin are at sea level. What will be the first evidence to the person of the attack? (As in how will he know he as been shot.) Since the bullet travels faster than the speed of sound (1116.44 fps at sea level) he will feel the pain of a foot thoroughly ruined before he hears the shot. So the order should be that he will see the flash, feel/realize his foot is pwnt, and then hear the shot. Problem 31+ Show Spoiler + + Show Spoiler + Put 1001 unit squares on a coordinate plane. The squares can overlap in any fashion. Let S be the region of the plane that is covered by an odd number of squares. Prove that the area of S is greater than or equal to 1. Note: the sides of the squares are parallel to X and Y axes. If all the squares are stacked up, then the area is one. If there is one even stack and one odd stack, then the area is one. If there are any more than one odd stack, then the area is greater than one. It is impossible to have no odd stacks. But a stack will have a minimum area of one. If it is an overlap, you can maximize the overlap with an odd number of squares to be all but 1 square unit, but you cannot maximize it beyond that. Problem 32+ Show Spoiler + + Show Spoiler + To start off, a truel is exactly like a duel just with three people. One morning Mr. Black, Mr. Gray, and Mr. White decide to resolve a dispute by trueling with pistols until only one of them survives. Mr. Black is the worst shot, hitting once every three times (1/3). Mr. Gray is the second best shot, hitting his target twice out of every three times (2/3). Lastly, Mr. White always hits his target (1/1). To make it fair, Mr. Black will shot first, following by Mr. Gray (if he is still alive) and then Mr. White (provided that he is still alive). The Question is: Where should Mr. Black aim his first shot? If Mr. Black shoots the ground, it is Mr. Gray's turn. Mr. Gray would rather shoot at Mr. White than Mr. Black, because he is better. If Mr. Gray kills Mr. White, it is just Mr. Black and Mr. Gray left, giving Mr. Black a fair chance of winning. If Mr. Gray does not kill Mr. White, it is Mr. White's turn. He would rather shoot at Mr. Gray and will definitely kill him. Even though it is now Mr. Black against Mr. White, Mr. Black has a better chance of winning than before. Problem 33+ Show Spoiler + + Show Spoiler + There are 3 coins on the table Gold, Silver and copper. The man at the table will let you make one statement, if it is true he will give you a coin. If it is false you won't let you have a coin. What will you say to him to always ensure that you have the gold coin? "You will give me neither the copper or the silver coin." If it's true, you get the gold coin. If it's false, it breaks the conditions that you get no coin when lying. Problem 34+ Show Spoiler + + Show Spoiler + On April 11 2011 12:05 x-Catalyst wrote: 4 captives are buried in the ground. There are 3 people on one side of a solid brick wall, and one person on the other. They are all facing the brick wall. The people on the left are in a line, so they can see the people in front of them. Person 1 can see person 2 and 3. Person 2 can see person 3. But person 3 and 4 can only see the brick wall in front of them. The people who are holding the captives place a star on each of the hats on their heads. 2 red, and 2 blue. They tell all 4 captives this, but do not tell them what order the stars are in. They say that if one of the captives can guess his color star, they will let him free. But if he's wrong, they all die. The captives can not talk to each other. They can only see what's ahead of them, including the other peoples stars, but not their own. The brick wall is completely solid and tall/wide. There is nothing reflective, and they cannot turn their heads to look at the people behind them. Which one of these people know what star they have, and how do they know? ![[image loading]](http://imgur.com/3EJ14.jpg) The prisoners know that there are only two hats of each color. If 1 observes that 2 and 3 have hats of the same color, 1 would deduce his hat is the other color. If 2 and 3 have hats of different colors, then 1 can't say anything. 2, knowing what 1 would do, can determine that if 1 says nothing about the hats of 2 and 3, that 2's and 3's hats must be different. Being able to see 3's hat, he can determine his own hat color. So if 2 & 3 have the same color hats, 1 will know. If 2 & 3 have different color hats, 2 will know. Problem 35+ Show Spoiler + + Show Spoiler + You have a jar filled with 100 black marbles and a jar filled with 100 white marbles. You can rearrange the marbles any way you like as long as all of the marbles are in jars. After sorting, you randomly select one jar and then randomly select one marble from the jar. If the marble is white you win. What are your maximum odds for winning? Place 1 white marble in one of the jar, such that it is the only marble in the jar. Place the other 99 white marbles and 100 black marbles into the other jar. This way, you have a near 75% chance to choose a white marble. Problem 36+ Show Spoiler + + Show Spoiler + You are blind folded and presented with 100 coins. You are told that 50 are heads and 50 are tails. How can you split them into two piles so that the two piles contain an equal amount of heads? You can not distinguish the orientation of the coins by touch. Make two piles of 50 coins and flip over one of the piles. (Sounds crazy, but works!) Problem 37+ Show Spoiler + + Show Spoiler + You have two cups with 10 teaspoons of tea in one and 10 teaspoons of coffee in the other. You take one teaspoon from the tea cup and put it in the coffee cup, then take a teaspoon of the coffee-tea mix and put it in the tea cup. Is there more coffee in the tea cup, or tea in the coffee cup? They're the same. Step 1 Cup 1: 10 Tea, 0 Coffee Cup 2: 0 Tea, 10 Coffee Step 2 Cup 1: 9 Tea, 0 Coffee Cup 2: 1 Tea, 10 Coffee Step 3 Cup 1: 100/11 Tea, 10/11 Coffee Cup 2: 10/11 Tea, 100/11 Coffee Problem 38+ Show Spoiler + + Show Spoiler + Suppose you are being screened for a disease that affects 1 in 10,000 people statistically. You are to be given a test for the disease that is 99% sensitive and 99% specific, that is, that the test will correctly identify someone who has the disease as testing positive 99% of the time, and will correctly identify someone who does not have the disease as testing negative 99% of the time. How much more likely are you to have the disease given a positive test result than to not have the disease given a positive test result. Let P(S) = the probability that you are sick (This is 0.0001 given that the incidence of disease is 1 in 10,000 people) P(N) = the probability that you are not sick (This is 1-P(N) or 0.9999) P(+|S) = the probability that the test is positive, given that you are sick (This is 0.99 since the test is 99% accurate) P(+|N) = the probability that the test is positive, given that you are not sick (This is 0.01 since the test will produce a false positive for 1% of users) P(+) = the probability of a positive test event, regardless of other information. (0.010098, which is found by adding the probability that a true positive result will appear (0.99*0.0001) plus the probability that a false positive will appear (0.01*0.9999).) P(N|+) = the probability that a non sick person tested positive P(N|+) = P(+|N)P(N)/P(+) = 0.01*0.9999/0.010098 ~ 0.9901960784313725 P(N|+) ~ 99% P(S|+) = the probability that a sick person tested positive P(S|+) = P(+|S)P(S)/P(+) = 0.99*0.0001/0.010098 ~ 0.0098039215686275 P(S|+) ~ 1% P(N|+)/P(S|+) = 101. You are 101 times more likely to NOT be sick given a positive test result than to BE sick given a positive test result. (Even though the test is 99% sensitive and 99% specific!) Problem 39+ Show Spoiler + + Show Spoiler + You have to walk into 1 of 2 doors, where one will lead to certain instantenous death, and the other will lead to a life full of starcraft 2 and happy things. Each door is guarded by an all knowing all powerfull zergling(A crackling, if you will). One of the zerglings will always lie and the other will always tell the truth. You can ask One of them, 1 question. What do you ask to figure out what door to take? (You obviously do not know what zergling lies, and what door the zergling guards holds no relation to him lying or telling the truth.) Ask one of the omnipotent and omniscient zerglings "If I asked the other zergling, which door would he indicate will lead to a life full of Starcraft 2 and happy things?" Then take the opposite door. And now to pretend that no new logic problems will pop up so I don't waste my entire life here. Your answer to number 15 + Show Spoiler + Problem 15+ Show Spoiler + + Show Spoiler + Let A be a collection of 100 distinct integers. Can you select 15 integers from A so that the difference of any two numbers from this selected subset is divisible by 7? The answer is yes if the collection of 100 distinct integers is consecutive. As you could start with the largest number in the set, and set up the recursion A(n+1) = n - 7, such that you fill a set of 15 numbers that have a difference of seven between terms in the set. If the collection of 100 distinct integers is for example multiples of 3s (3,6,9,12,15,18,21,etc.) then no pair of numbers subtracted will be divisible by 7. is incorrect. Here's why:+ Show Spoiler + Look at your counter example of a set. The least residue of each of those numbers mod 7 is 3, 6, 2, 5, 1, 4, and 0. These are certainly great numbers to start off with if you're trying to come up with a counter example, but unfortunately, you've just exhausted all of the least residues. The next number you pick MUST be the same least residue as one that you've already picked, and the difference between these two must be a multiple of 7 (as their difference is 0 mod 7). In your example set, the next number happens to be 24. 24 - 3 = 21, which happens to be a multiple of 7. So basically, our goal is to distribute 100 number across the 7 least residues mod 7, without any single least residue having 15 or more elements. You will find this to be impossible. We will distribute it so that each subset has 14, but that's only 98 integers, and we still have two left. Therefore, it is ALWAYS possible to select a subset of 15 integers. You don't even need 100; you can guarantee it with 99, and they don't even have to be distinct! | ||
]343[
United States10328 Posts
Let A be a finite set of (distinct) integers. Let A+A be the set of all sums a+b where a, b are in A, and similarly define A-A to be the set of all differences a-b where a, b are in A. a and b are not necessarily distinct. Prove or disprove: |A+A| <= |A-A|. (Example: A = {1, 2, 3}. A+A = {2, 3, 4, 5, 6}. A-A = {-2, -1, 0, 1, 2}.) | ||
|
Starfox
Austria699 Posts
On April 10 2011 00:05 stepover12 wrote: 40. (a round robin starcraft tournament) + Show Spoiler + Suppose that 20 starcraft pros played in a tournament where each player competed against every other player exactly once. The result of each game is only win/lose, no draw. Is it always possible (regardless of results) to name the players 1,2,3,...,20 so that player 1 defeated player 2, player 2 defeated player 3,... player 19 defeated player 20? Give a proof or a counterexample. I'll add more when I can. + Show Spoiler + Graph theory, find a Hamilton path in a directed complete graph Just look at it like you have a graph, with 20 vertices. Everyone is connection to everyone, and the connection has a direction. Basically each edges points FROM one vertex TO another one. Can be shown that for ever such complete graph there is at least one hamilton path (and the proof is also the instruction how to get it) Anyone can see that if there were only 2 players that the only edge you have actually is the path you are searching for. Either P1,P2 or P2,P1 Now the induction itself: Assume with have such a graph with n players, and we know the hamiltion path of it: P1,P2,....,Pn Now we go to n+1: We introduce a new player 0, which has either beaten or was being beaten by each of the players 1 to n Now find the player with the lowest number who was beaten by player 0, lets call this player m if he exists. If player m doesn't exist, it means EVERYONE has beaten player 0, which means you can safely put him at the end, as also player n has beaten him: P1,P2,...,Pn,P0 If player m exsists, you can insert player 0 right in front of him P1,...,P(m-1),P0,Pm,...,Pn As player m is the lowest number he has beaten, this means that player (m-1) must have beaton player 0 q.e.d. | ||
| ||
|
|
LiuLi Cup
MaxPax vs TriGGeR
ByuN vs herO
Cure vs Rogue
Classic vs HeRoMaRinE
Cosmonarchy
OyAji vs Sziky
Sziky vs WolFix
WolFix vs OyAji
Big Brain Bouts
Iba vs GgMaChine
TriGGeR vs Bunny
Reynor vs Classic
Serral vs Clem
BSL Team Wars
Team Hawk vs Team Dewalt
BSL Team Wars
Team Hawk vs Team Bonyth
Code For Giants Cup
SC Evo League
TaeJa vs Cure
Rogue vs threepoint
ByuN vs Creator
MaNa vs Classic
Maestros of the Game
ShoWTimE vs Cham
GuMiho vs Ryung
Zoun vs Spirit
Rogue vs MaNa
[BSL 2025] Weekly
SC Evo League
[ Show More ] |
|
|
EPT
