Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 14 15 [16] 17 18 ... 47  All

Author Topic: Maths thread.  (Read 307361 times)

0 Members and 3 Guests are viewing this topic.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #375 on: May 16, 2015, 05:49:36 pm »
0

Here's a problem that I don't know the answer to. I'm trying to solve a problem, and I computed the values for n = 1 to n = 10, then my program starts taking a long time to execute. Listed below are those 10 values. The first one is sort of shaky depending on definition I think, you could make a case for it being 0 instead. They should grow as n!, there may be combinatorial elements to the solution, and I believe that in general it will "grow more" when going from odd n to even n then from even n to odd n. Any idea what the general value is for n?

(1)
1
1
2
4
18
54
471
2246
25989

I can also just post the actual problem if people would rather have that. EDIT: Posted, and my program finally finished for n = 10.
« Last Edit: May 16, 2015, 06:33:12 pm by liopoil »
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Maths thread.
« Reply #376 on: May 16, 2015, 05:52:38 pm »
0

I don't understand, what is it that you have to do?
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #377 on: May 16, 2015, 05:56:38 pm »
0

I don't understand, what is it that you have to do?
Find the pattern!
Logged

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2210
  • Respect: +2854
    • View Profile
Re: Maths thread.
« Reply #378 on: May 16, 2015, 06:00:21 pm »
+3

Well, OEIS doesn't report anything, so it obviously has no pattern. OEIS knows all.

You should probably just post the problem, there's no guarantee a pattern exists at all and your question is too vague to answer.
Logged
I have a blog! It's called Sorta Insightful. Check it out?

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #379 on: May 16, 2015, 06:05:36 pm »
0

Well, I don't know what OEIS is, but okay...

Consider the n vertices of an n-gon. How many distinct ways are there to draw lines connect the dots such that each dot is used in exactly two lines, and there is a path of lines between any given two points (it is a complete cycle), in terms of n? Two dot-connectings are distinct if they cannot be made to look identical by rotation.

The problem wording is my own, so I'll answer any clarifying questions. And Titandrake is right, there might not be a nice pattern.
Logged

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2320
    • View Profile
Re: Maths thread.
« Reply #380 on: May 16, 2015, 06:34:40 pm »
+1

OEIS is the Online Encyclopedia of Integer Sequences is a list of ... integer sequences ... compiled so that if you come across a sequence of numbers in the course of solving a problem you can look it up and see if anyone else has found the same sequence before in some other context.  You can then look for connections between their problem and your own.

Counting your objects exactly is probably hard.  My instinctive guess is that the answer is (n-1)!/2 asymptotically, as I expect that most patterns aren't fixed by any non-trivial rotation.

I think what you're counting is cyclic permutations on n elements modulo the taking of inverses and conjugation by powers of the standard cyclic permutation (1 2 ... n).  Conceivably somebody has counted that before.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #381 on: May 16, 2015, 06:43:55 pm »
0

Well, I'm not sure what "modulo the taking of inverses and conjugation by powers of the standard cyclic permutation" means, but in my program I find all cyclic sequences of n integers with values in the range 1 to n-1 such that no strict subset of consecutive integers in the cycle add up to a multiple of n and the sum of all the integers is not greater than n * floor(n/2). Is this the same?

EDIT: I also noticed that any such cyclic sequence is a juggling pattern!
« Last Edit: May 16, 2015, 06:46:24 pm by liopoil »
Logged

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2320
    • View Profile
Re: Maths thread.
« Reply #382 on: May 16, 2015, 07:09:29 pm »
0

I don't immediately see that that corresponds with the description you gave before (but it might do!).  The first condition is equivalent to the fact that you're looking at cycles.  The second says something like "the cycles does not wrap around more than n/2 times", but I can't see what that has to do with rotations.  Is it maybe something to do with reflections/choosing directions?

Sorry for dropping all that jargon without an explanation.  My intention was to indicate that, since these things have names, it's possible that somebody has looked at them before.  I'll risk making things worse by saying more.  Do feel free to ignore.

Go back to your original picture, label the vertices 1 to n and choose a direction for your cycle arbitrarily.  Your picture now defines a function, where the rule is "follow the cycle to the next element".  This function is in fact a permutation (as different inputs map to different outputs) so lives in the "symmetric group" S_n.  Since you don't care about the direction you chose for your cycle, you don't want to count following the cycle forwards and backwards as distinct.  Since following the cycle backwards corresponds to a function that undoes the first function, you want to count permutations and their "inverses" as the same.

