EPT |A+A| <= |A-A|.
The "| |" notation is for number of distinct elements?
Brainteasers/Math problems - Page 17
| Forum Index > General Forum |
|
gyth
657 Posts
The "| |" notation is for number of distinct elements? | ||
|
jeanphil
France74 Posts
Four men have to cross a bridge at night. They are all on the same side. The only have one torch and only up to two men can cross the bridge at the same time. One has to have the torch to cross the bridge. Each man needs a certain time to cross the bridge. man 1: 1 min man 2: 2 min man 3: 5 min man 4: 10 min If two men cross the bridge together they take the time of the slower one. how can they cross the bridge in 17 min?? | ||
|
Gnaix
United States438 Posts
| ||
|
Starfox
Austria699 Posts
On April 11 2011 20:41 ]343[ wrote: Hmm, don't think this has been posted yet? 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}.) That's some number theory stuff, and not somethin you proof in a few lines, you sure it isn't just someones university stuff?  | ||
|
Tankcast
United States25 Posts
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. Solution: + Show Spoiler + You separate the 100 coins into two piles of 50 then flip all of coins in one of the two piles. Now both piles will have the same number of heads. | ||
|
Earll
Norway847 Posts
On April 12 2011 05:10 jeanphil wrote: here is one. Four men have to cross a bridge at night. They are all on the same side. The only have one torch and only up to two men can cross the bridge at the same time. One has to have the torch to cross the bridge. Each man needs a certain time to cross the bridge. man 1: 1 min man 2: 2 min man 3: 5 min man 4: 10 min If two men cross the bridge together they take the time of the slower one. + Show Spoiler + man 1 and 2 go over : 2 mins total Man 1 goes back: 3 mins total Man 5 and 10 goes over: 13 mins total Man 2 goes back: 15 mins total Man 1 and 2 goes over: 17 mins. | ||
|
stepover12
United States175 Posts
On April 12 2011 00:18 gyth wrote: The "| |" notation is for number of distinct elements? Yes, I suppose so. And "<=" probably means "less than or equal to". On April 11 2011 22:45 Starfox wrote: (solution to 40.) + 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. Yes! + Show Spoiler + Induction | ||
|
stepover12
United States175 Posts
On April 12 2011 05:10 jeanphil wrote: here is one. Four men have to cross a bridge at night. They are all on the same side. The only have one torch and only up to two men can cross the bridge at the same time. One has to have the torch to cross the bridge. Each man needs a certain time to cross the bridge. man 1: 1 min man 2: 2 min man 3: 5 min man 4: 10 min If two men cross the bridge together they take the time of the slower one. how can they cross the bridge in 17 min?? This one is the same as number 24 on the original post  | ||
]343[
United States10328 Posts
On April 12 2011 08:08 stepover12 wrote: Yes, I suppose so. And "<=" probably means "less than or equal to". Correct. This was on a math competition I went to around... 3? years ago. No one solved it during the contest  On April 12 2011 05:43 Starfox wrote: That's some number theory stuff, and not somethin you proof in a few lines, you sure it isn't just someones university stuff? I'd hesitate to call it number theory actually... seems more combinatorial than anything. | ||
|
Kazius
Israel1456 Posts
2 DTs can merge with each-other can create an HT, lowering the DT amount by 2. One can merge with an HT, creating a DT, not changing the amount of DTs at all. Therefor, any combination of 2 DTs will not change the amount of DTs by an odd number. Hence, if there are an odd number of DTs, one DT will remain. If there is an even number of DTs, one HT will remain. 29. + Show Spoiler + Each star can be created by movements under half the amount of it's points (otherwise, it is the mirrored to be the exact same way as the other way around). You cannot create a star with any number that is a multiple of one of it's prime factors. You cannot create a star with movements of 1, as that will not be a star. Therefor, 1000 cannot be made in jumps of even numbers (will skip all odd points), and numbers divisible by 5 (will skip all points not divisible by 5). So, what we are looking for is all numbers between 3 and 499 not divisible by 2 or 5. This can be discerned via the single digits of the number. In each 10, the numbers ending with 1, 3, 7 or 9 are not divisible by those numbers. there are 50 such 10s, therefor, there are 200 such numbers, needing to subtract 1 as it is not a star. Hence, there are 199 ways. 31. + Show Spoiler + Just think of it this way: Odd overlapping causes the color to be black. Otherwise, it is empty. Adding 2 more can not subtract from this, as to subtract from it, they do an inverse on an area of between 0 (they completely overlap) and 2 (they don't overlap at all) - but no matter where there is a black area they cover, will their edges will always do an inverse to exactly the amount the overlapped with, therefor, they cannot subtract one no matter what. You start out with one square (an odd overlap with itself), and add pairs, until you reach 1001. 32. + Show Spoiler + He should shoot not aiming at either one of the others. That way, he has a 2/3 chance of going against someone with a 2/3 chance to kill him, and otherwise, a 1/3 chance. If he kills someone else, he will most likely die the next shot. 33. + Show Spoiler + "if you will give me the gold coin, this statement is true" - If the listener gives the gold coin, than it is true. If he does anything else, then he makes that statement true (in the "if it's snowing dogs, I can fly" kind of way), and therefor, he gives the gold coin. Edit: accidentally deleted: 34. + Show Spoiler + If the one behind the other 2 sees 2 stars of the same color, her knows his color and leaves, and then the one in front of him knows that he is of the same color as the on in front of him and leaves as well. Otherwise, the guy in front of him knows he doesn't leave, and therefor knows he has a different color than the guy in front of him and leaves. Therefor, only the second out of the 3 can leave each time. The other two don't have enough information, so sadly they stay in prison. 35. + Show Spoiler + Let A be the event of picking the first jar, and B be the event in which he picked a white marble. The chances of B are the amount of white marbles out of the 100. Therefor, the chances of B happening are the chances of B if A happened, plus the chances of B if A didn't happen. Assume the first jar has M marbles. There is a 50% chance to select each jar (random choice), therefor the chance of B happening if A are M/100. Similarly, the chance of B if not A are (100-M)/100. Therefor, the chances are (1/2)*(M/100) + (1/2)*(M/100) = 1/2. Therefor, there will always be a 50% chance of picking a white marble. 36. + Show Spoiler + Easy enough. Split them 50-50, and flip over one of the halfs. One has M heads, the other has 50-M heads before flipping over, after flipping over it will also have M heads. 37. + Show Spoiler + First stage: cup A: 9 teaspoons of tea cup B: 10 teaspoons of coffee, 1 teaspoon of tea Second stage: Cup A: 9 tea + 10/11 coffee + 1/11 tea Cup B: 9 + 1/11 coffee + 10/11 tea Therefor, there is an equal amount. 38. + Show Spoiler + The number of diseased people is .001%, therefor, the number of healthy people is 99.99%. There is a 1% chance of a healthy person being misdiagnosed, therefor, 0.9999% of people are false positives. out of the .001%, 99% are properly diagnosed, therefor, .0099 of people are true positives. Therefor, you are 101 times more likely to get a false positive, or you have a 1/101 chance to actually have the disease given a positive result. 39. + Show Spoiler + Does the one telling the truth guard the door that will kill me? If it is the liar, and he is protecting the bad door, he will say "yes". If it is the truth teller, and he is protecting the bad door, he will say "yes". In both cases, I go to the other door. If it is the liar and he's protecting the good door, he will say "no", if it is the truth teller protecting the good door, he will say "no", and I enter the door behind the zergling I asked the question. | ||
|
gyth
657 Posts
{0,1,3} 3+3=6 3+1=4 3+0=3 1+3=4* 1+1=2 1+0=1 0+3=3* 0+1=1* 0+0=0 Three unavoidable pairs because a+b=b+a. Removes 3 from the possible 8. 3-3=0 3-1=2 3-0=3 1-3=-2 1-1=0* 1-0=1 0-3=-3 0-1=-1 0-0=0* An unavoidable triplet of 0s because a-a=0. But this only removes 2 from the possible 8. This isn't a proof, but it might give someone an idea for where to go. | ||
|
MusicalPulse
United States162 Posts
Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which. | ||
|
KameZerg
Sweden1769 Posts
+ Show Spoiler + | ||
|
Ferox77
United States59 Posts
+ Show Spoiler + Jar-A 1 white marble. Jar-B 99 white marbles 100 black marbles. 74.87% chance to draw a white marble. | ||
|
petitdragon
France22 Posts
+ Show Spoiler + For any 2 strictly positives and distincts integers a and b , a+b = b+a , while a-b != b-a So from there, I think we can conclude that |A+A| <= |A-A| | ||
|
blankspace
United States292 Posts
What competition is it from 343? | ||
|
]343[
United States10328 Posts
On April 13 2011 23:19 petitdragon wrote: |A+A| <= |A-A| + Show Spoiler + For any 2 strictly positives and distincts integers a and b , a+b = b+a , while a-b != b-a So from there, I think we can conclude that |A+A| <= |A-A| ah, but what if your b-a, a-b are already in the set, but a+b is not? also adding an integer a to the set adds to A+A 2a as well as a+b, for all b in A, while it adds only a-b, b-a (since 0 is already in A-A hopefully) to A-A. It was from the Princeton Math Competition a few years back (probably 07-08?) | ||
|
blankspace
United States292 Posts
Let it be true for an n-1 element set (trivial for n=2). Now given an n element set, order the elements so a_1 is the smallest and a_n is the greatest. Let A' = A\{a_n}. We already know from induction that |A'+A'| <= |A'-A'|. When we introduce a_n, the set of differences increases by this amount: 2(n - |B|), where B is set of pairs (n,i) such that a_n-a_i = a_j-a_k. Notice that the set of sums increases by: n+1-|G|, where G is the set of pairs (n,i) such that a_n+a_i = a_j+a_k (j=k possible). Now given (n,i) in G, consider a_n+a_i = a_j+a_k with a_j maximal among the possible sums. Then given (n,i) in G we can map this to the set { (n,j),(n,k) } in B. This mapping must be injective, for if we had (n,t) mapping to the set { (n,j),(n,k) } as well, then a_n + a_t = a_j+a_k would hold true, implying that i=t. Hence we've shown that |G| => |B|. Finally note that |G| <= n-1 because the way we ordered, (n,n-1) cannot be in G. Now 2(n-|B|) > = 2(n-|G|) >= n+1 - G where the last equality is equivalent to n-1 >= G. | ||
|
sidr
United States55 Posts
For those who know a bit more math, I have a variation on #10. Suppose countably many prisoners (meaning we can assign each prisoner a natural number, ie there is a prisoner 1, prisoner 2, etc for all positive whole numbers) are given the following scenario: on the following day, an evil warden will assemble them in one (very large) room and give each of them a hat with a (not necessarily unique) natural number on it. Each prisoner will be able to see all hats except their own. Without any communication with other prisoners after receiving his or her hat, each prisoner will communicate with the warden what he or she thinks his or her number is. This communication occurs simultaneously; that is to say prisoner x has know knowledge of what prisoner y communicated to the warden (unless of course x=y...). The prisoners are all allowed free if and only if finitely many of them are wrong. Assume the prisoners know this will happen the following day, and are given a night to prepare a strategy. Is there a strategy which guarantees the prisoners all go free? Give the strategy or prove no such strategy exists. | ||
|
JeeJee
Canada5652 Posts
On April 13 2011 14:18 MusicalPulse wrote: Friend asked me this one, kinda like the other 3 person truth/lie one. Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which. edit: ah, missed the fact that you don't know which is yes and which is no. maybe u do need 3 questions after all blah tricky. so far i can only figure out which is da/ja, and who is the random god in 3 questions. Hmm.. here we go i think + Show Spoiler + ask A "if i were to ask you, are you the random god, would you say da?". then ask B same thing. 2 questions used if da=no trueGod: ja falseGod: ja randomGodDecidingToLie:da randomGodDecidingToTellTruth: da if da=yes trueGod: ja falseGod: ja randomGodDecidingToLie:da randomGodDecidingToTellTruth: da therefore, in the first 2 questions we can either hear (remember we asked A then B) JAJA -> C is random god DAJA -> A is random god JADA -> B is random god now ask one of the true/false gods (whoever they are based on case) "if i were to ask you, are you the lying god, would you say da? if da=yes trueGod: ja falseGod: da if da=no trueGod: ja falseGod: da now we knew who random god was, and now we know who is who between false/true (as truegod will say Ja while falseGod will say Da) | ||
| ||
