Probability problem from Braingle

[Zag]

I've been plundering Braingle.com for riddles, puzzles, and problems, lately, but this was the first one that really struck me.

[Griffin]

Wow, that's really subtle. I like it!

[Zag]

I've been trying to grok this one. I hover on it, then it eludes me again. Here's my best attempt:

Consider a 6-card deck, with just aces and deuces in clubs, hearts, and spades. If you deal all possible 2-card hands.

------ - As Ah - As Ac - As 2s - As 2h - As 2c
Ah As - ------ - Ah Ac - Ah 2s - Ah 2h - Ah 2c
Ac As - Ac Ah - ------ - Ac 2s - Ac 2h - Ac 2c
2s As - 2s Ah - 2s Ac - ------ - 2s 2h - 2s 2c
2h As - 2h Ah - 2h Ac - 2h 2s - ------ - 2h 2c
2c As - 2c Ah - 2c Ac - 2c 2s - 2c 2h - -----

Flush rates
Overall: 6/30 = 1/5
(1) Hands whose first card is an ace: 3/15 = 1/5
(2) Hands whose first card is the ace of spades: 1/5
(3) Hands with at least one ace: 6/24 = 1/4
(4) Hands with the ace of spades : 2/10 = 1/5

In this case, it is easy to see, because if a hand does not have an ace, then it can not be a flush. So, by excluding the non-ace hands, we've excluded some of the non-flushes, but none of the flushes.

I guess I see it now (for good ). Look at it this way: #3 is the same as saying "excluding hands with no ace." Looking at the excluded hands, they will have a higher percentage of pairs (which are always non-flushes), because they are drawing from only 12 ranks, not 13. If we had said, "Hands with at least one card above 6" which is the same as "exclude all hands with only 2-6 in them." Note that almost all of those hands have a pair. You are still excluding a lot of hands, but only 4 flushes.

[Zag]

Here's another one from Braingle that I liked:

[lostdummy]

It seems that such water filled universe would not be very stable ;p

First introduced bubble would result in less gravitational pull on water on edge of that bubble, meaning water would retract even further from center of bubble (increasing bubble size), meaning even less attraction to new edge, meaning more retraction and even larger bubble....

In such way initial bubble will become larger and larger ... kinda opposite of gravitational contracting into black hole. And soon universe will not be any more "mostly water" ;p

[Quailman]

I would think that they'd move apart (though not by repelling each other). The bubbles are presumably lighter than the water (though there might be a gas that's heavier). If we look at the Earth, which is mostly covered with oceans, any bubbles head toward the surface. If the oceans were deeper - a lot deeper - extending to the center of the planet, any bubbles in it would head toward the outer surface, because the heavier substance - water - would be drawn toward the center and would displace the bubbles, forcing them upward. The same would apply if you made this model larger so that it filled the universe. The bubbles would head toward the edge of the universe.

[lostdummy]

Quailman, I'm not sure that we can compare bubbles in Earth oceans with bubbles in universe filled with water. On Earth there is clear center of gravity, and oceans are compressed toward that center - there is clear difference in pressure and gravitational force on different depths of ocean.

In theoretical "water universe" that would not be same. If we imagine homogeneous distribution of water and "infinite" universe, then at any given point in universe gravitational forces would cancel each other. In other words, there would be no "pressure", and nowhere for bubble to go. For that matter, there would be no "upward" and no "edge".

But there remains problem that I described above - instability of such universe. If we introduce one single bubble, then water at edges of such bubble would not have "canceled" gravitational influence any more - it would be attracted by water further away from bubble, without counter-attraction from bubble side. So it would futher retract from bubble center.

Of course, all this talk is hypothetical around gravity, so it ignore other "water" non-gravitational characteristics like electrical issues, molecules, pressure , etc. Forces such as those would probably overcome gravitational forces and make things quite more complicated.

Better "thought experiment" along this lines would be if we imagine universe filled homogeneously with neutrons , and then make "bubbles" as absence of neutrons in spherical space. Then we would have gravitation as major player much longer ;p

[Zahariel]

