EventHorizon
-
Posts
578 -
Joined
-
Last visited
-
Days Won
8
Content Type
Profiles
Forums
Events
Gallery
Blogs
Posts posted by EventHorizon
-
-
You do not need to allow a die to have more than one of the same number. You can just increase the value of all faces above it by one to make room for the other.
Also, the relative ordering is all that matters. This means you can simply use the numbers 1 to N, where N is the sum of the number of faces on the dice.
This means that an isomorphic problem would be to find a string of the digits 1 to D, with repititions and where D was the amount of dice in the first problem, with the property if you (uniformly) randomly pick one of each digit and discard the rest, you'll end up with a (uniformly) randomly picked permutation. The length of the string would be N, the sum of the number of faces of the dice from the first problem. An example would be 01101001 is equivalent to two dice with values {1,4,6,7} and {2,3,5,8}.
One thing to notice about these problems is that if you ignore a die (equivalently, all of a given digit in the second problem), you will still be picking uniformly random.
This can lead to insights in the four dice case such as:
1. At least 3 of the dice need an even number of faces.
2. At least 2 of the dice need a number of faces that is a multiple of 3.
3. The product of the number of faces must be a multiple of 72. (The number of permutations of 4 objects (=4!=24) times the extra 3 from (2))
I'm not sure if one of the dice need a number of faces that is a multiple of 4 or not. With prime numbers it is simpler (need at least D+1-p dice with faces that are a multiple of p, where p is any prime number and D is the number of dice)
The fewest total faces is 12. It requires a coin (2 faces), a 4-sided die, and a 6-sided die.
The faces, using the string of digits notation, can be one of the following three (ignoring swapping numbers):
012001100210
012010010210
012100001210
I'm fairly certain the fewest number of faces is greater than 18.
I wrote some code to try and find the fewest, but it ran really slow. I have had a few extra thoughts on optimizations, which should speed things up. It requires a rewrite though.
I thought of limiting the search to palindromes, as the fewest faces for 2 and 3 dice were palindromes. I'll try not to do this unless the code is still far too slow.
-
This is a direct modification of plainglazed's strategy that gets 37. I was trying to get, after 18 cards, 10 correct and 8 bits of information. With that I could continue with my old 37 solution to end up with 38.
I thought I'd try to guarantee some pairs that are both correct, so I introduced a pair offset. This is the difference between the suit to guess for each pair (the first is selected by the orientations, then add offset). I decided to let the suit selected in the first pair signify the offset. If the cards are the same suit, yay, two free cards... and try the next pair. The offset is selected by finding the offset that produces the most correct guesses in the next 7 pairs. And I only needed 2 pairs with 2 correct cards each to get me to the goal (card 18 is guessed correctly from orientations 17 and 18, then get one of the pairs wrong on purpose to get the bits up to 8).
If neither of the two suits in the first unequal pair signify an offset that gives at least 2 pairs with both guessed correctly (so they both happen at most once in the seven pairs, giving (7 choose 2)+7+7+1 possibilities out of 4^7 = about .002) then give the offset that will be best (guaranteed to give at least 3 correct pairs by pigeon-hole principle). Doing the same method as before and getting one card wrong on purpose gives 10 correct cards but only 7 bits to work with.
I wondered where I could get that extra bit...
v v v v v doesn't work
racked up some debt!
I called it bit debt, where I'd 'borrow' from the future and pay it back after processing the group of cards.
It doesn't actually work that way, but it was what I called it. It is actually just grouping outcomes intelligently so you can tell what the first few bits are before seeing all the cards.
Here are the two situations I needed to show are possible for the simplest strategy I found that guarantees 38.
Getting four of a group of five cards correct takes 5 bits of information and leaves 4 bits of information afterwards. But then I applied 'debt.'
With the 3 bits, I can look at the first 3 cards.
If one of those cards is wrong, I have my 2 bits of informations right there since I know the last 2 will be correct. There are 9 ways this situation occurs. I group 8 of these possibilities together and group the last one with the possibilities that have the first three cards all guessed correctly (7 possibilities).
This groups the possibilities into two groups of 8. So depending on which group I end up in after those 3 cards, I got another bit of information.
There are 3 ways to get the fourth card wrong. Grouping the stray outcome with these gives a group of 4, so I have another bit to use. This gets me the last card... so I'm done.
We've already seen 6 of 8 in my strategy that gets 37. I was quite surprised when I found I only needed 3 bits of information up front.
After seeing 3 cards, the situation can be one of the three below
2 are wrong: (3 choose 2) * 9 = 27 outcomes.
1 was wrong: 3*3 possibilities that could each end up as one of 16 different outcomes. 9*16 = 144 outcomes. (all the rest correct + 3 different ways to miss one of the next 5 cards = 16 outcomes)
All correct: all correct + 3 ways each to miss 1 of the 5 cards + (5 choose 2) * 9 = 106 (don't need 21 of them though)
It was nice that when 1 card was wrong it could be one of 16 outcomes. Group 8 of those together for 128 outcomes, and 1 with the rest. The other group is (106-21)+27+16=128.
If 1 card was incorrect, you could look at the next 4 cards since they are already in groups of 16. If any of those 4 cards are wrong, you know the last card is correct. If they are all wrong, it leaves 4 possibilities (last card can be wrong in 3 ways or be correct). This is a group of 4 so you can look at the final card.
If the situation seen is in the second group, we can look at 1 more card due to the group of 128 outcomes.
If the fourth card is the first incorrect card seen then the outcome could be one of 13. There are 3 ways for the fourth card to be wrong, so there are 3 groups of 13 outcomes. Add 3 from the 27 outcomes (2 wrong in first 3), to reach 16 (can look at the next 3 cards, leaves a group of 4 (final card could be wrong 3 ways or correct)).
If the fourth card was correct, that leaves (4 choose 2) * 9 + 13 = 67 - 21 (extra outcomes above the needed 2^8) possible outcomes with all correct so far, and the 18 (27-9 from the 3*3 borrowed) from 2 of the first 2 wrong. Grouping the 18 with 46 gives a group of 64. Look at the next card.
If the 5th card is the first missed card, it could be one of 10 outcomes. Group each of the 10 outcomes representing the 3 ways this could happen with 6 outcomes from 2 of the first 3 being wrong. Each of those are a group of 16.
If all 5 cards were guessed correctly, there are 1 (all correct) + 3 * 3 (one cards missed in final 3) + (3 choose 2) * 9 - 21 (extra outcomes above 2^8) = 16.
Since we're down to a group of 16, look at 2 more cards.
If one of those two cards is missed, it could be one of 4 possible outcomes (last card wrong in one of 3 ways or correct). Since we only needed 16 outcomes in this region on possibilities and we've grouped them down to 4 (only needed them down to 8), we're done. We can look at the final card and get the final bits of info.
Sorry if that was hard to follow, I was describing a mess that covered half a page.
Get the first three orientations to give three bits of information. Miss the first 3 cards.
Group the next 40 cards in groups of 8 and get 6 cards correct in each group.
Get 4 of the next 5 cards correct leaving 2 bits.
Get the next 2 cards correct using those 2 bits.
Get the final 2 cards correct.
3+8+8+8+8+8+5+2+2=52
0+6+6+6+6+6+4+2+2=38
Checking outcomes to make sure the bit 'debt' works fine is tiresome. I thought of writing a program to calculate maximum debt for each situation, but that seemed like a lot of work. I may still do that later. (I did already write one to calculate bits produced by missed cards, and used that to find '6 of 8' and large groups to claim you can get 'all' of an infinite deck.)
I did find a heuristic that seems pretty good. It is basically to make sure that the amount of outcomes without a missed card yet can be put into groups that halve with each successive card taking into consideration the superfluous outcomes greater than the needed power of 2.
Using this I found two groupings that work according to the heuristic, but I'm currently to lazy to make sure:
6 bits > 18 of 23 correct > 6 bits
6 bits > 15 of 18 correct > 2 bits
For 39 then, start by pairing cards (2 3) (4 5) (6 7) and using plainglazed's plasmid inspired method to get 3 correct and 4 bits of info. Miss one card on purpose (or not... 1 more outcome) to give 2 extra bits.
This means after 7 cards, you have 2 correct and 6 bits of info.
7+23+18+2+2=52
2+18+15+2+2=39
bits after each group
6,6,2,0,0
Other possible 39s with one main grouping that I haven't even checked the bit debt heuristic yet:
9+39+2+2=52
3+32+2+2=39
7,3,1,1
7+41+2+2=52
2+33+2+2=39
6,4,2,2
The extra bits left over could make the groupings possible by not needing to use as many outcomes. Half off per extra bit.
Here's some 40s that would require crazy debt, but haven't checked the heuristic (numbers are bigger than I want to work with by hand). I also have to wonder if 2 or 3 bits is enough, but there are 9 or 10 missed in the group which creates crazy amounts of outcomes. Who knows...
2+46+2+2=52
0+36+2+2=40
2,3,1,1
3+45+2+2=52
0+36+2+2=40
3,2,0,0
3+45+2+2=52
1+35+2+2=40
2,4,2,2
-
I've got a strategy that gets 38 (or more) on 99.8% of decks, and needs one more bit on the rest... one bit... grr.
Edit: Hey... 500th post!
v v v v doesn't work
Edit 2: I got a strategy that guarantees 38. I'm going to flush out this idea before posting (hoping I can get 39).
-
We've mentioned this before, and plainglazed's new algorithm gives 75% (9 of 12, same as my modification 6 of 8).
I decided to see what would happen if we used plainglazed technique, including my addition of using all the possibilities with less missed cards, and see what happens as the cards in the groupings increases. It turns out that you can get....
80% with 80 cards per grouping.
90% with 1640 cards per grouping.
95% with 2820 cards per grouping.
96% with 3375 cards per grouping.
97% with 4267 cards per grouping.
98% with 5950 cards per grouping.
99% with 10700 cards per grouping.
99.5% with 19399 cards per grouping.
99.9% with 79961 cards per grouping.
99.99% with 633144 cards per grouping.
So with an infinite deck, you can get basically all of them.
-
Had bumped this thread over a month ago after an extended period with a previous optimal answer. It's about to go off of the front page of the forum and even though there is at least one person following this topic (that you plasmid?), think it's about time to offer another solution. Besides, suspect this solution can be bested.
the direction of the plane on the first two cards indicates the suit to be guessed on cards 2-14. Out of those thirteen cards at least four must be correct (pigeon hole principle). The direction of the plane on cards 3-14 along with the direction of the plane on cards 15-26 could give twelve more correct suit predictions. One could intentionally miss any one of those twelve cards three different ways. Now three of those twelve (cards 15-26) could be missed in 12C3 or 220 different combinations and those three cards could be missed 33 or 27 different ways for a total of 5940 permutations which is greater than 212. In other words, every 12 digit binary number could be represented thus one can correctly predict 9 out of cards 15-26 and again have 12 bits of extra information. So 4 out of 14 + 9 out of 12 + 9 out of 12 + 12 out of 12 gives 34 out of 50 correctly predicted with the last two predicted as previously determined.
Think that logic is sound. 37 anyone?
Very similar to the one you gave.
First two cards give the suit to guess for cards 2-10. You can get 3 of those cards by the pigeon-hole principle.
Cards 3-10 give their bits to let you guess cards 11-18. You can miss 2 cards, 8c2 = 28 pairs in 3^2 different ways = 252.... not quite 2^8. However, you could also just miss 1 card intentionally which gives 8c1 * 3 extra possibilities for a total of 276. That's the extra 8 bits of info needed for the next group.
Just like yours, you'll get the last group all correct and the final two.
3 of 10 + 6 of 8 + 6 of 8 + 6 of 8 + 6 of 8 + 8 of 8 + 2
= 3 + 6 + 6 + 6 + 6 + 8 + 2
= 3 + 24 + 10 = 37
-
Is there some other commonly accepted mathematical construct, e.g. denoted for set A by [A], that evaluates to a number, such that if A is a strict subset of B, then [A] < even for infinite sets?
One more requirement for [A]: for finite sets, [A] = |A|
One more requirement:
If A is the real interval [0,1], and B = [0,0.5) U (0.5,1] U {2}
Then [A] =
B is the same as A, except that 0.5 is removed, and 2 is added.
B is no longer a subset of A, but from an intuitive perspective should have the same "quantity of points".
For your example A and B, there's always set difference (eg, |A-B| = |B-A| ).
For continuous segments of reals and n-tuples of reals there's length, area, volume, hyper-volume, and further n-spaces. But you'd still need to represent the missing lower order segments within. An option would be to have a tree structure whose child nodes are the missing or added segments of lower order. But this could make comparisons anywhere from difficult to meaningless. This would still have problems representing things that aren't extremely well-behaved and contrived. An example would be [0,1] - Q, where Q is the set of all rationals if Q was a set that wasn't a named and known set.
It seems there are possibilities where you could have one set's cardinality less than another in the limit as some finite intersecting set grows. This would still be meaningless with sufficiently complex sets, and would be highly dependent on the intersecting set and the way it grows (as different choices could give drastically different results). This would also have problems due to the intersecting set being finite when both sets are uncountable degrees of infinity (may just compare a tiny infinitesimal portion).
I'm fairly positive any such operator would only be useful with the most well-behaved and contrived of sets, and be easily 'fooled' and/or misleading with the rest... (sort of like = with cardinalities of infinite sets)
A big part of the problem is that you can map (eg, bijection) all reals to a small section of the reals. You can't assign a different number as the "quantity" of the points within. So the "quantity" should be the same after abstracting away the sets. Such is the nature of uncountablility. Set operations seem to me like the only "good" way to compare them.
-
What things can I include in this post more than are contained in my previous posts?
Notice I used more in the sense of other, extra, additional, etc. We agree, except I'm harping on the various definitions of more.
Just wait until I start arguing over what the definition of is is...
I've seen those examples of sets of various degrees of infinity, and have had to come up with various bijections including them. But it doesn't say whether bijections are always necessary or if math can be used instead. Perhaps in these cases the symbolic math is just shorthand for the bijections already given. But that seems to be the way with math in general... operators are defined by previously defined operators and/or algorithms including other previously defined operators.
Aleph0! = Aleph0 * (Aleph0-1) * ... * 1. Since Aleph0 = Aleph0 * Aleph0, the limit seems to be Aleph0.
But if you replace those all with 2's... it is equal to Aleph1.
Aleph0Aleph0 = x ... you'd expect it to be >= Aleph1 since 2Aleph0=Aleph1 (assuming GCH).
log(Aleph0Aleph0) = log(x) ...ignoring the question of what that means.
Aleph0 * log(Aleph0) = log(x) ...log seems to subtract 1 from the aleph number... what is Aleph-1?
Aleph0 = log(x)
eAleph0 = x
Aleph1 = x = Aleph0Aleph0
Since 2Aleph0 <= Aleph0! <= Aleph0Aleph0 and 2Aleph0 = Aleph0Aleph0, 2Aleph0 = Aleph0! = Aleph0Aleph0.
SUMi=1Aleph0 0 = 0 ...additive identity
SUMi=1Aleph0 1 = Aleph0 ...could use anything greater than the additive identity.
SUMi=1Aleph0 i = Aleph0
SUMi=1Aleph0 Aleph0 = Aleph0 ....since Aleph0 = Aleph0 * Aleph0
PRODi=1Aleph0 1 = 1 ...multiplicative identity
PRODi=1Aleph0 2 = Aleph1 ...could use anything greater than the multiplicative identity.
PRODi=1Aleph0 i = Aleph0! = Aleph1
PRODi=1Aleph0 Aleph0 = Aleph0Aleph0 = Aleph1
Makes perfect non-sense to me
....
Actually, if you have multiplication representing a cross product of sets (ie, all possible tuples... and the obvious/common/correct interpretation when applied to sets), then Aleph0Aleph0 is the set of infinite length tuples whose elements are any integer (wlog, i'll say positive integers... easier for the bijection).
(Edit: could also interpret it as the set of all multisets of a countable set. Instead of included or not, it is how many are included.)
If the integers that are the tuple elements were bounded, it would obviously be the same cardinality as the reals (represented in the base number of the bound).
A bijection between the reals and this set would be the following.
Let the reals be given in binary.
Two 0's in a row is a sentry marking the end of the current segment.
For a 1, list a '1'. For a 0, list a '01'.
Each segment represents an integer in the infinite length tuple.
All of the set of infinite tuples are covered and the reals between 0 and 1 are used to map onto (so '0.' whatever is needed for the matching infinite length tuple).
The tuple is [1,2,3,4,5,6,7,...]
The real is 0.(1)00(101)00(11)00(10101)00(1011)00(1101)00(111)00... with the integers from the tuple marked in parenthesis.
So, assuming GCH, Aleph0Aleph0 = Aleph1 after all
-
If extra, or better, other, were used in OP, the answer would be Yes.
But with more, as in OP, the answer is No.
But it's best to say the points in the cube and its edge have the same cardinality. That gets us off the hook a little, because cardinality is a well behaved algebraic number only for finite sets. For infinite sets, Aleph0, Aleph1, Aleph2, are symbols that are not like algebraic symbols. Specifically, they are invariant to addition, multiplication, squaring, cubing ...
Aleph1 == Aleph1 + 1 == Aleph1 x Aleph1 == ... And so forth.
That's why asking questions about the Alephs that include words like "more than" lead to counterintuitive results.
But 2Aleph1 == Aleph2.
That is, the set of all subsets [power set] of an infinite set jumps up to the next higher cardinality. The proof that the elements of any set can not be paired 1-1 with the elements of its power set is both simple and elegant.
Cantor [can't or] originally thought Aleph1 x Aleph1 would lead to Aleph2. That is, the points in a plane would have next higher cardinality than the points in a line. And a cube would have the next higher cardinality than the plane. And so on.
But when he tried to show this, he instead proved all three cardinalities were the same. Much to his surprise, and now to ours.
So the point of this puzzle was to pause and wonder at the result that adding and multiplying, squaring or cubing do not affect the cardinality of infinite sets.
And that result can be shown, as Bushindo did, by finding a bijection between the cube and an edge.
One point I omitted to state outright (but meant to include) was that English (and spoken language in general) is quite subjective.
For instance, looking up "more" in the dictionary gives one definition as being "additional or further." Extra's definition sounds just like that ("beyond or more than what is usual, expected, or necessary; additional"). So I still think the question vague (if only because it is in English), and it seems I was mistaken when I thought it intentionally vague.
Also, even though it is commonplace nowadays and I'm positive I've done it before, I intentionally didn't call the cardinality of the set of reals Aleph1 due to the generalized continuum hypothesis being unproven (unprovable with common set theory, and some have even said it is not well defined so it has no truth value).
I did point out that (2Aleph0)3 = 2(Aleph0*3) = 2Aleph0.
And hinted that, where n is a positive number, nAleph0 = (2log2 n)Aleph0 = 2(Aleph0*log2 n) = 2Aleph0.
Since Alephn = Alephn * Alephn for all non-negative integer n, the same could be done for any Alephn.
This means, assuming GCH, that Alephn raised to any non-zero finite number is Alephn and any positive finite number raised to Alephn is Alephn+1. What is AlephnAlephn? Since xx grows similarly to x!, is Alephn! the same as AlephnAlephn?
And is any of this math useful/valid/defined or does working with infinities mean you cannot use it so bijections are absolutely necessary?
-
Let Z be the set of all integers and Q be the rationals. We know that |Z| = |Q| and that |Q|-|Z| is undefined since |Q| and |Z| are both infinity. But isn't it true that Q contains more than just integers? Since Q is a superset of Z and the extra elements of the set Q are still numbers, can't it be said Q contains more numbers than the numbers contained in the set Z... even though the cardinality of the sets are equal?
In other words the number of elements in each is the same, and yet one set contains more elements in addition to those contained in the other.
Let C be the set of points in the cube.
Let E be the set of points in the edge.
We know |C| = |E|. I've shown they're the same degree of infinity and others have given one-to-one mappings. So we know the number of points in each is the same. But does that necessarily mean one doesn't contain more points than are contained in the other?
We know |C| - |E| is undefined since both |C| and |E| are infinity. However, |C-E| is infinity. So if we wait to abstract away the actual sets, we can have an answer that isn't just undefined.
So I guess what I'm saying is that if the question was "is the number of points in the cube greater than the number of points in the edge", the answer would be no since both are infinity. But if the question isn't outright asking about the cardinalities and comparing their values, it could be different. If it is only asking about the points not contained in the edge, then the answer is yes. We have the sets and know their difference. So we know what points are contained in the cube in addition to those contained in the specified edge.
So just like I would say Q contains more than just the numbers contained in Z (even though they both contain the same number of numbers), the cube contains more points in addition to those contained in the edge.
So, yes, we all agree the cardinality is the same. The question now is whether the original question is asking "|C|>|E|" or "|C-E|>0?"
"Does the cube contain a greater quantity of points than the quantity contained in one of its edges?" - Answer: No.
"Does the cube contain more points than the quantity of points contained in one of its edges?" - Answer: No.
"Does the cube contain more points than just those points contained in one of its edges?" - Answer: Yes.
"Does the cube contain extra points in addition to those contained in one of its edges?" - Answer: Yes.
"Does a cube contain more points than those contained in one of its edges?" - I'd still answer yes.
Actual question: "Does a cube contain more points than are contained in one of its edges?"
It does sound slightly vague to me as to which it is asking, but I'm still leaning towards the latter interpretation (ie, answer is yes).
I'm sure if I ask bonanova which interpretation he meant... he'll say "I can't or I won't say."
-
First lets look at the degree of infinity of the number of points in each. The number of points in the edge has the same degree of infinity as the same as the number of real numbers, which is 2Aleph0. If you look at where that 2 came from, it really is just any finite number greater than 1. You can see this easily by noting that n*Aleph0=Aleph0, where n is any positive finite number. If you assume the number of points on an edge was x, then the number of points in the cube would be x3. Substituting 2Aleph0 for x gives, (2Aleph0)3 = 23*Aleph0 = 2Aleph0. So the degree of infinity of the number of points in the edge are the same as that of the number of points in the cube.
The cube contains 12 edges, so it certainly contains more points... right? That's even ignoring the internal points and points on the faces of the cube! The degree of infinity is the same, but there are surely points more in the cube because it contains the edge and more. (infinite copies of the edge even! You can let y and z be any constant value in [0,1] to get another copy)
So the answer is yes if only because every point in the edge is in the cube and not vice versa. (e.g., a set contains more elements than any strict subset of itself)
-
so i guess the next logical question is this, if every irrational number is countably infinite in it representation, can you represent all irrational numbers in a countably infinite way? that is, we know we can form any individual irrational number with a series of 1's and 0's. there is no individual irrational number we can't form this way. now imagine we have a countably infinite number of people flipping coins. which irrational number won't be hit?
This leads exactly to Cantor's diagonalization argument, which can show that between any two distinct numbers are an uncountably infinite number of irrational numbers.
Here it is (for between 0 and 1 at least... though it is trivial from here to any two distinct numbers):
Assume there is a way to list them all in a countably infinite way. Let the list be numbered so Ir1 is the first irrational number listed, Ir2 is the second, etc. Let IrN(M) be the value of the Mth decimal place of the Nth irrational number listed. You can create a missed irrational number whose Nth decimal place's value is different than IrN(N) for all N. Therefore it cannot be listed because if it was, and assuming it is the Kth number, then it would need to differ from itself in the Kth decimal place's value.
So a given irrational number has a countably infinite number of decimal places, but there are 2^aleph0 number of irrational numbers (and consequently, real numbers) as we have just shown by the coin flip representation, where aleph0 represents a countably infinite quantity. So we've shown that 2^aleph0 is greater than aleph0. And, as speculated by the continuum hypothesis, 2^aleph0 = aleph1, which is the next in the hierarchy of infinite sets. This, however, has not been proven, so there may be provably smaller uncountably infinite sets.
Edit: According to wikipedia, it has been shown to be unprovable given the common set axioms. Also, as bonanova points out in the next post, the simple answer to "which irrational number will be missed" is you'll miss 100% of them. Yeah, I overlooked actually answering that question as stated.
-
okay maybe some clarification is in order.
clearly no finite number of flips will be enough, assuming you're not allowed to apply a function to it.
but can you mathematically flip an infinite number of coins to represent an irrational number?
i guess what I'm asking is, is the digits of a single irrational number countably infinite?
As you know, the integers are countably infinite. You can simply map each nth integer to the nth digit after the decimal place to see that the digits of an irrational number are countably infinite.
You ask if you can flip an infinite number of coins to represent an irrational number, and the answer is yes.
If you represent the number in binary and have a coin per decimal place, you'll **always** end up with an irrational number. To be rational, the digits would eventually need to continue to repeat through infinity. By this construction, each digit is random and therefore no repetition can be continued through infinity. In other words, the probability you end up with a rational number is 0%, and the probability you end up with an irrational number after flipping an infinite number of coins representing its digits is 100%.
Can you end up with a rational number using a fair coin and an infinite number of flips? In theory, yes (it could, for example, come up heads every time). In practice, no... it is impossible.
Can you end up with a rational number using a fair coin and an infinite number of flips if you allow reordering of digits/coins? Yes. In fact, you can end up with **any** rational number whose repeated pattern contains at least one one and at least one zero... and you'll still use every coin... eventually... if you want to.
-
Now that bonanova and EventHorizon have posted solutions to the original problem, allow me to pose an extension. What is the average number of coin flip required for bonanova's and EventHorizon's approach to sampling the probability p? Extra bonus for putting the answer in closed form (i.e., without requiring an infinite sum).
that for each digit in the binary representation, if your coin flip is not the outcome representing the digit, you stop. So 50% chance of needing another coin flip at any point in the process.
So there's a 50% chance of it taking only 1 flip.
There's a 25% chance of it taking 2 flips.
There's a 12.5% chance of it taking 3 flips.
etc.
So the infinite sum for the average flips needed is the sum from i=1 to infinity of i/(2^i).
f(y) = sum x=1 to inf xy^-x
f(y)/y = sum x=1 to inf xy^-(x+1)
integrate (f(y)/y) + c = sum x=1 to inf -y^-x
-integrate (f(y)/y) + c = (1/y)/(1-(1/y))
-integrate (f(y)/y) + c = (1/y)/((y-1)/y)
-integrate (f(y)/y) + c = 1/(y-1)
integrate (f(y)/y) + c = -1/(y-1)
f(y)/y = d(-1/(y-1))/dy
f(y)/y = d(-(y-1)^-1)/dy
f(y)/y = (y-1)^-2
f(y) = y(y-1)^-2
Plugging in 2 for y gives f(y)=2.
So it takes 2 flips on average.
Of course, it would be easier to formulate it this way...
All need at least 1 flip.
50% need at least an additional 1 flip.
25% need at least an additional 1 flip.
etc.
So 1 + .5 + .25 + .125 + ... = 2.
-
...
The volume that has been put forward as the largest is convex,
but in fact it pertains to the convex solid with the smallest volume!
If it helps, the shape of the largest solid is the simplest, and has
a volume that's larger by almost 1 in3.
I've got a convex solid with a smaller volume than the one posted so far...
After a while of wondering how another solid could work I found that if I had a clay model of the solid already found, that I could simply use a plane and slice a small piece off along the curve connecting the base of the triangle to the top of the square.
So how much could I shave off? The requirement of being convex would actually give me the answer. First, take the required orthogonal cross sections and simply connect each point in the cross sections to each other (repeat if necessary) to get the convex closure / convex hull. Easy to visualize now, huh? (kidding of course)
Still a bit confused about how connecting all those points would look, I found that the triangle is superfluous given the other two (already have the two base vertices from the circle and the top from the square, and the convex closure given these points includes the triangle cross section). That simplified things greatly. So I simply connect the circular base to every point on the top edge of the square. You can think of this as skewing (to keep the cross section parallel to the base a circle) the top of a cone from one top vertex of the square to the other and including all the volume it passes through. Another visualization would be to have two intersecting skewed cones terminating at the top two vertices of the square and connect the two skewed cones with planes.
Now for the volume of this solid. Everything I need to solve this is in the visualization of two skewed cones. Each cross section parallel to the circular base would be a rectangle with semicircles on either side. The width of the rectangle would be 2 - h, which is easy to see from the cones. This makes the radius of the semicircles (2-h)/2. The length of the rectangle would be 2 - 2*radius of semicircles = 2 - 2*((2-h)/2) = 2-2+h = h.
The area for the cross section at any particular height would then be
f(h) = area = (2-h)*h + pi * ((2-h)/2)^2
area = 2h-h^2 + .25 * pi * (2-h)^2
area = 2h-h^2 + .25 * pi * (4-4h+h^2)
area = 2h-h^2 + pi - pi*h + .25 * pi * h^2
Integrating with respect to h gives
F(h) = h^2 - (h^3)/3 + h*pi - .5*pi*h^2 + (1/12) * pi * h^3
Evaluating from 0 to 2 gives
F(2)-F(0) = 2^2 - (2^3)/3 + 2*pi - .5*pi*2^2 + (1/12) * pi * 2^3 - (0 - 0 + 0 - 0 + 0)
F(2)-F(0) = 4 - 8/3 + 2*pi - 2*pi + (8/12) * pi
F(2)-F(0) = 4/3 + (2/3) * pi
F(2)-F(0) = (4 + 2*pi)/3, which is about 3.4277 in3
As of yet, I'm still at a loss for the solid with the maximum volume.
-
Yup, that's essentially what I got.
What's interesting is combining the last puzzle and this one you can show that with any biased (or fair) coin you can emulate any other biased (or fair) coin or any die of any number of sides. I didn't include emulating a biased die, but that's not much of a stretch. (this does assume both heads and tails can and do occur)
I thought I'd include it even though it's similar to what bonanova posted.
Take the binary representation of the probability of a head coming up that you are trying to emulate. If you let heads be 0 and tails 1, start flipping the coin and once you have a different outcome than in the binary representations stop. If you got a heads instead of a tails, the emulated outcome is heads. If you got a tails instead of heads, the emulated outcome is tails.
You can actually extend this directly to emulating any biased (or fair) coin or die with any other biased (or fair) coin (or die, as you can emulate a biased coin by trivially rerolling if one of two selected outcomes don't come up) that you know the outcome probabilities for. If you don't know it's probabilities, emulate a fair coin first, but then it's not quite direct.
You just need to partition the space on a number line from 0 to 1, giving each outcome to be emulated the space corresponding to the probability it should occur. Start with the whole space, [0,1]. Subdivide the space according to the probability heads comes up in the coin you are using. So the ratio of the length representing heads to the length representing tails is the ratio of heads to tails in the probability of the biased coin you are using. If heads comes up, repeat using the portion currently representing heads. Similarly for tails. Once you have subdivided small enough that the whole length is within the partition representing one emulated outcome, that is the outcome to use.
-
The golden ratio is (1+sqrt(5))/2. The reciprocal of this happens to be (sqrt(5)-1)/2 which is about .618.
I happened to have a biased coin that would come up heads with exactly that probability. This was my lucky coin, and I used it to bias my decisions slightly towards the ones I favored. It was quite a tragedy when I lost this coin (not only for it's decision making qualities, but it was, coincidentally, made of gold).
How can I simulate a coin toss from my missing lucky coin using a fair coin instead?
-
Hey jim. It is common courtesy to use spoilers so others will see your answer only if they want to. Please use them in the future. (Will a mod spoilerify his post please?)
That being said... good job on 1&2. I wanted a different answer for 1, but 2's answer will obviously work too.
As for 3, it was a valiant attempt. You've identified a number of the needed elements in the solution, but you've missed something. Also, I think you may have misunderstood the problem as choosing between two options with an unequal probability based on N. The problem is asking you to choose from from a set of N different options with equal probability. This is a simple difference, but not the only thing I believe is missing from the solution.
Though I should point out that I don't have a full solution worked up yet.
-
I took the coin from out of the biased random number generators jar that had been collecting dust in the corner of the Den, but I needed to choose between two options with 50% probability each. I thought this would be easy since I already calculated the probability that heads would come up for this coin.
From ujjagrawal's puzzle: After flipping the coin 4 times, having heads come up 2 times is the same probability as heads coming up 3 times.
Also, assume the probability heads comes up on any given flip is neither 1 nor 0. Yeah, it's a coin so those are veritable impossibilities, but thought I'd spell it out regardless.
1) How can I choose between the two options with 50% probability?
2) I accidently drop ujjagrawal's coin in the jar, and now don't know which one it is. I grab another coin from the jar. How can I choose between the two options with equal probability using this new coin (assuming both heads and tails can be outcomes on any given flip and occur with constant probabilities)?
3) How can I use the coin from (2) to choose between N options, where N is a positive integer, with the fewest number of coin flips needed on average?
-
Let the probability of getting heads in a single flip be p.
The probability of getting 2 heads and 2 tails is (4 choose 2)*p^2*(1-p)^2
= 4!/2!2! * p^2*(1-p)^2
= 6 * p^2*(1-p)^2
The probability of getting 3 heads and 1 tails is (4 choose 3)*p^3*(1-p)
= 4!/3!1! * p^3*(1-p)
= 4 * p^3*(1-p)
Setting these equal gives
6 * p^2*(1-p)^2 = 4 * p^3*(1-p)
6 * (p-p^2)^2 = 4p^3-4p^4
6p^2 - 12p^3 + 6p^4 = 4p^3-4p^4
6p^2 - 16p^3 + 10p^4 = 0
5p^2 - 8p + 3 = 0 (divided by 2p^2 and reordered terms)
Applying the quadratic equation gives
p = (8 +/- sqrt( 64 - 4 * 5 * 3 ) ) / 10
p = (8 +/- sqrt( 64 - 60 ) ) / 10
p = (8 +/- sqrt( 4 ) ) / 10
p = (8 +/- 2 ) / 10
So p (which is the probability of getting a head in any one flip) is either 1 or 6/10.
Since this is a coin we're talking about, I doubt p=1.... so p = 6/10.
Here's a little verification:
If p is 1, the probability of both outcomes (2 head and 2 tails and 3 heads and 1 tails) is 0. Tails simply cannot come up.
If p is 6/10:
2h2t: 6 * p^2*(1-p)^2 = 6 * (.6)^2*(.4)^2 = 6^3 * 4^2 / 10^4 = .3456
3h1t: 4 * p^3*(1-p) = 4 * (.6)^3 * .4 = 6^3 * 4^2 / 10^4 =.3456
Edit: Since I divided by 2p^2 earlier.... it is possible p=0 too (but unlikely since it is a coin). In this case, like in the case of p=1, both the outcomes have probability 0.
-
I thought of another advantage. You can easily find all the unsolved puzzles. I'm kinda interested in the puzzles that have slipped through without being answered (I've already seen a few interesting ones from my very incomplete database). I know there are a few I've forgotten about, but had an idea to try or was planning on writing code to solve. There are also some puzzles whose answers were never confirmed. Some optimization problems may have better solutions out there somewhere. Perhaps each puzzle can be tagged one of unsolved, unconfirmed, or solved.
Will the search work only based on tags or will it be full text search? Might be interesting to have both options - tags if you like a certain type of puzzles and full text search if you want to find a puzzle you read a few days ago (eg. search all "Morty's" puzzles).
If they have access to the web, they could text search on the forum. Searching by author would be quick like tag searches. I was trying to avoid full text search. I don't want to deal with caching, creating word indexes, or other such optimizations. Depending on the platform it may be quick enough to search linearly through the database, but maybe not. Some optimization may not be that bad... but I haven't really looked too much into search optimization.
Adding tag for difficulty might help - user could solve puzzles adequate to the level of skills. 1 admin person should rate all puzzles to avoid discrepancies.
I think that's a great idea. Having one person rate them all may not necessarily remove discrepancies unless they follow a strict rubric of some sort. Having been a T.A. and graded tests I've seen how grading subjective answers will tend to let scores slide around over time without something to tie it down. Then again, a simple easy, medium, or hard (and very hard / impossible?) doesn't seem like it would be too hard to get a good approximation even with different people rating.
It may be easy to estimate the solution for some puzzles quickly or to be able to show a solution works easily, but it may have a tough logical derivation / proof. Things like this will complicate marking the difficulty. Some puzzles have an easy way to solve and a hard way, too. Perhaps multiple difficulty ratings (one for each method and one for proof), but that may be overkill. Maybe just give the range of difficulty since some puzzles include multiple parts.
Link to solution might be useful - if someone disagrees and wants to check reasoning of others.
Again, that would be a another good thing to include in the database. All it would need is post number(s). I think it would be good to include the reasoning/proofs in the database too (like I did, where applicable, with the incomplete database). Perhaps in a separate text field, now that I think of it. That way it could easily be separated programmatically from the simple answer if the database needs to be made smaller.
Is it possible that visitor just clicks 1 thing from the web and he/she immediately is browsing the database. In other words, no need to install anything on computer (eg. no need to install Java environment) and everything can be visible on any desktop/mobile (not depending on operating system or installed programs)?
Is there an easy way to incorporate the database into Android App? The major obstacle used to be that the solution has to be found in the forum thread while your approach could give the solution directly. On one hand, Android App would be a great place to have all content available offline, however, on the other hand it might be too big in MB to download all puzzles onto phone. So I am still thinking of an effective way of distribution.
I think that nature of this database (offline browsing of well sorted content anywhere) would have the best use on mobile phone - that's what we could focus on. What do you think?
If you are not requiring java, then I think that leaves html5 or flash for the web 1-click options (assuming we don't want simple html pages (would be really easy to make from the database with code), or cgi, servlets, etc). I don't know either (looked into flash a bit), but have been meaning to learn one. I think it could be doable (definitely on a computer (there are larger flash games files than what the database will be when compressed), though a mobile version may need restructuring depending on the platform).
The Android app itself would simply be a reader/viewer for the database (or could potentially have the database embedded in it, but I'd prefer it otherwise). The actual XML file I was thinking of, uncompressed, will likely be around 7-10mb (This is extrapolating from the size of my incomplete one, which may be off... though I don't think it would be more than 30mb), and a third of that size compressed (again, extrapolating from current compression rate). We could also separate the puzzle and solutions from the information about them (tags,author,title,etc in the index/"Table of Contents" file along with pointers into the larger file of puzzles and solutions (which could possibly be in some compressed form, and just decompress the puzzle/solution requested)), that way less data needs to be stored in memory and traversed regularly... and it would probably work fine for an Android app (I have no experience with Android or its apps. I just checked online and I think most cheap android phones have about 512mb of working memory, support for an SDHC card (so lots of storage space), and around a 1ghz processor... that should be more than enough of all those (by a lot).)
Once the database is made, it can be changed programmatically to be used on specific platforms. We'd just need to know what information the app on each platform will need left in the database, and what form the database needs to take. Of course, we'd need to actually code up the reader app on the specific platforms. It shouldn't be that hard to get it working on any specific platform (with possibly the exception of iPhone/iPad... since you need a mac (though it may be possible with a virtual machine hackintosh... still haven't gotten around to looking into that)).
The simplest app for me would just be some java code on my computer. It does sound like a good idea to have an Android app. We could also try a flash version for the web (just the index so it's small and just link it to the forum). We just need to get the database ready, then find ways to display it later.
-
and I came up with the same probabilities as curr3nt.
I thought perhaps combining the two darts would still have a larger variance and that would change things. I worked up formulas for the binomial distribution, combined them, and ended up with another binomial distribution of the new probability .98% (which really should have been obvious from the Bernoulli trial).
There surely was something I was missing.
Since then I've decided that....
I noticed the word reproducibly, and that changes things since if he never gets less than 97% we are no longer dealing with the binomial distribution for him.
Let B(k;n,p) be the probability of getting k successes in a Binomial distribution with n trials and a probability p of success.
Assuming he always gets exactly 97 out of 100, he will still lose since the probability the duo get 98, 99, or 100 is (B(100;100,.98) + B(99;100,.98) + B(98;100,.98)) which is slightly over 67%.
But will Alex ever get more than 97 out of 100?
Assuming Alex's distribution is uniform (so he gets 97, 98, 99, and 100 darts out of 100 with equal probability)...
The probability the duo will win is:
.25 * ( B(100;100,.98) + B(99;100,.98) + B(98;100,.98) ) +
.25 * ( B(100;100,.98) + B(99;100,.98) ) +
.25 * ( B(100;100,.98) ) +
.25 * 0
= about .303144
The probability they tie is :
.25* ( B(100;100,.98) + B(99;100,.98) + B(98;100,.98) + B(97;100,.98) )
= about .214740
This leaves the probability Alex win at .482116.
But that only works if Alex's distribution is uniform between 97 and 100 when throwing 100 darts.
But what if they only throw 33 darts at a time? Alex must always get all 33 or he will not have reproduced the result of a percentage greater than or equal to 97%. In this case he will never lose.
So that's my guess. They always throw darts in groups of 33. Alex always gets 97% or more, so he cannot miss. Alex gets some more beer money.
Though perhaps I'm reading too much into it...
-
1
-
-
I'm thinking the database will simply be a condensed form of the forum. It will have the puzzles and solutions without the discussion in between. It will occasionally need to be updated with the newest posted puzzles and solutions.
The more puzzles, the easier the interface and search must be. Let's keep it simple.
I was thinking the interface would be fairly similar to the one I used in the simple XML editor I made. It would have a drop down box at the top that by default lists every puzzle, but you can prune the list by tag values ("tag a, but not tag b" etc). But I guess it would be a good idea to think of other ways to simplify searching for puzzles in the database without increasing the size of the database much. The editor/viewer/app is separate from the database, so someone could always build another app to read and view the database.
The reason I like the tag approach is that it is independant of the actual wording of the puzzle. If the puzzle deals with geometry, it should be tagged "geometry" regardless of whether the description mentions geometry or even geometric terms. So each puzzle will have a set of tags that describe the essence of the puzzle and not just the way it was worded. The problem is finding enough useful tags to make finding any given puzzle not take too long.
What are the advantages compared to live BrainDen version (apart from having it offline)?
It will be a condensed form so you can find the solutions a lot easier (click the solution tab instead of searching through pages of posts). Someone could go through the database and fix grammar errors, ambiguous descriptions, poor formating, etc. It would be personalizable, so you could mark favorites, annotate, have a "to do" list tag for puzzles to work on later, etc. People could add in their own puzzles that they want to store and remember, but hopefully they would post them in the forum as well.
Where/when/by whom could it be used? Is there a better way to propagate it compared to the live BrainDen site?
BrainDen site has static pages (old best of selection), this forum (great fresh puzzles), igoogle gadgets and Android App. I wonder how this new channel would fit in the strategy - what gaps it fills and what the added value is.
It's just a condensed mirror of the forum really. I guess you could think of it as something that goes along with the forum. I'm not really sure how much value it would have to the community, which is why I'm interested in people's thoughts on this. Hopefully it can become something useful to many and not just some personal project.
I'm thinking how I'll split up work is to have people take a section of the database to make pretty, add solutions, tag puzzles, and maybe add in hints. So I'd need to get the script done (which shouldn't be that bad) and make an editor to use (not necessarily complete and polished, just enough to edit and tag) first, then split up sections to be worked on and returned to me to be combined. I'm sure this would leave duplicates, so they'll be taken care of later as they are found.
I've got a script that is almost ready to get all the first posts (I've parsed out all the information), but I need to decide how to work with bbcode like spoilers and such. I also need to decide how to organize the XML/database so I can have the script output it in a form ready to be distributed and worked on.
-
Someone posted that they would like to have a paper copy of brainden to take on flights, camping, etc. I thought it would be nice to have a local electronic copy to search through, annotate, rank, mark favorites, mark ones to work on later, etc. It wouldn't be too hard to export from an electronic copy to a text document then into a word processor to format and print it out. XML is a standard, so I thought I may use that to store it.
I played around with handling XML documents in java (I generally use java when I want GUIs) and worked up a simple little XML editor and started manually copying and pasting puzzles into an XML document (and replacing images with text art). This turns out to be a very slow process. I got to around thread 1700 of 15000 (580 total puzzles in the file) before deciding there was a better way to approach it (though it was interesting to see all the unsolved puzzles and old puzzles I had forgotten about but liked). Not only this, but I wasn't recording who posted the puzzles, who gave the solutions, when it was posted, the brainden topic number (to easily find the topic on brainden later), etc.
For those who want to see my simple editor (source code included in executable jar file) and incomplete database, here it is:
Just run the executable jar file, load the "puzzles.xml" file, and the top dropdown box lists all the puzzles I got through. Click on one, and its information appears in the text areas. You can type in the boxes, but nothing is saved unless you press the update puzzle button (just switching to another puzzle will lose the changes). The application does seem to occasionally hang after selecting a file to load from or save to (so I kill it from a terminal window)... but I believe this is because I am running it on the newest version of ubuntu (not a point release yet), due to using open jdk 7, compatibility issues with linux and java, or some sneaky bug in my code dealing with file dialog boxes (but really...there doesn't seem like there's much to mess up there). Hopefully it runs great on other platforms.
I'm thinking I'll write a bash script to rip the first posts of all topics to a file, then manually prune repeats and other undesirables (should be much faster since I'm not loading web pages, and I won't be loading topic numbers that reach an error page), then manually go through each of them and find the posted solutions and add text art or descriptions in place of images.
I think I'll get at least the following pieces of information using the bash script:
-post date
-topic number
-who posted it
-title (if it exists)
-subforum it came from (ignoring the whole miscellaneous subforum)
-puzzle description (ie, the actual puzzle)
I'll do the following manually (after pruning undesirables):
-add solution (and person who posted it) or mark unsolved
-add tags to tell what kind of puzzle it is
-add Title (if it doesn't have one I'll make one up)
-replace images with text art or descriptions
-fix formatting
Here are some of the tags I'm thinking of using:
-Unsolved
-Math
-Logic
-River-Puzzles
-Truth-Lies-Questions
-Geometry
-Algebra
-Calculus
-Probability
-Develop-Strategy
-Sequence
-Words
-Word-Riddle
-Anagrams
-Decrypt-the-Message
-Hats-or-See-Everyone-Elses-Status
-Letters-to-Numbers
-Proof
-Optimization
-Search
-Constraint-Satisfaction
-Find-Similarity
-Measurement
-Cards
-Weighing
-Speed
-Physics
-Grid-Chessboard-or-Cartesian-Plane
-Matches
-Switches
-Explain-Why-What-or-Where
-Coins
-Drawing-From-Containers
-Children-Family-or-Ages
-Primes
-Paradox
-Puzzle-Pieces-or-Xominos
-Multiplayer-Competition
-Clock
-Design-a-Structure
-Subdivide-Area
-Computation-or-Programming
As for the viewer/editor, I'll plan to add in the following features:
-Export to text document (puzzles with their solutions or all puzzles first solutions after)
-Import file into current list
-Easily edit anything
-Can add in fields or tags and name them
-Tags as checkboxes
-Separate tab for each field (bigger text areas and don't need to see solution unless you click its tab)
-Ability to list by requested tag(s) and/or rank
Here are the questions I have:
Is there a better way to go about it than this approach?
Am I missing something that could easily be ripped using a script?
Should I not include some of the information listed above or include something else?
Did I miss any tags that would be good to use or do I have a useless one?
What other features should the new editor have?
Any other thoughts about this project?
Do you think this would be useful, or is it a waste of time?
Would anyone be interested in helping once I get to a point where I can divide workload?
-
Draw one ball from each bag to determine color. WOLOG it's blue.
Discard the bags that gave red balls.
Draw from a blue bag until a red ball is drawn.
Draw from another blue bag until a red ball is drawn.
...
Stop after the 10th ball is drawn.
This algorithm gives a minimum of 4 and a maximum of 8 balls of one color.
On average, 6.95...
Just thought I'd point out that those 4's are actually 6's in a red disguise.
Dicey Permutations
in New Logic/Math Puzzles
Posted
So, after reading your post and looking at the fewest for 3 again. I thought of one configuration to try. Since testing a configuration with my code is fast, I threw it into my code and...