Now rotations.  If you rotate your circuit one position then you get a new function.  If you write down the definition of this function then it's the same as the definition of the old function except that you replace x by x+1 everywhere (mod n).  (Or x-1 depending on the direction you rotate compared to the direction in which you labelled the points originally.)  This corresponds to a group theoretic operation called conjugation.

"Modulo X" just means "ignoring differences of the form X".  This is just like saying 1 = 7 mod 3 -- 1 and 7 are "the same" if you ignore 3.

This translation is unlikely to help you with your problem.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #383 on: May 16, 2015, 07:28:10 pm »
+1

Okay, yes I do think our statements were equivalent. If we have a cycle and its inversion, one of the cycles wraps around more than n/2 times and the other doesn't, so that bit made sure to count each just once. I chose clockwise to be the positive direction, so counted "times going around" as if each line went around the circle clockwise until it got to its destination. Rotations I just checked in my program by making sure each cycle wasn't a rotation of one I already found, by recording all the rotations of a cycle when I found it. I'm sure it was very inefficient, but it works. The xth number in the sequence represents how many dots around from the xth dot in the clockwise direction the dot that the line goes to from the xth dot is.

What if we also ignore reflections? This just makes it even harder, right?
Logged

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2320
    • View Profile
Re: Maths thread.
« Reply #384 on: May 16, 2015, 07:57:45 pm »
0

Okay, yes I do think our statements were equivalent. If we have a cycle and its inversion, one of the cycles wraps around more than n/2 times and the other doesn't, so that bit made sure to count each just once. I chose clockwise to be the positive direction, so counted "times going around" as if each line went around the circle clockwise until it got to its destination. Rotations I just checked in my program by making sure each cycle wasn't a rotation of one I already found, by recording all the rotations of a cycle when I found it.

Ah, I see now: that was just enumerating cycles.  The rotations comes in later.

Quote
What if we also ignore reflections? This just makes it even harder, right?

I don't think it makes it easier.
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #385 on: May 16, 2015, 08:33:00 pm »
+2

I have found a summation which gives the solution for odd numbers (I think).

It is:

(1/n)(Sum of ((d - 1)! / 2)((n / d)^(d - 1))phi(n / d)^2 over all d such that d|n),

where phi(n) is the Euler phi function.

Similar summation for even numbers coming soon, maybe. They are kind of a pain.
Explanation also coming soon, probably. Basically I used Burnside's Lemma and then thought a lot and then decided that even numbers are bad.

Edit: rewrote for clarity, maybe?
Edit2: I think maybe I messed up and this stops working around either n = 15 or n = 27. Not sure yet.
Edit3: Upon further reflection, I am confident that I didn't mess up.
« Last Edit: May 16, 2015, 09:30:22 pm by heron »
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #386 on: May 16, 2015, 08:45:12 pm »
0

I am not sure what you mean by d|n of x, where x is that crazy expression. I understand that the vertical line means "is a divisor of", but how it relates to n of x, since x is just a number... that is strangely in terms of d.
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #387 on: May 16, 2015, 08:58:14 pm »
0

I am not sure what you mean by d|n of x, where x is that crazy expression. I understand that the vertical line means "is a divisor of", but how it relates to n of x, since x is just a number... that is strangely in terms of d.

Oh sorry if that was confusing. I mean that you plug in all of the divisors of n into x, and add up the results. So if we say x = x(d) for a specific d, then for example the formula for 6 is (1/6)(x(1) + x(2) + x(3) + x(6)). Hopefully that clears it up; I don't really know what the proper way to write this is without using summation notation, which is hard to do on the forum.

I made an edit that hopefully is more clear now.
« Last Edit: May 16, 2015, 08:59:50 pm by heron »
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #388 on: May 16, 2015, 09:10:08 pm »
0

Ahh, that makes sense. Okay, I'll test the first few odd n:


1: 0, yeah the problem isn't too well defined for this one.
3: 1/6. Uh....
5: 33/10

Or am I evaluating it wrong?
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #389 on: May 16, 2015, 09:16:36 pm »
0

