Heroes of Might and Magic Community
visiting hero! Register | Today's Posts | Games | Search! | FAQ/Rules | AvatarList | MemberList | Profile


Age of Heroes Headlines:  
5 Oct 2016: Heroes VII development comes to an end.. - read more
6 Aug 2016: Troubled Heroes VII Expansion Release - read more
26 Apr 2016: Heroes VII XPack - Trial by Fire - Coming out in June! - read more
17 Apr 2016: Global Alternative Creatures MOD for H7 after 1.8 Patch! - read more
7 Mar 2016: Romero launches a Piano Sonata Album Kickstarter! - read more
19 Feb 2016: Heroes 5.5 RC6, Heroes VII patch 1.7 are out! - read more
13 Jan 2016: Horn of the Abyss 1.4 Available for Download! - read more
17 Dec 2015: Heroes 5.5 update, 1.6 out for H7 - read more
23 Nov 2015: H7 1.4 & 1.5 patches Released - read more
31 Oct 2015: First H7 patches are out, End of DoC development - read more
5 Oct 2016: Heroes VII development comes to an end.. - read more
[X] Remove Ads
LOGIN:     Username:     Password:         [ Register ]
HOMM1: info forum | HOMM2: info forum | HOMM3: info mods forum | HOMM4: info CTG forum | HOMM5: info mods forum | MMH6: wiki forum | MMH7: wiki forum
Heroes Community > Tavern of the Rising Sun > Thread: Let's talk about Maths!!!
Thread: Let's talk about Maths!!! This thread is 55 pages long: 1 10 ... 18 19 20 21 22 ... 30 40 50 55 · «PREV / NEXT»
dimis
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 (N-1) die to decide which of the (N-1) 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

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
Corribus
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

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
TheDeath
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.

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
TheDeath
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 pseudo-random 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 pseudo-random 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 pseudo-random 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
w-1 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 pseudo-random 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.

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
dimis
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 (N-2)^3, since they all belong in a (N-2)x(N-2)x(N-2) cube.
Now, the number of cubes that are painted with just 1 color, are 6(N-2)^2, since on each face of the cube we have a square of size (N-2)x(N-2) 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(N-2)^2 ) = (N-2)^3
<==> (N-2)^2 ( (N-2) - 12 ) = 0
<==> (N-2)^2(N-14) = 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 (N-2)x(N-2) = (N-2)^2
So, the result in this case is:
2(N-2)^2.

2 red faces are adjacent
The observations are similar like before, however, this time, we gain a region of (N-2) smaller cubes which lie on the boundary between the two faces of the bigger cube, and hence, the number is
2(N-2)^2 + (N-2) = 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(2N-1) 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 (N-2)x(2N-3) = 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 (N-1) die to decide which of the (N-1) 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

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
DagothGares
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 1-6, 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.

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
mamgaeater
mamgaeater


Legendary Hero
Shroud, Flying, Trample, Haste
posted May 15, 2009 10:51 PM
Edited by mamgaeater at 22:51, 15 May 2009.

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

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
DagothGares
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.

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
mamgaeater
mamgaeater


Legendary Hero
Shroud, Flying, Trample, Haste
posted May 15, 2009 11:05 PM
Edited by mamgaeater at 23:06, 15 May 2009.

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 A-F

There are 6 groups so our combinations are.

(N/2)*(n-1)

Where N is 6.

(6/2)*(6-1)

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

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
DagothGares
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.

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
dimis
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

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
DagothGares
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.

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
dimis
dimis


Responsible
Supreme Hero
Digitally signed by FoG
posted May 15, 2009 11:25 PM

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

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
DagothGares
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.

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
dimis
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 (re-drawn 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.

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
dimis
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

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
TheDeath
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.

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
dimis
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 so-called 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

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
Ecoris
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 N-graph is (N-1) + (N-1)/2 + (N-1)/3 + ... + (N-1)/(N-2) + 1.
____________

 Send Instant Message | Send E-Mail | View Profile | Quote Reply | Link
alcibiades
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?

 Send Instant Message | Send E-Mail | View Profile | PP | Quote Reply | Link
Jump To: « Prev Thread . . . Next Thread » This thread is 55 pages long: 1 10 ... 18 19 20 21 22 ... 30 40 50 55 · «PREV / NEXT»
Post New Poll    Post New Topic    Post New Reply

Page compiled in 0.1911 seconds