I admit it, I had to check the answer for this one to be sure, but I was right. Although Braingle's provided answer is quite poorly explained. Here's an explanation I've just come up with that I can actually understand: Quailman's point that the bubbles are "lighter" than the water around them is the important bit. Consider the environment around one large bubble. This large bubble effectively has negative mass (relative to the medium), so any massive objects (e.g. rocks) would tend to be repelled (attracted by the water across from the bubble). However, other bubbles nearby also have negative mass! So they will appear to be attracted to the large bubble as the water around them falls away. This is the same effect you see with helium balloons in a suddenly-braking car; all the massive objects in the car get thrown forward and the relatively negative-density balloons cluster in the back as the heavier air crowds them out of the front.

In principle you could construct entire "solar systems" of bubbles, if you used a frictionless medium. Our sun has very nearly unit density on average, so that works out to be a pretty good size.

In fact, if you simply think of the bubbles as having negative mass, then Newtonian gravitation clearly requires this result: multiply two negative masses together to get a positive inward force. Now, if this notional universe has both bubbles and rocks.... the gravitational situation gets really complicated.

lostdummy's argument that any given bubble would expand infinitely as the medium on the edges falls away is harder to refute, at least for me. In our universe, an object made purely of negative matter would hold itself together gravitationally (same reason as above), but I'm not sure that argument holds up in this situation. It SEEMS like it should, but... I think the counterargument here boils down to conservation of mass, which in this case ends up being equivalent to water pressure. Imagine building a big steel box inside this universe. There's some fixed amount of medium inside this steel box, so there's a fixed volume of bubble as well.

Of course, in the presence of negative-mass objects, you could claim that the expansion of a bubble is possible if, somewhere else, a chunk of medium solidifies into a positive-mass object. Now my head hurts. In principle you could actually do this experiment, but you need to use a superfluid or surface-tension considerations completely overpower any gravitic concerns, unless you have a convenient way to build a steel box full of water sufficiently big as to contain minor planets.

[Nsof]

[lostdummy]

Because idea of that problem (as can be seen in solution) is around gravitational issues.

All references to vacuum, pressure, ups/downs, surface-tensions are attempts to model real water, and if we are doing that there could be also water currents, molecular bindings, browning movements and what not - in that case solution definitely would not be just "bubbles attract", since it would depend on too many variables, and least of them would be gravity;

On the other hand, if we are just considering gravitational effects (which were used to describe solution), then what I posted about bubble spreading will hold. Note that bubble itself in that case is "vacuum", ie it is not air, but absence of water.

Again, much better analogy for this problem , if we wanted to consider only gravity without multitudes of other influences, would be to imagine universe filled homogeneously with neutrons, and bubbles as empty spherical area (vacuum). Alternative would be universe filled with some neutral molecule

In such setup we would really have gravity as predominant force, or at least much-much longer than with water case. Even with neutrons gravity could be surpassed by nuclear forces at some point, but that would be long after bubbles expanded, neutrons stopped being homogeneous and grouped into constellations, where some would be dynamic (ie moving), and kinetic energy will start overriding gravitational behavior, while other will be static and gravity of neutrons will pull together until nuclear forces become evident, and afterward even pass that to black holes and similar stuff.

But in water universe scenario, we would almost immediately have forces stronger than gravity, and any solution using gravity as explanation would be probably wrong.

In such "neutron universe" scenario, as long as whole universe is homogeneously filled there would be cancellation of gravitational pull on any neutron in such "soup", and in theory things should be static. But as soon as you introduce one bubble (as absence of neutrons in spherical area, imagine they just "evaporated"), balance would be broken and result would be anything but static ;p

As I was describing in previous post - gravitational force of neutrons outside bubble would be harder than force of neutrons on far side of bubble , and neutrons on edge would be pulled even further from center , and then even further.... aside from widening up bubble, there would be introduction of kinetic energy.

If more than one bubble would be there, it would result in currents of neutrons, joining of such bubbles, forming irregular shaped ones, until eventually universe would stop being homogeneous and become similar to what we have now - groups of matter(neutrons), with different movement/kinetic energies, and wide areas of vacuum.

Note that neutrons may not be ideal "filler" for this theoretical universe, since while for molecules we can say with more accuracy that they are "static", or "move away/toward", neutrons would exhibit more quantum movement (ie all around volume of probability).