Ahh, that makes sense. Okay, I'll test the first few odd n:


1: 0, yeah the problem isn't too well defined for this one.
3: 1/6. Uh....
5: 33/10

Or am I evaluating it wrong?

Yea, I think so. For 1 you should be getting (1/1)((1/2)(1^0)(1^2)) = 1/2. (which is weird, but 1 is weird).

For 3 you should get (1/3)((1/2)(3^0)(2^2) + (1)(1^2)(1)) = (1/3)(2 + 1) = 1.

For 5 you should get (1/5)((1/2)(5^0)(4^2) + (12)(1^4)(1)) = (1/5)(8 + 12) = 4.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #390 on: May 16, 2015, 09:37:15 pm »
0

Ahh, I was evaluating phi(1) = 0, phi(3) = 1, phi(5) = 3, because I wasn't counting 1 as relatively prime to 1, 3, and 5 for some reason. Great! Then 7 gives (1/7)((1/2)(7^0)(6^2) + 360(1^6)(1^2)) = 378/7 = 54, and 9 gives (1/9)((1/2)(9^0)(6^2) + 1(3^2)(2^2) + (8!/2)(1^8)(1^2)) = 1/9(18 + 36 + 20160) = 2 + 4 + 2240 = 2246. Hey, they all fit my brute force answers, cool!
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #391 on: May 16, 2015, 09:53:17 pm »
+3

And here is an explanation:

First, read this: http://en.wikipedia.org/wiki/Burnside%27s_lemma
If you don't know all of the terms, that's okay, just read the example application and it will probably make sense. Burnside's lemma is pretty intuitive I think.



Anyway, the (1/n) is because there are n possible rotations. Then, the summation term thing (which was being called x earlier, I will probably continue to do this) is the number of cycles with n/d-symmetry. (for example, a regular hexagon has 1-symmetry, 2-symmetry, 3-symmetry, and 6-symmetry).
A cycle is invariant under a rotation by k/n revolutions if and only if the cycle has gcd(k,n) symmetry. The number of k ≤ n such that gcd(k,n) = d is equal to phi(n/d), which explains one of the phi(n/d) in the summation term.

