

dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted May 12, 2009 09:08 AM 


Expected Time to cover a complete graph Kn
I think this problem might shed some light to the whole discussion and it has a very interesting solution in the end (I am talking about the final formula here).
[Sorry Zamfir and Corribus. I promise I'll come back to yours soon.]
Problem: You are given a complete graph with N vertices*. You start from one vertex, and every time you roll a (N1) die to decide which of the (N1) neighboring vertices you are visiting next. What is the expected number of steps to visit all vertices at least once?
*: A complete graph with N vertices for those who do not know is the following. Place N points in the plane and connect every vertex with all others by a line (one line between each pair). For example, a complete graph with 3 vertices is a triangle. So, as a special case you can play with the following problem.
Draw a triangle, and pick a starting vertex at random. Then toss a coin each time, and if the outcome is Heads move clockwise; if the outcome is Tails move counterclockwise. The problem asks how many times (on average) you have to toss a fair coin so that you visit all vertices.
____________
The empty set


Corribus
Hero of Order
The Abyss Staring Back at You

posted May 12, 2009 03:14 PM 


No problem, dimis. I think I lost the paper where I had written down the answer to mine, anway.
____________
I'm sick of following my dreams. I'm just going to ask them where they're goin', and hook up with them later. Mitch Hedberg


TheDeath
Responsible
Undefeatable Hero
with serious business

posted May 12, 2009 11:08 PM 


@dimis: Thanks a lot for the explanation man, don't worry about detailing the fair coin thing, it makes perfect sense
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.


TheDeath
Responsible
Undefeatable Hero
with serious business

posted May 14, 2009 11:41 PM 

Edited by TheDeath at 23:42, 14 May 2009.

Here's a relatively simple problem that I stumbled across in an idea for a project algorithm, and obviously had to solve it (I hope some others may be interested in since it's not as hard as before).
Basically I thought about making up a "fair system" of random, one which averages out way quicker than infinity (normal "ideal" random only averages out when taking a 'window' of infinity, see below for 'window' definition). This helps two things, especially in algorithms which use pseudorandom generators which have to be fast and thus may not distribute it equally normally. This avoids such weaknesses without sacrificing speed and CPU power.
This problem I present here will only get down to the first, easier part of the process  the latter, constructing the actual random window based on the pseudorandom seed is not covered.
Basically, let me first define the goals. The goal here is to have a 'window'  which is the number of consecutive "coin tosses" (let's call it that way!) we average out. In one such window, the average of the number of true/false (heads/tails if you prefer) must be defined exactly by the probability specified  i.e if probability is 50% for heads, 50% for tails, then half of the throws in such window must be heads, and half tails.
The "size" of this window depends on the chances. A chance of 50% each must be made of a window of 2 "tosses", or any multiple of this (to make it more natural). If it's not a multiple of 1/chance (chance being 0...1 without being 0 of course  you'll need an infinite window for that) then it's simply IMPOSSIBLE for the average over such window to.
To illustrate, consider a window of size 3. Let's say with 1s and 0s, like this:
000
this means 100% on average for 0. Now please arrange them however you want to arrive at 50% 0 and 50% 1, if you can. Which is impossible.
010
will be aprox. 66% 0 and 33% 0. This is why the window must be a multiple of 1/chance. If chance is 1/2 (0.5, like above), then 1/0.5 means 2.
To make this easier, chance will represent from now on the reciprocal of a chance. I.e 50% means 2, 20% is 5, etc... (reciprocal of 1/2, 1/5).
To make it general purpose, we will also use a window size multiplier, w, to multiply our window size. This, however, will be considered a constant  it is there just to be able to change it easy in the final formula (which you'll have to find out ).
Let's define some variables:
c = 1/chance (i.e the reciprocal of a chance, for example, 1/(1/2) or 1/(1/5), etc... which means 2 and 5 respectively)
w = window size multiplier (multiplier of the boundary of a window, which is 'c').
What we actually want right now is, given a window of size c*w (multiplier of 1/chance, explained above why), to find out the number of possible "fair random structure" in such a window. Let us take a few examples. A window multiplier of 1 with two chances, 1/2 and 1/5 respectively:
1/2 chance (c=2): xx
1/5 chance (c=5): xxxxx
What we need is, to fill up those x's with either 1 or 0, such that over the entire window the average will be EXACTLY described by the probability. In the case above, we'll need half of the first one as '1', and 1/5 of the second one as 1, the rest 0s. Let's fill them with an example:
10
10000
we can also place them like this:
01
00100
or
01
01000
same thing on average. This is 100% fair on average if the game lasts for a multiple of this. Actually as you can see, we can always place only one 1 in every window  in fact, we can actually place w number of 1s over the entire window, if we use a multiplier. Let's use w=2 to make this "more natural":
xxxx
xxxxxxxxxx
with this we have much more choices since we can place two 1s anywhere:
1100
0101000000
or
0101
0000100010
or whatever. With this we can be assured that our pseudorandom generator will only generate a sequences for the window, and then it will all be fair without blaming a "poor" PRNG like people do in let's say, Nival's case with Heroes 5 on luck (and I don't blame them).
Anyway, what we're interested for the moment is to give a range to the random seed. And to do that, we'll need the number of possible sequences as mentioned above. In the former case, we can clearly see that there are only 6 such possible sequences from intuition:
1100
1010
1001
0110
0101
0011
In other words, if '1' represents a lucky strike a la Heroes (this is a heroes board so I think everyone is familiar), if we measure as per 4 shots, we will see that a 50% lucky chance will be 100% fair.
However now here is the problem: find the NUMBER of possible sequences given a reciprocal chance c, and a window multiplier w. (i.e give me the formula)
Please note that I ask for a simple, optimized formula. This means it should have very few multiplications, as few as possible (divisions are out of the question, they're much slower to compute which is a considerable factor in computer programming).
Also PLEASE NOTE that 'w' is treated as a constant, so operations on it do not count as an extra operation or multiplication or division. w is just there for our convenience when we'll decide which multiplier to use, as such, operations on it result in CONSTANTS. For example, 1/w is a constant and doesn't count as a division. Neither does 2*x count as a multiplication, etc...
Operations on c however, are not constant since c changes with the chance. By the way any operation on w can be precomputed so really, do NOT count those towards your result number of operations. Of course my algorithm actually is supposed to scale w based on c but that will make your job harder which I do not intend to do, ok?
I do not ask you to give me an algorithm to "fill" those sequences randomly, that would be more complicated and I do not want to overcomplicate your job.
In case it matters, my formula, given the information above (about what is a constant and what is not) only requires the following number of arithmetical operations (depending on w):
w multiplications
w1 additions
(addition also can mean subtraction, or rather addition of negative value).
e.g: for w=5 it would require 5 multiplications and 4 additions.
PS: a raise to power is considered many multiplications (as obviously also is factorial) and division is very slow, it should not have any division on c but just constants (or on w).
You don't have to use math symbols for the answer, intuitively is perfectly fine too if you feel comfortable
For those interested (dimis maybe?) I have also written a powerful script for PARI/gp which takes any polynomial and factors it better than "Horner's Rule" because it results in much better parallelism while having the same number of multiplications (and sometimes even 1 multiplication less, if there's no leading constant). It factors it around the polynomial roots completely automatically, let me know if you're interested. (I have to warn you, it's not a pretty and simple sight to look at ).
The actual algorithm is like this (sorry, only briefly described): First see if you are still in a window, simply look at the next position in the sequence and take the random output from there. If you are out, then you'll have to "generate" a new one with random structures.
With this in mind, if the 'game' lasts a multiple of window size number of coin tosses, then it can be GUARANTEED to be 'fair' or 'average' over that amount. If it doesn't, well, it's just the nature of random.
I hope you can see how this can actually make the game fair on a lot smaller multipliers than the theoretical infinity which is needed in a theoretical ideal random number generator. A pseudorandom number generator used in computers is even worse because it can be poorly made to not reflect everything uniformly. You can make a better one but that usually requires more computing resources for computing it, not a very attractive idea.
Have fun!
DISCLAIMER: When I solved this, I relied much more on intuition and logic than on math skills, which is why it took a small time without any rigorous proofs, I think it took almost twice as much writing this whole thing with my fast typing skills lol.
Anyway I owe this to my ability to spot patterns in numbers and sequences, which for some reason I can connect them easily (one of the reasons I like these problems in IQ tests and probably the reason I score high since most IQ tests have most questions of this type )
suffice to say I'm much more a programmer than a mathematician
I hope this has been an intuitive description, because I am one of the few who actually understands some "advanced" (as far as noobs are concerned) math problems but still hates the way it is presented, with too many symbols and not enough visualization. I hope this attracts more people, it surely would attract me
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted May 15, 2009 09:40 PM 

Edited by dimis at 01:25, 16 May 2009.

Problems that were left unanswered
Ok, the problems that were left unanswered so far, since this will get out of hand soon.
Thanks for the problem Zamfir. It was very interesting on working out the details.
Corribus problem on slicing a cube:
Quote: John takes a wooden cube of a certain size and paints it blue. Then, using a saw, he cuts the cube into an exact number of smaller cubes all measuring exactly 1 cm in dimension. He then sorts the small cubes by the number of faces that are painted blue. He finds that there are precisely twice the number of cubes with no blue faces as there are cubes with 1 blue face. What was the size of the original cube?
As stated earlier, the number of cubes that are unpainted is (N2)^3, since they all belong in a (N2)x(N2)x(N2) cube.
Now, the number of cubes that are painted with just 1 color, are 6(N2)^2, since on each face of the cube we have a square of size (N2)x(N2) which contains the cubes that have only one face painted (the square in the interior of each face), and there are 6 faces (hence the multiplication by 6).
So, what we want is
2 ( 6(N2)^2 ) = (N2)^3
<==> (N2)^2 ( (N2)  12 ) = 0
<==> (N2)^2(N14) = 0
So, we have the "natural" solution N=14; i.e. a 14x14x14 cube, as well as, a 2x2x2 cube, since this in such a cube all smaller cubes have 3 faces painted, and as a consequence, the number of unpainted smaller cubes is two times the number of smaller cubes that are painted by just one color trivially, since they are both zero.
There was also another problem after that:
Quote: Suppose you take a cube with dimension exactly n cm along the side and paint 2 sides red and 4 sides blue. You then saw it up as described in the above problem into 1 cm cubes. How many of the resulting smaller cubes will have at least one red face but no blue faces, in terms of n? (hint: there are actually two possible answers).
Again, the big cube is assumed to be NxNxN.
First note, that by looking at a face of such a cube, you observe NxN = N^2 smaller cubes.
We distinguish cases based on whether or not the two red faces of the bigger cube are adjacent.
2 red faces are in opposite sides
In this case, whenever, you look at a red face of the big cube, all smaller cubes that are on the boundary, have at least one blue face. Hence, the number of smaller red cubes with no blue face is (N2)x(N2) = (N2)^2
So, the result in this case is:
2(N2)^2.
2 red faces are adjacent
The observations are similar like before, however, this time, we gain a region of (N2) smaller cubes which lie on the boundary between the two faces of the bigger cube, and hence, the number is
2(N2)^2 + (N2) = 2N^2  7N + 6.
Another easy way of figuring this out is by stretching both red faces of the big cube, which creates a grid with dimensions Nx(2N1) and not Nx(2N) since one column/row of squares is "shared" between the two big red faces, and we are interested in the number of small squares in the interior. All of them are contained in a rectangle of dimension (N2)x(2N3) = 2N^2  7N + 6
Hint on Cover time of a complete graph Kn:
I remind you the problem:
Quote: Problem: You are given a complete graph with N vertices*. You start from one vertex, and every time you roll a (N1) die to decide which of the (N1) neighboring vertices you are visiting next. What is the expected number of steps to visit all vertices at least once?
If a coin succeeds with probability p, then it is expected that we have to toss the coin 1/p times in order to obtain one (the first time) success.
Death's Problem:
You are given a sequence of 0's and 1's, of size "c*w", and the sequence contains "w" 1's. "c" and "w" are (presumably on Death's description), positive integers. So, the question becomes:
How many different sequences of this form can we make? For that we need a formula.
And there is a second question: What is the fastest way of computing the end result? I suggest we skip this, as well as some other points that are made throughout that post, mainly because the discussion is about math and not about programming.
I will not be around during the weekend.
____________
The empty set


DagothGares
Responsible
Undefeatable Hero
No gods or kings

posted May 15, 2009 09:43 PM 


Okay, I have six groups:
Group A, group B, group C, group D, group E and Group F ( can be renamed groups 16, if you like)
They're volleyball teams. Now, I'll have to make them play so that each of them has played against another team without any repeating (so if graoup a played against group b, I don't want to see that combination again). All teams have to play during one turn and I want to do this four turns. I want to know whether it's possible or not and I would like an explanation.
____________
If you have any more questions, go to Dagoth Cares.


mamgaeater
Legendary Hero
Shroud, Flying, Trample, Haste

posted May 15, 2009 10:51 PM 


four turns as in the teams play a total of 4 times against another team?
____________
Protection From Everything.
dota


DagothGares
Responsible
Undefeatable Hero
No gods or kings

posted May 15, 2009 10:58 PM 


Yes
____________
If you have any more questions, go to Dagoth Cares.


mamgaeater
Legendary Hero
Shroud, Flying, Trample, Haste

posted May 15, 2009 11:05 PM 


Assuming that each team only plays 1 game a turn. and that you want to know if each team can play each other team at least once in 4 turns.
Possible combinations
Lets see
Let each group be group AF
There are 6 groups so our combinations are.
(N/2)*(n1)
Where N is 6.
(6/2)*(61)
3*5
15 combinations.
A,B
A,C
A,D
A,E
A,F
B,C
B,D
B,E
B,F
C,D
C,E
C,F
D,E
D,F
E,F
For four turns that means that a total of 12 combinations(matchups) can occur.
No,
One more turn would be nessesary for each team to have played against each other team at least once.
____________
Protection From Everything.
dota


DagothGares
Responsible
Undefeatable Hero
No gods or kings

posted May 15, 2009 11:11 PM 


Alright, thanks
____________
If you have any more questions, go to Dagoth Cares.


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted May 15, 2009 11:22 PM 

Edited by dimis at 23:23, 15 May 2009.

Funny thing because I understood an entirely different thing when I read:Quote: They're volleyball teams. Now, I'll have to make them play so that each of them has played against another team without any repeating (so if graoup a played against group b, I don't want to see that combination again). All teams have to play during one turn and I want to do this four turns. I want to know whether it's possible or not and I would like an explanation.
Clearly one team has one opponent on each round, so in four rounds each team can face at most 4 different opponents, and since there are 5 opponents for each team, it is straightforward that you can not create a "pool" tournament (i.e. everybody plays against everybody) with just 4 (<5) rounds.
So, my interpretation was: "Give me a sequence of matches for the first 4 rounds of the tournament, if that is possible, otherwise prove that it is impossible".
And here we are:
Round 1: (1,2), (3,4), (5,6)
Round 2: (1,3), (2,5), (4,6)
Round 3: (1,4), (2,6), (3,5)
Round 4: (1,5), (2,4), (3,6)

and the last round can be:
Round 5: (1,6), (2,3), (4,5)
____________
The empty set


DagothGares
Responsible
Undefeatable Hero
No gods or kings

posted May 15, 2009 11:23 PM 


Holy cow, you solved it!
____________
If you have any more questions, go to Dagoth Cares.


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted May 15, 2009 11:25 PM 


LOL, so what was your question?
____________
The empty set


DagothGares
Responsible
Undefeatable Hero
No gods or kings

posted May 15, 2009 11:34 PM 


No, that was the question.
We were sitting there and were like (even two teachers were helping us trying to do it): Okay...
we always came with three combinations and the last one always failed, because we were left with a five and a six the for the fourth round.
____________
If you have any more questions, go to Dagoth Cares.


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted May 16, 2009 12:03 AM 

Edited by dimis at 00:17, 16 May 2009.

Actually, when I created the solution I used a grid (redrawn with many colors this time) to verify that the combinations I made by hand were legitimate:
Try filling in a new grid like I did above. Use different colors for different rounds. It will be straightforward then.


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted May 16, 2009 01:07 AM 


I updated the post with the solution on Zamfir's problem. It was really ugly in plain text.
____________
The empty set


TheDeath
Responsible
Undefeatable Hero
with serious business

posted May 16, 2009 03:17 AM 


Quote: And there is a second question: What is the fastest way of computing the end result? I suggest we skip this, as well as some other points that are made throughout that post, mainly because the discussion is about math and not about programming.
Yes but actually I meant the fewest number of operations. Surely math is concerned with factoring and simplifications, right? Well at least it's how I thought (there's nothing "programming" about it, just fewest operations), sorry for that then. Without that the problem is very easy, but I'm not sure for others though.
____________
The above post is subject to SIRIOUSness.
No jokes were harmed during the making of this signature.


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted May 16, 2009 06:34 AM 

Edited by dimis at 08:26, 16 May 2009.

Matchings
To be honest Dagoth, the idea with the table above has its roots on what is socalled a graph ( = a bunch of vertices in the plane, and lines connecting the vertices).
So, in your problem, you are looking for different matchings, like in the following picture:
A matching is what you do on each round in your problem: find edges that connect vertices, so that each vertex belongs to precisely one edge. So, the different colors above, indicate the matchings in the graph, and hence represent the pairs on each round of the tourney. Here we were allowed to create the graph, and we wanted to find 5 different matchings.
Anyway, our building blocks for the solution found above, were:
Hence, by rotating them (e.g. clockwise), we can obtain more solutions:
and
This is not a coincidence, but let's stop here. I hope the pictures help on the intuition.
____________
The empty set


Ecoris
Promising
Supreme Hero

posted May 16, 2009 01:59 PM 


The expected number of steps needed to visit all N vertices of a complete Ngraph is (N1) + (N1)/2 + (N1)/3 + ... + (N1)/(N2) + 1.
____________


alcibiades
Honorable
Undefeatable Hero
of Gold Dragons

posted May 16, 2009 03:17 PM 


Here's a little task if you're bored.
We know from previous discussion that the following statement is true:
1.(9) = 1.999999999999... = 2
Now, explain how the following sentence can be said to be true from a similar argument:
1.(1) = 1.111111111111... = 10
Note: This may not be on the correct side of the finer rules of mathematics, but was none the less a funny little thought I had in the shower yesterday.
____________
What will happen now?