Other alternative would be to imagine universe filled with some neutral gas, or other molecule which does not exhibit electrical/chemical behavior. All of my predictions from above (bubbles extracting, universe being broken from static state to very dynamic even with one bubble) would probably hold in that case too.

[lostdummy]

I wonder if it would be feasible to make simulator of large number of "particles", remove number of particles to form few bubbles, and observe what would happen ;p

But it seems not easy to do - in order to make any meaningful simulation (simulating attraction from far-away parts of universe), we would need large number of particles. And even if we consider only 1000 particles in one direction, that would be 1000^3 = billion of them in simulation of volume of space. Every single move step would need to calculate how every particle influence every other, which is (1000^3)^2 calculations. And we would need very small dT (time steps), at least in start where equilibrium exists, so millions of simulation steps would be needed to simulate any meaningful time span. That is 10^6*(1000^3)^2 ~ 10^24

So even if we manage that one calculation lasts only 100 CPU cycles, that would be with fastest CPUs around (lets say 4GHz), it would take about 1e26/4e9 sec ~ 800,000 millenniums.

No wonder that simulations nowdays usually include only dozens of particles. Anyway, if i think up of some optimization tricks for above, I may try it - but so far it does not look promising ;p

[Zag]

There are some vastly simplifying assumptions you can make. When considering the effects of particle A, for every particle B, if there is a perfectly symmetrical particle B', you can ignore them both. Since we are assuming an infinite universe filled with particles, except for the small number of bubbles, you only need to calculate the effects of the particles that are symmetrically opposite from the ones that are "missing" due to the bubbles.

[lostdummy]

or simplify it even more, and consider each part of space where particle is absent as having negative gravitational influence on other particles (ie, repelling them instead of attracting).

but both simplifications have one drawback - what is really considered as "ones that are missing" in your case, or "particle is absent" in my case?

Problem is that , as soon as symmetry is broken, all nearby particles will start moving - those farther away only slowly, but as soon as it move even a little, did it created "missing" one? How far need particle move for volume of space to be considered to miss particle?

Also, "homogeneously filled with particles" does not necessarily mean particles are next to each other. More realistically is that distance between particles would be many times larger than diameter of particle. Lets say its distance=100x diameter. Now, if somewhere nearby there is bubble and forces moved a bit one particle, it did not create "missing" volume. It could have just moved a bit, so for example its now 99 diameters from one neighbor and 101 from other, instead 100/100.

We could of course treat each volume of space sized same as particle as either having particle or missing one, but in above case that would result in simulation working with (1000x100)^3 elements, instead just with 1000^3.

[lostdummy]

ok, I did make simulation after all.

I made some zillion time optimization, mainly by reducing problem by half-zillion times It means following:

1) I reduced problem space from 3D to 2D - it is not only smaller by orders of magnitude, it also have advantages that it is easier to visualize/show, and most importantly, it still retain all behavior as 3D model. It is similar to situation where we introduced bubbles in 3D in such way that all bubbles had center on same plane, and if we look only at what happens on that plane. Anyway, that reduce from (1000^3)^2 (~ 1e18) to some (1000^2)^2 ( ~12), or some million times reduction

2) I reduced problem space from 1000 particles in one dimension to 100 particles in one dimension. It still consists of 10,000 particles (100x100), which is large enough sample to show behavior. After this, I had ~1e8, or 10 billion times reduction compared to initial.

3) of course, in all previous cases, I ignored need to calculate effect of all other (infinite) particles outside my grid of 1000^3 (or 100^2). I solved that by precalculating it based on initially missing particles.

End result is this program:

Particles.rar

it is written in C#, in order to draw some graphics, and it has only 6k zipped. Requirement is .NET 2.0. BTW, download just by rightclick/saveAs may get you partial file, so open in new tab/window and click on small "click here" to download.

If you start it, and just press "Simulate" (without changing parameters), it will take about half minute (on my notebook) to display how particles will move, with 3 bubbles introduced (two large and one small).

Result is similar to what I predicted in previous posts - bubbles will not so much attract each other, as they will inflate. After some time, all particles will leave simulation grid (after bubbles inflated enough). Interestingly, last particles to leave would be those at boundary between two big bubbles, which is not exactly along "attraction" predictions, but is not so surprising in hindsight, because those particles symmetrically between two bubbles are ones under least gravitational influence since bubbles cancel each other.

