Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
p4wn3r wrote:
Further optimizations can be applied, you can initialize all even numbers except 2 as composite and , start at 3 and use n+=2 instead of ++n, and that can be made even better using something called a factorization wheel, but that's more complicated.
If we are talking about programmatic optimizations, then one of the major problems with the basic algorithm is that it has poor cache locality if the bit array is much larger than even the outermost cache, and the algorithm can be made significantly faster by doing things in a slightly different order. However, that topic is beyond the scope of this thread, which is about math.
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
Here's my full solution to RGamma's problem, without the two numbers specified beforehand, and without any prior assumption that a solution exists or that it is unique: In this post, "factorization" means writing n=cd with c,d in [2,99] and c≤d. "Two factorizations" means "at least two factorizations". Clearly, S must be at least 4 for this problem to make sense. Let x,y be two integers in [2,99] with x≤y, xy=P with P given to Mr. Product, x+y=S with S given to Mr. Sum. Mr. Product: "I know neither of both numbers." That means P has at least two factorizations. Mr. Sum: "I, too, know neither of both numbers; but I knew that you wouldn't know them." That means for all c,d in [2,99] with c+d=S, cd has two factorizations. S<55 since otherwise if c=S-53, d=53, then cd has only one factorization. S is odd, since all even numbers in [4,54] are the sum of two primes (just take my word for it). S-2 is composite, since otherwise if c=2, d=S-2, then cd has only one factorization. Furthermore, if S-2 is composite, then S is consistent with Mr. Sum's statement. This is because if c+d=S, with c,d in [3,50], one of c,d is even and the other is odd. Without loss of generality, c is even, so c=2e, e>1. As well, d≤49. Then cd=e(2d) and so cd has two factorizations. If c=2, d=S-2, then since S-2 is composite, cd has two factorizations. Therefore S must be one of the numbers of the set {11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53}. Call this set V. Mr. Product: "Now I know both numbers." That means there is exactly one factorization of P into cd such that c+d is in V. Let W be the set of all integers x for which there is exactly one factorization of x into cd such that c+d is in V. Mr. Sum: "Now I know both numbers as well." That means that, over the set of all pairs (c,d) with c+d=S and c≤d, there is exactly one pair (c0, d0) with c0d0 in W. Suppose S>33. If c=S-29, d=29, then cd is in W. Similarly, if c=S-31, d=31, then cd is in W. This is inconsistent with Mr. Sum's second statement. Therefore S is one of {11, 17, 23, 27, 29}. Furthermore, any number of the form q(2m), where q is an odd prime and m>1, and with q+2m in V, is in W, since c=q, d=2m is the only factorization with c+d odd. We see that 11=3+8=7+4, 23=19+4=7+16, 27=23+4=19+8, and so 11, 23, and 27 have more than one representation as c+d with c≤d such that cd is in W, so we can get rid of them. S is either 17 or 29. Note that 29=13+16. Now for 4,25 (29=4+25), we see that 100 is in W since the only factorizations with one odd and one even are 4,25 and 20,5, and 20+5=25 is not in V. Therefore S cannot be 29, so S=17. Now 17=13+4, and 13(4)=52 is in W. The other possibilities for c+d=17 are ruled out as follows: 17=2+15, 2(15)=6(5), 6+5=11 is in V. 17=3+14, 3(14)=21(2), 21+2=23 is in V. 17=5+12, 5(12)=20(3), 20+3=23 is in V. 17=6+11, 6(11)=2(33), 2+33=35 is in V. 17=7+10, 7(10)=35(2), 35+2=37 is in V. 17=8+9, 8(9)=24(3), 24+3=27 is in V. So none of the other pairs (c,d) have cd in W. This gives the two numbers for the unique answer, x=4 and y=13.
Editor
Joined: 3/10/2010
Posts: 899
Location: Sweden
I have a probability problem. Gamefaqs.com has an annual character battle. It is a series of three way polls. There is a series of polls in the form of a perfectly balanced tree. The depth of the tree is five, the leaf nodes is at level five. Users get to guess how every poll will turn out and there is a scoreboard. Users need to correctly guess at least the winner for the previous level in order to be able to correctly guess the next level. That is, the guessed winners of the previous levels become the possible guesses for the next level. Guess all previous levels wrong and you will be unable to guess correctly. Now I wonder what the chance is for blindly guessing A all of the battles and B just the final winner.
Tub
Joined: 6/25/2005
Posts: 1377
henke37 wrote:
The depth of the tree is five, the leaf nodes is at level five.
So there's 3^5 = 243 characters?
henke37 wrote:
Now I wonder what the chance is for blindly guessing A all of the battles and B just the final winner.
B is very easy to answer: Each character has a 1/243 chance of being the final winner. If you blindly pick one, your chance is 1/243. A is a bit more difficult. There are two interpretations: A1) for each battle, you blindly pick a winner from the set of characters that could participate. You may guess for Mr X to lose his first poll, but win the finals. Which is stupid, but certainly "blind". For each poll, your chances are 1/[number of characters that could participate]. The chance of winning all of them is (1/3)^81 * (1/9)^27 * (1/27)^9 * (1/81)^3 * (1/243) A2) You're a bit smarter than that. Whenever you pick a winner, you bet on him to win all his previous polls, too. Let's work backwards: (1/243) chance for the winner to be correct. If you got him correct, you've also guessed his previous four polls correctly. (1/81)^2 chance for the other two semi-finals to be correct, which includes their previous three polls. (1/27)^6 chance for the remaining tier 3 polls to be correct. At this point you'll likely want to draw the tree and cross out any paths you've already guessed. There's 9 polls in tier 3, and you already know that three of them are correct, so 6 remain. For the remaining two tiers, it'll get a bit more finicky. In fact, I'll leave that as an exercise to the reader :p Once you've understood the structure, you can try to derive a general formula that can tell you your chances of guessing a 4-per-match, 7-tier poll. If you feel like it.
m00
Editor
Joined: 3/10/2010
Posts: 899
Location: Sweden
A2 is enforced by the guessing contest.
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
A2 is just this: Guess each of the match-ups in Round 1. Knowing the 81 remaining contestants at this point (since you are smart), guess each of the match-ups in Round 2. And so on. Since each match-up is a three-way poll, and there are 121 (81+27+9+3+1) matches in the tournament, the probability of guessing them all right is (1/3)^121. Note: Tub's solution to A2 is correct as well. Also, a k-per-match, m-tier poll, the probability of guessing them all right (assuming you are smart) is (1/k)^((k^m-1)/(k-1)).
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Warp wrote:
p4wn3r wrote:
Further optimizations can be applied, you can initialize all even numbers except 2 as composite and , start at 3 and use n+=2 instead of ++n, and that can be made even better using something called a factorization wheel, but that's more complicated.
If we are talking about programmatic optimizations, then one of the major problems with the basic algorithm is that it has poor cache locality if the bit array is much larger than even the outermost cache, and the algorithm can be made significantly faster by doing things in a slightly different order. However, that topic is beyond the scope of this thread, which is about math.
Using factorization wheels is a mathematical optimization. Notice that I didn't mention anything about the computer architecture. Using a step of 2 numbers removes 50% of the composite numbers. Using larger wheels generated by more prime numbers can shave off 95% of them. Although I don't think the algorithmic complexity changes, the improvement on the constants is huge.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
p4wn3r wrote:
Warp wrote:
p4wn3r wrote:
Further optimizations can be applied, you can initialize all even numbers except 2 as composite and , start at 3 and use n+=2 instead of ++n, and that can be made even better using something called a factorization wheel, but that's more complicated.
If we are talking about programmatic optimizations, then one of the major problems with the basic algorithm is that it has poor cache locality if the bit array is much larger than even the outermost cache, and the algorithm can be made significantly faster by doing things in a slightly different order. However, that topic is beyond the scope of this thread, which is about math.
Using factorization wheels is a mathematical optimization. Notice that I didn't mention anything about the computer architecture. Using a step of 2 numbers removes 50% of the composite numbers. Using larger wheels generated by more prime numbers can shave off 95% of them. Although I don't think the algorithmic complexity changes, the improvement on the constants is huge.
I don't understand what that has to do with what I said. I was talking about CPU caches and the order in which data is being processed.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Really?
Warp wrote:
If we are talking about programmatic optimizations
p4wn3r wrote:
Using factorization wheels is a mathematical optimization.
You compared it to programming optimizations, like cache stuff, and I said it isn't, because it makes the algorithm faster while being totally agnostic to the computer implementation.
Player (80)
Joined: 8/5/2007
Posts: 865
I don't know if this is a nontrivial question. I went for a bicycle ride around my neighborhood the other day. My neighborhood is shaped roughly like a 3x1 grid (two north-south streets crossed by four east-west streets). I wanted to go on a ride that wouldn't be boring, so I wanted to see every street both forward and backward. That got me thinking: Is it possible to go on a bike ride that does this without traveling the same direction down the same road twice? To make things more interesting, I'll add one more condition: you cannot immediately double-back down a road you just traversed. (My justification for this rule is that my bicycle has momentum, so it is inconvenient to make a 180o turn.) My suspicion is that it is possible, based on my quick survey of theorems relating to Eulerian paths. We can simply construct a symmetric directed graph from the streets, after which the fifth theorem would apply if 180o turns were allowed. So does disallowing 180o turns alter the validity of the theorem?
Player (146)
Joined: 7/16/2009
Posts: 686
Allowing 180 degree turns makes the solution fairly simply: If there is an Eulerian path, you simply turn around at the end and traverse it in the other direction. But disallowing that gives graphs where it is impossible: consider a triangle. It's obviously possibly to create a Eulerian path, but unless you turn around (which isn't allowed) all you can do is traverse the graph in the same direction. My gut tells me it's possible as long as there is at least one vertex that has 4 or more edges, but proving it is another thing.
Tub
Joined: 6/25/2005
Posts: 1377
Scepheo wrote:
Allowing 180 degree turns makes the solution fairly simply: If there is an Eulerian path, you simply turn around at the end and traverse it in the other direction.
Except there is no Eulerian path in the undirected graph, where you traverse every street only once. There are four nodes (street corners) with an odd number of edges, so there cannot be a path. There is an eulerian path (even a circle) in the directed graph, where you traverse every street twice, once in each direction. Bobo has already mentioned the proof, and it's easy to construct a circle as well. I can't get below two 180° turns, though, and I suspect it's impossible without. /edit: found a circle with only one 180° turn. If you happen to start at that position, you'll have a 180°-free route. I realized that there are 8 street corners, but actually only 4 nodes that matter, since the upper two and lower two corners only give you the choice to carry on, if you want to avoid the 180. Thus it's much easier to play around and brute force a bit. If you look closely at the two vertical roads AC and BD and consider when to travel them and what to do in between, I doubt you'll find a true circle, but I still lack rigorous proof.
m00
creaothceann
He/Him
Editor
Joined: 4/7/2005
Posts: 1874
Location: Germany
sack_bot
He/Him
Player (112)
Joined: 11/27/2011
Posts: 394
Location: Massachusetts
Oh I've seen that. There is a thin sliver that adds the extra square.
Message me here for my discord. Current Project: Psycho Waluigi Project on wait list: None?
Tub
Joined: 6/25/2005
Posts: 1377
the first cut is across a 8x3 area, the second across 2x5. The angles of the cuts are: atan(3 / 8) = 20.56° atan(5 / 2) = 68.20°, which is ~21.80° after turning. So no matter how many 90° or 180° transformations you do, edges from the different cuts won't fit together. If you look closely at the image, you can see that the outlines are getting thicker in the middle, conveniently hiding the gap in the rectangle.
m00
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
There's an even more impressive version of this that uses drawings of people: There are 12 people, then the top half of the picture is cut into two, these two parts are swapped... and you end up with 13 people. There's an easy explanation of how it happens, but it's very hard for the human brain to comprehend.
Skilled player (1651)
Joined: 7/25/2007
Posts: 299
Location: UK
There's a whole selection of "vanishing puzzles" [Url=http://www.marianotomatis.it/blog/index.php?post=blog/20110715]here[/Url], all showing different amounts of an object after rearranging the pieces. They're all based on the same principle though, of the new arrangements just simply being incomplete.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
So here's a trick question for you: I play a gambling game with someone. We bet $40 each, and I lose and my opponents gets the pot. Therefore I lost $40 and my opponent won the $80 pot. We then play again, but this time we bet $20 each. This time I win. Therefore I win the $40 and my opponent loses his $20. Therefore I broke even, and my opponent is now $60 richer. How is this possible?
Noxxa
They/Them
Moderator, Expert player (4124)
Joined: 8/14/2009
Posts: 4090
Location: The Netherlands
When the opponent bets $40 and then wins the $80 pot, that leaves him with a net gain of $40. Then he bets $20 and loses it, leaving him at a net gain of $20, not $60. You first bet $40 and lose it (net -$40), then bet another $20 and win back $40, leaving you at a net gain of minus $20, not breaking even. -$20 + $20 = $0, so in the end there's no money lost or created.
http://www.youtube.com/Noxxa <dwangoAC> This is a TAS (...). Not suitable for all audiences. May cause undesirable side-effects. May contain emulator abuse. Emulator may be abusive. This product contains glitches known to the state of California to cause egg defects. <Masterjun> I'm just a guy arranging bits in a sequence which could potentially amuse other people looking at these bits <adelikat> In Oregon Trail, I sacrificed my own family to save time. In Star trek, I killed helpless comrades in escape pods to save time. Here, I kill my allies to save time. I think I need help.
Editor
Joined: 3/10/2010
Posts: 899
Location: Sweden
I have been thinking about my toast at breakfeast lately. If I pick N slices in order from the bag, toast them and randomly place them in a stack on my plate, what is the chance that all slices touch on the same sides as in the bag? That is either in the same order as in the bag, or the reverse order. And each slice can be flipped face the other way. They must either all not be flipped or must all be flipped, depending on if the slice order is reversed or not.
Player (80)
Joined: 8/5/2007
Posts: 865
henke37 wrote:
I have been thinking about my toast at breakfeast lately. If I pick N slices in order from the bag, toast them and randomly place them in a stack on my plate, what is the chance that all slices touch on the same sides as in the bag? That is either in the same order as in the bag, or the reverse order. And each slice can be flipped face the other way. They must either all not be flipped or must all be flipped, depending on if the slice order is reversed or not.
Well, there are N! different ways of arranging the pieces of toast, two of which are potentially valid. For each of those, there are 2^N different toast orientations, only one of which is valid. Therefore, my answer is simply 2 in N!*2^N or 1 in N!*2^(N-1). Bonus: Generalize this result for all eight possible different orientations of each slice. I'd do it myself, but I'm busy making peanut butter and jelly sandwiches...
Tub
Joined: 6/25/2005
Posts: 1377
The formula is correct, but only if you actually insert the toasted bread randomly into the stack. Who does that? Your actual chances would be better. You're taking K pieces of bread, put them into the toaster, take them out and put them on the plate. Repeat with K pieces of bread (however many your toaster holds), stacking them onto the plate until you're done. (This only applies when N > K, otherwise Bobo's formula holds.) This means that the first K pieces are always at the bottom, the next K pieces above etc. For each part of K pieces, there are K! * 2^k permutations, only one of which is correct. (only the reverse order is possible; the first slice you take will not end up on top of the stack). So for N = n*K slices, your chances are 1 in (K! * 2^k) ^ n Then again, you wouldn't randomly flip toast while putting it into the toaster or putting it onto the plate. You'd usually use the same hand movement each time, go about it in an orderly fashion... Depending on the way you do it, I'd say you either have sorted toast every time, or never.
m00
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
This is actually something that I have been thinking about. Let's say that you have a deck (of a collectible card game) consisting of 60 cards. If there are n cards of a certain type in the deck, and you draw an opening hand of 7 cards, what are the probabilities of having each possible amount of that type of card in your opening hand? (Ie. what's the probability of drawing no cards of that type, drawing 1 card, and so on up to either n or 7, whichever is smaller?) It would be even more interesting (and a bit more complicated) when we start with combinations. For example, let's say that in the deck of 60 cards there are 24 land cards, 4 cards of type A, and 4 cards of type B. In your opening hand of 7 cards, what are the probabilities of getting: 1) n land cards and no cards of type A, 2) n land cards and no cards of either type A or B, 3) n land cards and at least one card of type A, 4) n land cards and at least one card of type A or B, 5) n land cards and at least one card of type A and at least one card of type B? Moreover, suppose that there are 24 land cards, but of two different types. What is the probability of drawing an opening hand containing n land cards (where n is at least 2), with at least one of them being of the other land type than the others?
Skilled player (1651)
Joined: 7/25/2007
Posts: 299
Location: UK
There's 60C7 total hands, with (60-n)C7 of these containing no Land cards. The probability of choosing a hand with 0 Land cards is thus given as P(i=0)=(60-n)C7/60C7. For P(i=1), we want 6 of the (60-n) regular cards, and 1 of the n good ones. Thus (60-n)C6 * nC1 ways of constructing the hand. Totally probability P(i=1)=(60-n)C6*nC1/60C7. Generally, in a hand of 7 cards the chance of having i out of n good cards, is given by P(i)=((60-n)C(n-i))*(nCi)/(60C7) 1) Previously "n" was how many there are in deck, not the specified amount you want in your hand, so be careful of notation. 60-24-4=32 other cards. There's 24Cn ways of choosing which Land cards you want in your hand. There's 32C(7-n) ways of choosing the remaining (7-n) cards from the 32 boring ones. Thus P(i=n, A=0)=(24Cn * 32C(7-n) ) / 60C7. 2)Similarly, now there's 28 boring ones, thus P(i=n,A=0,B=0)=(24Cn)*28C(7-n)/60C7 3)So we want n Land cards in our hand, which had 24Cn combinations. Now in our remaining (7-n) cards we want A not to be equal to 0; where the probability is given by P(A>0)=P(A>=0)-P(A=0). We have (7-n) cards left, choosing from the remaining 60-24=36 cards. There are 36C(7-n) total hands, with 32C(7-n) of these not containing any A cards. Thus there are 36C(7-n)-32C(7-n) hands containing at least 1 A card. This gives: P(i=n, A>0)=(N selections * Remaining A>0 Selections)/Total Hands=(24Cn * (36C(7-n)-32C(7-n)) / 60C7. 4)As before, we have 24Cn combinations for the first n cards. We have 36C(7-n) total combinations for the remaining cards, with 28C(7-n) of these containing none of the 8 A or B cards. Thus this gives us 36C(7-n)-28C(7-n) combinations, which do contain at least 1 A or 1 B. Thus we have a very similar formula: P(i=n, A+B>0) =(24Cn * (36C(7-n)-28C(7-n)) / 60C7. 5)Needs more variables for the amount of red cards j, where 0<j<(7-n-1), giving at least 1 free space so we can have k>0 blue cards too. We have k<(7-n-j), giving at most (7-n-j-k)>=0 remaining cards to be drawn from the 28 remaining boring cards. Proper formulas inc another day.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Take any finite series of digits. Question: Does that series of digits appear (in the same consecutive order) somewhere in the decimal expansion of pi? Pure intuition could be argued for either case: 1) Since pi is an irrational number, and moreover a transcendental number, then its decimal expansion is pretty much "random", so in principle any finite series of digits ought to appear somewhere in it. 2) It's hard to imagine that at some point in the decimal expansion of pi there would be, for example, a million consecutive zeros. Can this question be proven? And even if it can't (or it's way too difficult), which intuition would be probably closer to reality?