So, we need to count the number of cycles with d-symmetry. For odd n, this is (((d - 1)! / 2)((n / d)^(d - 1))phi(n / d).
Notice that if the graph has d-symmetry, if vertex a is linked to vertex b, then vertex a + d is linked to vertex a + d + b (where the vertices are labeled in order and the labels are taken modulo n). So, we can divide the vertices into d groups of n/d vertices. If d > 1, then no vertex can be linked to any vertex in its own group, because then its group would just become a cycle by itself (this is the step which is false if n is even).

Now, if a vertex in group A is linked to a vertex in group B, then all of the vertices in group A are linked to a vertex in group B. So, the ways all of the groups are linked form a cycle of their own, which I'll call a group-cycle. Since there are d groups, there are (d - 1)! / 2 possible group cycles.

Now we need to count the number of cycles you can form given a certain group-cycle. Say d = 5 and our group cycle is A to B to C to D to E and back to A. Then, starting with a vertex in group A, we have n/d choices of what vertex to link to in B, then n/d choices for what to link to in C, then n/d choices for what to link to in D, and finally n/d choices for what to link to in E, for (n/d)^(d - 1) total possible choices (so far).

Now, how many ways are there to link back to A? If we link back to the wrong vertex in A, for example if we link back to the vertex we started with, then we will get multiple cycles rather than one big cycle. Label the vertices of group A in order as 0, 1, 2, ... n/d - 1, where 0 is the vertex we started with and the labels are taken modulo n/d. Say the vertex we link back to is vertex m. Then, as we go from vertex m to a vertex in B and then a vertex in C and so on, when we get back to group A again, we will land on vertex 2m. And if we do that again, we will land on 3m, 4m, etc. until we land on 0 again. Now, if m is not relatively prime to n/d, there will be some vertices of A which we never landed on, so we would not have a full cycle. Therefore we must pick a vertex m such that m and n/d are relatively prime; there are phi(n/d) ways to do this.

Multiplying all that stuff together, we get ((d - 1)! / 2)((n / d)^(d - 1))phi(n / d) cycles with d-symmetry.

Finally, the case where d = 1 is pretty straightforward and similar to what we just did. Label the vertices 0, 1, 2, ..., n - 1 and the labels are taken modulo n. If 0 is linked to m, then m is linked to 2m, and so on, until we get back to 0. This will only produce a full cycle if m is relatively prime to n, so there are phi(n) valid choices of m. However, linking 0 to m results in the same cycle as linking 0 to -m, so we actually only have phi(n)/2 choices. Fortunately phi(n)/2 = ((1 - 1)! / 2)((n / 1)^0)phi(n / 1), so we don't need to special case this in our summation.

Now, we just apply Burnside's Lemma to get (1/n)(Sum of ((d - 1)! / 2)((n / d)^(d - 1))phi(n / d)^2 over all d such that d|n)   :D

Since that probably was not clear at all, feel free to ask questions.
Logged

SwitchedFromStarcraft

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1088
  • Respect: +856
    • View Profile
Re: Maths thread.
« Reply #392 on: May 17, 2015, 09:57:49 am »
0

Sometimes I miss being in school.
Logged
Quote from: Donald X.
Posting begets posting.

Quote from: Asper
Donald X made me a design snob.

There is a sucker born every minute.

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #393 on: May 18, 2015, 06:19:22 pm »
+2

Here is a problem:

How can liopoil's problem (or a special case of it anyway) be used to prove Wilson's Theorem?

Wilson's Theorem states that for any odd prime p, (p - 1)! = -1 (mod p).
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #394 on: May 18, 2015, 06:29:40 pm »
0

WOAAHH my problem is way more interesting than I expected. Will think about this soon... I've read your solution, understood like the first half and just need to spend a bit more time to work through the rest. One quick question though, how are you forming these groups? If that's specific enough of a question...
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #395 on: May 18, 2015, 06:33:52 pm »
0

WOAAHH my problem is way more interesting than I expected. Will think about this soon... I've read your solution, understood like the first half and just need to spend a bit more time to work through the rest. One quick question though, how are you forming these groups? If that's specific enough of a question...

Each group just consists of every d-th vertex. I grouped them this way because if the cycle has d-symmetry, then every d-th vertex is doing the same thing, so I can think about them all at once instead of individually.

Edit: btw the Wilson's theorem thing is much easier than your problem imo.
« Last Edit: May 18, 2015, 07:17:57 pm by heron »
Logged

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7096
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9411
    • View Profile
Re: Maths thread.
« Reply #396 on: May 18, 2015, 07:57:33 pm »
0

Here is a problem:

How can liopoil's problem (or a special case of it anyway) be used to prove Wilson's Theorem?

Wilson's Theorem states that for any odd prime p, (p - 1)! = -1 (mod p).

Isn't this also true for 2?
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #397 on: May 18, 2015, 08:03:35 pm »
0

Here is a problem:

How can liopoil's problem (or a special case of it anyway) be used to prove Wilson's Theorem?

Wilson's Theorem states that for any odd prime p, (p - 1)! = -1 (mod p).

Isn't this also true for 2?
Yes well that's not what the theorem states apparently :P
Logged

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2210
  • Respect: +2854
    • View Profile
Re: Maths thread.
« Reply #398 on: May 18, 2015, 11:00:24 pm »
0

heron, is the idea you're thinking of the last proof in the Wikipedia page for Wilson's Theorem, using Sylow theorems?
Logged
I have a blog! It's called Sorta Insightful. Check it out?

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #399 on: May 18, 2015, 11:37:25 pm »
0

heron, is the idea you're thinking of the last proof in the Wikipedia page for Wilson's Theorem, using Sylow theorems?

Well, I was thinking of something much more elementary. I don't actually know group theory, I just basically just know Burnside's Lemma and the Orbit-Stabilizer Theorem.
But I tried to read the wikipedia stuff about that, and I think I understood most of it. The basic idea is the same I think, and the first steps of that proof are identical to the proof I am thinking of. However, the finish is different. If I understood the proof of Sylow theorems then maybe I would be able to tell if it is essentially the same proof or not.

Anyway, the proof I am thinking of relies on nothing other than counting stars. (mild hint spoilered)
Logged
Pages: 1 ... 14 15 [16] 17 18 ... 47  All
 

Page created in 0.184 seconds with 21 queries.