If I have time, I may expand simulation to use GPU, in order to support more particles, but even with 100x100 you can hardly distinguish between two particles on screen so it is fine-grained enough to indicate behavior.

[L'lanmal]

Original question, for the record:

Consider hands with no Aces. Equivilently, imagine removing all aces from the deck before drawing your hand. There are 48 cards remaining in the deck, 12 in each suit.

Possible hands: 48 Choose 5.
Hands with a flush: 12 choose 5 * 4.
Prob(flush) = (12 C 5)*4/ (48 C 5).

If this is greater than the original probability of a flush (13 C 5) * 4 / (54 C 5), then the probability of cards containing at least one ace being a flush must be higher. (The "Lake Woobegone Principle": Not everything can be above average.) Since most terms cancel, this should be a reasonably easy calculation.

Conceptually, you can see that if you removed all but 2/3/4/5/6s from your deck, it would be very difficult to make a flush (4 ways), and if you removed all but 2/3/4/5s from your deck, it would be impossible to make a flush, but other non-flush hands are possible.

[lostdummy]

Related to my last post, I finally found time to upgrade a bit my initial "particle simulator". It didn't change answer to original question (inflating bubbles), but its much nicer to play with, so if anyone want to try :

particles2.rar

Some things that I was playing with:
- CUDA: now it can both use CPU or GPU (Nvidia CUDA) , where GPU is about 30x faster for large number of particles (like 10000 in 100x100).
- D3D: in addition to standard drawing, it can visualize simulation by using D3D to draw. Unlike CUDA, work on both Nvidia and ATI, speedup x100. Also added option to show speed vectors
- Collision: can detect collisions of particles and combine them into larger ones
- Presets: several predefined "situations", with or without infinite universe grid
- Custom setup: possibility to set your own particles, grids or bubbles, and play with gravity
- Some other stuff, like zoom in/out, speed up/down , coloring and different density of particles, in addition to different types (groups of particles or solid big objects) ...

Anyway, I had fun playing with both making simulator, and using it to try and setup for example planets orbiting each other, comets, interaction of large groups of particles (like in Preset #2) etc

What I wonder is if 3 files included in above rar(exe,dll,cubin) are enough to run program even on PCs that did not have CUDA installed previously. So I would appreciate comment here if anyone tried it ;p

[Griffin]

lostdummy -- the program is amazingly awesome. I wasted like two hours trying all sorts of different scenarios, although I've always had a soft spot for physics simulators.

I did have to reinstall my video card drivers to get ones with cuda before the cuda worked.

[lostdummy]

Thanks Griffin ;p

Its good to know that it is not needed to install anything beside normal drivers for it to work. It is also good to know that I'm not only one who like to play with physics simulations ;)

[Zag]

Here is another of my favorites from Braingle:

[Zag]

No takers, eh? What if every bag has only 3 jelly beans, and only 4 guests at my party? [4 combos: (0,3) (1,2) (2,1) (3,0).] Now what if every bag has 4 jelly beans, for 5 guests?

[Trojan Horse]

Well now. That heavily implies that the answer to the original problem is 1/2. No time to work out the details now, but we'll see what I can do tomorrow. (There must be some elegant proof.)

[Zahariel]

The answer is definitely 1/2, no matter how many guests are at the party. More generally, if we ask what the probability is that the first k jellybeans chosen by a random guest are the same color, the answer is always 2/(k+1) as long as there are at least k+1 people at the party.

Proof follows:

Name the guests 0 to n where guest i has i red jellybeans.
P(1st k same color with n guests)
= 1/(n+1) sum{i = 0 to n} P(guest i gets k same color)
= 1/(n+1) sum{i = 0 to n} [(iCk + (n-i)Ck)/nCk]
= 1/[(n+1) (nCk)] sum{i = 0 to n} (iCk + (n-i)Ck)
= 2/[(n+1) (nCk)] sum{i = 0 to n} (iCk)
= 2/[(k+1) (n+1)C(k+1)] (n+1)C(k+1)
= 2/(k+1) (assuming n >= k)

where the removal of the sum is by the hockey-stick identity, sum{i = 0 to n} iCk = (n+1)C(k+1); and (n+1)(nCk) = (n+1)! / (k!(n-k)!) = (k+1) ((n+1)C(k+1)) by definition.


I feel like there should be an easier combinatorial proof, but it's not coming to me.

Edit: even more generally, the probability of a random guest selecting j red jellybeans and k black with her first (j+k) draws is 1/(j+k+1). The given problem is just the sum of two special cases of this general problem. The proof is essentially identical except it uses the generalized hockey-stick identity, sum{i = 0 to n} (iCj)((n-i)Ck) = (n+1)(j+k+1). I'm thinking there must be a correspondence argument that groups the possible outcomes of some guest drawing (j+k) jellybeans into sets that contain exactly 1 of each possible distribution. But I can't come up with it.

[Zag]

Here is the answer that the original author wrote. I believe it works out the same as yours.

[Trojan Horse]

Congrats, Zahariel. I never would've thought to generalize the problem as far as you did. I'm impressed.

[Trojan Horse]

Looking for a correspondence argument, Zahariel? I think I found one. Here it is. (I'm not going to spoiler it though.)



To make things easier to picture, I'm going to make the numbers smaller (though the argument works in every case). Say we have 11 guests, 10 candies in each bag, and a random guest is going to pull out 3 candies.

First, number the bags from 0 to 10, according to the number of red candies in the bag. For example; the #3 bag has 3 red and 7 black.

Next, number the candies in each bag. Each candy gets a number from 0 to 10; the reds get numbers that are smaller than the bag number, and the blacks get numbers larger than the bag number. For example: in the #3 bag, the reds get numbers 0, 1, and 2; the blacks get numbers 4 through 10. In the #8 bag, we have 8 reds (which get numbers 0 through 7) and 2 blacks (which get numbers 9 and 10).

So, each bag has all the numbers from 0 to 10 exactly once; one number on the bag, and the rest on the candies.



Now, pick 4 different numbers at random from 0 to 10. The first number represents the bag we pick; the rest represent the candies we take from that bag. (Example: the four numbers are 5, 7, 8, and 3. We take the candies numbered 3, 7, and 8 from bag #5; we get 1 red and 2 blacks.)

We have the following possible outcomes:

1st number is the smallest of the 4: we get 3 black candies.
1st number is 2nd smallest: we get 1 red and 2 black (as in my example)
1st number is 3rd smallest: we get 2 red and 1 black
1st number is the largest: we get 3 red.

All four possibilities are equally likely; the 1st number is just as likely to be the smallest as the 2nd smallest, or the 3rd smallest, or the largest. So each possible combination of candies has a 1/4 chance of occurring.



Same reasoning works in general. If we have n+1 bags with n candies in each, and we take m candies out of a random bag, each possible outcome has an equal 1/(m+1) probability.

Does that make sense?

[Griffin]

I like it!

[Zahariel]

TH wins! I came up with something that was essentially equivalent to that but the numbering was all terrible because I didn't think of skipping the bag's number, so it wasn't at all easy to state. Very well done and it makes my last result really obvious (as a good combinatorial proof should).

This correspondence illustrates the identity I used earlier: (n+1)(nCk) = ((n+1)C(k+1))(k+1). Both of these expressions are the total number of outcomes possible from some guest choosing k candies from his bag of n. The first chooses a guest in one of n+1 ways, and then that guest chooses candies; the second chooses k+1 of TH's numbers from 0 to n and then interprets them in one of k+1 ways. Conveniently the k+1 interpretations are exactly what I was looking for in a correspondence.

I dislike Braingle's answer because they provide no proof for the closed form of that summation and it's not at all obvious or well-known. I suppose at least some people would find it obvious because it's a falling sequential product X ³ = X!/(X-3)!. Falling sequential products are neat because they treat summation and the "forward difference" operator the same way ordinary exponents treat symbolic integration and differentiation; thus, the sum for X from 0 to N+1-1 of X ³ is (1/4)(N+1) ⁴ just like the integral dX from 0 to N+1 of X ³ would be (1/4) (N+1) ⁴ .

[Zag]