Post by FractalFusion

Posted: 7/24/2018 9:09 PM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

The newest Numberphile video made me think of this hypothesis: Three non-overlapping spheres (not necessarily of the same radius) are on a floor (ie. a plane). As long as the points where the spheres touch the floor are not collinear, there will exist another plane that also touches all three spheres (in such a way that all three spheres will be on the same side of this second plane). Can this be proven?

Posted: 7/24/2018 11:53 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Tub wrote:

Your code got mangled there, but it's easy enough to see the dynamic programming invariant.

Well, the board doesn't like less than and greater than signs. I always have to disable HTML for them to work. In this case, I didn't bother because I thought the code tag would handle that. Guess I was wrong... Since Fractal corrected it, I think it's OK :P In any case, for those who are not familiar with algorithm theory (they are an art far darker than witchcraft), here's how you can write that code. The idea is: suppose you have already decided on a collection of 4 coin values (which in practice are just 3, because 1 must be included), then put these values in ascending order. Suppose you have a function f that takes a number n as an argument, and an index m, and that returns the minimum number of coins used to represent n using only the first m coin values in the set. You can calculate f recursively as follows: f(n,m) = min(f(n,m-1),f(n-v,m)+1), where v is the value of the m-th coin in the set. The relation can be easily understood. If you want to represent n using the set of m coins, you either use the m-th coin or you don't. If you don't, then the m-th coin is useless, and the value is the same as if you represented n using the set of m-1 coins. If you do use the m-th coin, and its value is v, then your task is to represent the number n-v using the same set of coins and add 1 to that result. At the end, the smaller value of these two will win. Now, 0 takes no coins to represent, so f(0,m)=0 for any m, and since no positive number n can be represented from the empty set, f(n,0)=infty. Using this, you can set up a recursion and it will always terminate. The problem is that a simple recursion takes way too long, the running time grows exponentially. That's because the computer is stupid and keeps evaluating values of functions it already calculated. The simplest solution is to cache all results from the functions in an array. That's already a form of dynamic programming (the top-down approach). However, the classic bottom-up approach to dynamic programming is usually much faster, because it has no overhead from recursive calls. You essentially work with the array where you store all the function values and scan them in a given order applying the recursive relation. Sometimes that even saves memory, because after a scan you no longer need the old values. In this problem I could do everything only with an array of 100 integers, but since I had to test lots of combinations, I decided to use 4 arrays to speed up the process reusing each stage.

Posted: 7/25/2018 5:23 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

The following problem is a bit open ended, but I still think it can be considered an exact problem :) It's a bit well known, so if you search it on the internet, you might find the answer. An attack that is very effective against most cryptographic schemes is the meet-in-the-middle attack. When trying to find a key in an encryption scheme, ideally the only way to solve for the key would be to try all possible combinations. If a system is susceptible to an MITM, the search can be done in a value proportional to the square root of the number of all possible combinations, which is much more efficient. The classic example is the subset-sum problem. Naively, if the set has n elements, one tests all 2ⁿ subsets to find the sum. But with a meet-in-the middle strategy, you can do it in 2^n/2. Split the set in half, then place all 2^n/2 sums from the first half in an array A, then the sums from the other half in an array B. By sorting the arrays A and B, you can find whether an element in A and an element in B sum to a given value very efficiently. Another problem that admits a meet-in-the-middle solution is the discrete logarithm problem, where it's called baby-step giant-step. The challenge is to find a similar weakness in a secure random number generator. One popular way to do a secure RNG is to use an n-bit block cipher. If f is the encryption function of the cipher, your random numbers should be f(0), f(1), f(2), f(3), ... That should work well, because if the block cipher is good, its output for any message should look random. It turns out this method is also vulnerable to a meet-in-the-middle strategy, even with an ideal block cipher. So, the problem is: devise a statistical test to determine, after looking at something of the order of 2^n/2 pseudorandom numbers, whether it's much more likely that this stream of numbers came from an n-bit block cipher operating in the previous manner rather than a truly random source.

Posted: 7/25/2018 5:45 PM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

FractalFusion wrote:

Take a plane that goes through the centers of the spheres. If we reflect across this plane, then the spheres remain the same (by symmetry). So the reflection of the floor through the reflection plane gives another plane (the "ceiling") that touches all three spheres.

A corollary of this seems to be that if there are more than three spheres, as long as their centers are coplanar, there will exist another plane that's tangential to all of them. I'm not sure if there should additionally be the requirement that no three floor touch points should be collinear.

Posted: 7/29/2018 1:34 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

This week's Riddler classic puzzle kinda disappointed me, it's a simple Hamiltonian path problem, which can also be solved with dynamic programming. The algorithm is even in the Wikipedia article!

Riddler wrote:

Start with an empty 5-by-5 grid of squares, and choose any square you want as your starting square. The rules for moving through the grid from there are strict: You may move exactly three cells horizontally or vertically, or you may move exactly two cells diagonally. You are not allowed to visit any cell you already visited. You are not allowed to step outside the grid. You win if you are able to visit all 25 cells. Is it possible to win? If so, how? If not, what are the largest and smallest numbers of squares you can legally visit?

The code is (compile with --std=c++11):

Language: cpp
#include <stdio.h>
#include <utility>
#include <map>
#include <vector>

using namespace std;

typedef pair<int,int> pii;

vector<int> g[25];
map<pii,int> dp;

int d[8][2] = {
    {-3,0},
    {-2,-2},
    {-2,2},
    {0,-3},
    {0,3},
    {2,-2},
    {2,2},
    {3,0}
};

int f(int mask, int v) {
    pii key = make_pair(mask,v);
    if (dp.find(key) != dp.end()) {
        return dp[key];
    }
    if (mask == (1<<v)) {
        return dp[key] = -2;
    }
    for (auto x: g[v]) {
        if (mask & (1<<x)) {
            int val = f(mask - (1<<v),x);
            if (val != -1) {
                return dp[key] = x;
            }
        }
    }
    return dp[key] = -1;
}

int main() {
    for (int i=0; i<5; i++) {
        for (int j=0; j<5; j++) {
            for (int k=0; k<8; k++) {
                int ii = i + d[k][0];
                int jj = j + d[k][1];
                if (ii>=0 && ii<5 && jj>=0 && jj<5) {
                    g[i*5+j].push_back(ii*5+jj);
                }
            }
        }
    }
    int v = 0;
    int mask = (1<<25) - 1;
    while (v != -2) {
        printf("(%d,%d)\n",v/5,v%5);
        int u = f(mask,v);
        mask -= (1<<v);
        v = u;
    }
    return 0;
}

It prints out the path (0,0), (0,3), (2,1), (2,4), (0,2), (2,0), (2,3), (0,1), (3,1), (3,4), (0,4), (2,2), (4,0), (4,3), (1,3), (1,0), (3,2), (1,4), (4,4), (4,1), (1,1), (3,3), (3,0), (1,2), (4,2). By the way, for the problem I proposed, the answer is: When you run a secure RNG from a secure cipher, it's guaranteed that all sequential outputs will be different from each other. That's because if you had two values x and y with f(x)=f(y), it would be impossible to decrypt the cipher, even with the key. The result is that, if you read all 2^n numbers generated, you'd see that they are a permutation of all values in the range [0, 2^n-1]. That's very improbable to arise from random chance, you'd expect some values to repeat! It's counter intuitive, but it's more probable that you see a value repeating even if you read a square root of the total number. See here for an explanation. So, if you simply read the numbers, at around the square root of total possibilities you should start seeing repetitions. If that does not happen, it's likely that the source of these numbers is not really random, but generated by a block cipher in counter mode!

Posted: 7/29/2018 6:10 PM

Quote

OmnipotentEntity

He/Him

Player (36)

Joined: 9/11/2004
Posts: 2631

p4wn3r wrote:

By the way, for the problem I proposed, the answer is: When you run a secure RNG from a secure cipher, it's guaranteed that all sequential outputs will be different from each other. That's because if you had two values x and y with f(x)=f(y), it would be impossible to decrypt the cipher, even with the key. The result is that, if you read all 2^n numbers generated, you'd see that they are a permutation of all values in the range [0, 2^n-1]. That's very improbable to arise from random chance, you'd expect some values to repeat! It's counter intuitive, but it's more probable that you see a value repeating even if you read a square root of the total number. See here for an explanation. So, if you simply read the numbers, at around the square root of total possibilities you should start seeing repetitions. If that does not happen, it's likely that the source of these numbers is not really random, but generated by a block cipher in counter mode!

This is clever, but this isn't really unique to secure block cipher PRNGs, this is true of any PRNG that doesn't keep a significant amount of hidden state. So for instance, the MT is safe from this attack because its internal state is much larger than the output state, but a basic LCG would be vulnerable because its output is its state. This threw me because I was looking for something specific and unique to it being a cipher, rather than just having a state that is fully utilized in the output phase.

Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.

Posted: 7/29/2018 9:26 PM
(Edited: 8/8/2018 9:50 PM)

Quote

FractalFusion

Editor, Expert player (2079)

Joined: 6/15/2005
Posts: 3282

Warp wrote:

I'm not sure if there should additionally be the requirement that no three floor touch points should be collinear.

If the floor touch points are collinear but the centers of the spheres are not, then there is only one tangent plane. In the case where the floor touch points are collinear, that means one of the spheres (call it sphere A) is tangent to the cone inscribing the other two spheres. For there to be another tangent plane, that means sphere A must be tangent to the cone at a second point; if it is not (which is the case when the centers of the spheres are not collinear), then there is no second tangent plane.

p4wn3r wrote:

This week's Riddler classic puzzle kinda disappointed me, it's a simple Hamiltonian path problem, which can also be solved with dynamic programming.

Actually, you are expected to use pen and paper to solve it; that's why the Riddler put it as "a puzzle perfect for doodling during a boring class or meeting". Think of it like a knight's tour problem on a small board. You can program for a solution, but what's the point? There are many solutions; there's a solution I found which is a closed tour and is 180-degree symmetric: 12 02 20 09 03 22 16 05 25 15 19 08 13 18 07 11 01 21 10 04 23 17 06 24 14 Riddler Express is pretty open-ended (and therefore too difficult as an Express problem) this time around. I'll post it here, but I made a few edits to the problem statement in bold and square brackets in case it isn't clear what a centrifuge is or what it does. ------- A centrifuge [has a number of slots or "buckets" that are arranged in a circle, some of which have sample bottles placed in them. It] needs to be perfectly balanced along every axis before being run [; that is, the samples MUST be aligned so that their center of mass is in the exact center]; otherwise, the torque will damage the internal rotor. If a centrifuge has N equally spaced buckets, some of which you’d like to fill with K samples, and all samples are of equal weight, for what values of K can [the samples be aligned so that] all the samples [can] be spun in the centrifuge safely? Hint: You can run seven samples in a 12-bucket centrifuge. But you cannot run 10 samples in a 21-bucket centrifuge. ------- You can model this with points on the unit circle (or roots of unity in the complex plane) whose average is (0,0). Now it is clear that with N buckets, you can fill it with M>1 samples whenever M divides N; just place the samples so that they form a "ring" of M equally spaced samples. So the problem is probably(*) to find a union of such rings in the N buckets so that their sum is K. With 12 buckets you can put 7 samples safely (3+2+2). However, with 21 buckets you can't do that with 10 samples even though 10=7+3, since, once you take a ring of 7 samples, you can no longer fit a ring of 3. I think this is because 21 is a product of two primes, whereas 12 isn't. There are a few limited cases I can figure out, such that if N=2,3,4 or a multiple of 6, then you can put any number of samples from 2 to N-2 (this is why centrifuge buckets come in multiples of 6). If N is a prime power, or a product of two primes, then K has to be a multiple of a prime factor of N. Other than that, it seems difficult to express in general what the solution is. In conclusion, Riddler Express and Riddler Classic were switched around this week by accident. :) (*) I think, but cannot prove, that all safe alignments are a union of such rings.

Posted: 7/29/2018 11:10 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

FractalFusion wrote:

Actually, you are expected to use pen and paper to solve it; that's why the Riddler put it as "a puzzle perfect for doodling during a boring class or meeting". Think of it like a knight's tour problem on a small board. You can program for a solution, but what's the point?

That's what I was thinking of Riddler puzzles until last week's problems. For one of them you needed to do a numerical calculation, for another the algorithmic solution was the intended one (after I spent lots of time trying to solve it manually), so this time I just opened my text editor right away. Besides, I take my laptop to meetings, so I can do programming tasks if they are too boring :) About Riddler Express, if gcd(K,N) > 1, you can run K samples. If the gcd is d, then K=d*e, so pick e rings of d roots of unity, and it's done. That's not a necessary condition, though, since you can run 7 on 12, and gcd(7,12)=1. I would not be surprised if the intended solution is some backtracking nonsense. ------ Changing the subject, since we're in the topic of programming and the knight's tour was brought up, I remembered a very simple chess variant I used to play at a club just for fun. I've never seen this variant described anywhere on the Internet, I think it's a solvable game. Some time ago, I was trying to come up with an AI that plays it optimally, and wanted to put up a website for others to play, but got too bored. Perhaps this is a topic for the programming thread, but I think it can be posted here. The game was essentially "Chess Tic-Tac-Toe". It's played on a 3x3 board. The rules are the following: * Each of the two sides, white and black, has a rook, a bishop and a knight. They move on the 3x3 board just like the normal chess pieces. * There's no starting position. Instead, at the first move, white must choose a piece and drop it anywhere on the board. Similarly, after that, black drops one of his pieces on another square, without removing any other piece on the board. That continues until all six pieces are dropped. * With all six pieces on the board, white does the first move, according to normal chess movement rules, with the exception that no captures are allowed. Black moves later and so on. * If, at any time, a side manages to place all their three pieces on a row, column, or one of the two long diagonals, they win the game. Victory can happen even during the dropping phase. * If one side has no legal moves, the game is drawn. * If a position is repeated twice (same piece configuration, same side to move), the game is drawn. That looks like a nice game to exercise your AI skills, so I hope people here get interested. :)

Posted: 7/31/2018 6:01 AM

Quote

FractalFusion

Editor, Expert player (2079)

Joined: 6/15/2005
Posts: 3282

Apparently, the centrifuge problem was posted in a blog a month ago, before the Riddler came up with it. - That page expresses the solution in a neat way: you can safely run K samples in N buckets if and only if both K and N-K are expressible as a sum of prime divisors (possibly with repeats) of N. - You may have noticed that one of the images gives a centrifuge with 20 buckets. So much for centrifuges being a multiple of 6. At least it's an even number. - The proof uses this result that if K Nth roots of unity (possibly with repeats) add up to 0, then K is expressible as a sum of prime divisors of N. - It turns out I was wrong about all safe alignments being a union of evenly-spaced rings. For example, if N=30 and we number buckets around the circle, then we can place samples in the buckets 5, 6, 12, 18, 24, 25 and it all balances out. However, note that we can get this alignment by taking a ring of 5 and a ring of 3, and removing a ring of 2. Indeed, the paper above says that we can "add" and "subtract" these rings to get any sum of roots of unity that adds to 0, so I wasn't that far off.

Posted: 8/5/2018 8:57 AM

Quote

FractalFusion

Editor, Expert player (2079)

Joined: 6/15/2005
Posts: 3282

Riddler Classic this week is as follows: ------------------ I flip a coin. If it’s heads, I’ve won the game. If it’s tails, then I have to flip again, now needing to get two heads in a row to win. If, on my second toss, I get another tails instead of a heads, then I now need three heads in a row to win. If, instead, I get a heads on my second toss (having flipped a tails on the first toss) then I still need to get a second heads to have two heads in a row and win, but if my next toss is a tails (having thus tossed tails-heads-tails), I now need to flip three heads in a row to win, and so on. The more tails you’ve tossed, the more heads in a row you’ll need to win this game. I may flip a potentially infinite number of times, always needing to flip a series of N heads in a row to win, where N is T + 1 and T is the number of cumulative tails tossed. I win when I flip the required number of heads in a row. What are my chances of winning this game? (A computer program could calculate the probability to any degree of precision, but is there a more elegant mathematical expression for the probability of winning?) ------------------ As for an infinite series that gives the exact answer but not in closed or numerical form: It's easy to write down for the probability of losing this game. To lose the game, you have to fail to flip heads by flipping a tails, then fail to flip two heads in a row by flipping a tails, then fail to flip three heads in a row by flipping a tails, etc. This gives (1/2)(3/4)(7/8)(15/16)..., and the probability of winning is one minus this. As for whether this series can be evaluated easily: It doesn't converge too quickly, but it does converge to a number > 0. There is a way to show this as well as improve on this. First, (1/2)(3/4)(7/8)(15/16)... is the series (1-x)(1-x^2)(1-x^3)... evaluated at x=1/2. Then (1-x)(1-x^2)(1-x^3)... = 1 - x - x^2 + x^5 + x^7 - x^12 - x^15 + x^22 + x^26 - x^35 - x^40 + x^51 + x^57 - ... , based on this theorem, the Pentagonal Number Theorem. This not only converges much faster than the above infinite product (provided |x|<1) but also has an effective bound on the error from the rest of the terms. Evaluating at x=1/2 up to the term x^40 in WolframAlpha gives approximately 0.28878809508660, accurate to 14 decimal places, since the error is bounded by (1/2)^50. This is the losing probability, so the winning probability is about 0.71121190491340. I don't have a way to evaluate this exactly in closed form (without infinite sum or product); I thought at first the problem implied there was such a form but I'm not so sure now.

Posted: 8/5/2018 10:48 AM

Quote

Flip

Skilled player (1653)

Joined: 7/25/2007
Posts: 299
Location: UK

And of course, the peaches way 500kg, not 990kg.

Posted: 8/28/2018 8:07 PM

Quote

OmnipotentEntity

He/Him

Player (36)

Joined: 9/11/2004
Posts: 2631

This is one I ran into on the Reddit a few days ago, and it's burrowed into my brain. The original question is: What is the probability that if I flip 15000 coins, at least 15 consecutive heads appears at least once. The answer is a very large irreducible fraction that's about 20.45%. I won't explain in case someone wants to attack this problem. My question is: If C(f, h) is the number of combinations for "f" flips and "h" consecutive heads. (So that P(f, h) = C(f, h) / 2^f, and in particular P(15000, 15) = 20.45%), is there an explicit formula (ie, not recursive) for C(f, h) in terms of f and h. I have a method of finding an explicit formula in f for a given h. But I don't know how to extend it to an arbitrary h.

Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.

Posted: 8/30/2018 8:45 AM
(Edited: 8/30/2018 7:02 PM)

Quote

FractalFusion

Editor, Expert player (2079)

Joined: 6/15/2005
Posts: 3282

OmnipotentEntity wrote:

What is the probability that if I flip 15000 coins, at least 15 consecutive heads appears at least once.

Reminds me of the recent Riddler Classic problem on "Riddler Rugs", where you find the probability of finding a 4x4 same-color square within a 100x100 patch rug. However, the Riddler Rugs problem, being two-dimensional, only has inexact estimates based on inclusion-exclusion-type arguments, whereas the coin flip problem, which is one-dimensional, can be solved exactly. It would be easier to consider the opposite probability; that is, the probability that in a sequence of 15000 flips, there is not a subsequence of 15 (or more) consecutive heads. In addition, we will add an additional tails to the end of the sequence; this does not affect whether there is a subsequence of 15 consecutive heads. Let f(n) be the number of such sequences of length n with no subsequence of 15 consecutive heads, and the sequence ending in a tails (*). The probability would then be f(n+1)/2^n. The set B={T, HT, HHT, HHHT, ... , HHHHHHHHHHHHHHT}, the "atomic elements", are possible sequences of 0 to 14 heads terminated by a tails; B has generating function (by length) G(z) = z + z^2 + z^3 + ... + z^15. Then the elements of B construct all possible sequences (*), using any number (zero to many) of elements in any order. The generating function F(z) of f(n) is then: F(z) = 1+G(z)+G(z)^2+G(z)^3+... = 1/(1-G(z)) = 1/(1-z-z^2-...-z^15) = (1-z)/(1-2z+z^16). How to get z^n coefficient from F(z): We write F(z) in its partial fraction decomposition using residues. Because the roots of 1/F(z) are all simple (check this from the GCD of 1-2z+z^16 and its derivative), we can write: F(z) = sum[α]( (lim[z→α](z-α)F(z)) * (1/(z-α)) ) where the sum is over all roots of 1/F(z). However, 1-z-z^2-...-z^15 (and 1-2z+z^16) apparently cannot be factored algebraically, so we use L'Hôpital's rule on the limit when F(z) is in the form (1-z)/(1-2z+z^16): F(z) = sum[α]( ((1-α)/(16α^15-2)) * (1/(z-α)) ) = sum[α]( ((α-1)/(α(16α^15-2))) * (1/(1-α^-1z) ). The z^n coefficient is: sum[α]( ((α-1)/(α(16α^15-2))) * (α^-1)^n ) (**). About the roots of 1/F(z): They are all roots of 1-2z+z^16. One of the roots is a real number ζ very close to 0.5 (ζ≈0.500007631258) and the others lie just outside the complex unit disk in the annulus 1<|z|<1.2. The fact that ζ is the only root inside the unit disk, and the others have a complex absolute value between 1 and 1.2 can be proved using Rouché's theorem; I'll leave it to you to figure out. So when α is a root other than ζ, since 1<|α|<1.2, we can bound its term in (**) by |((α-1)/(α(16α^15-2)))*(α^-1)^n| < 1/70. Therefore the terms other than the one for ζ don't even add up to 0.5. This immediately gives us: f(n) is the nearest integer to ((ζ-1)/(ζ(16ζ^15-2))) * (ζ^-1)^n ≈ 0.5001068621 * 1.9999694754 ^ n. (approximate because you need thousands of digits of ζ to calculate it exactly) The probability of no subsequence of 15 consecutive heads is f(n+1)/2^n. For n=15000, that would be about 0.7955373. The probability of at least 15 consecutive heads at least once is one minus this, or about 0.2044627, which agrees with OmnipotentEntity.

OmnipotentEntity wrote:

I have a method of finding an explicit formula in f for a given h. But I don't know how to extend it to an arbitrary h.

The method above would be pretty similar for arbitrary h. You would find the real root ζ of 1-2z+z^(h+1) near 0.5, then compute f(n)=((ζ-1)/(ζ((h+1)ζ^h-2))) * (ζ^-1)^n, and the probability would be f(n+1)/2^n. ζ can be computed by Newton's Method on x^(h+1)-2x+1 starting with 0.5. The first iteration gives 0.5 + 1/(2^(h+2)-2h-2) which is already a very good approximation to ζ.

Posted: 8/30/2018 12:34 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Can't you find a recurrence relation for the coefficients of z^n on F(z) instead of using complex analysis? Normally if you play with the generating functions you can derive differential equations between them, which translate to recurrence formulas.

Posted: 8/30/2018 6:15 PM

Quote

OmnipotentEntity

He/Him

Player (36)

Joined: 9/11/2004
Posts: 2631

I approached the problem using a toy example. Let C(f, h) be the number of flip possibilities out of the 2^f that satisfy the condition that h heads appear in a row. Enumerating C(5,2) gives the following truth table (X is don't care, ? will be explained later).

HHXXX | True
THHXX | True
?THHX | True
??THH | True
Other | False

The ? marks are combinations that don't include the target sequence. So in the third line with one ? it can be either T or H. But the fourth line ?? can only be TT HT TH, not HH (otherwise it would be double counted in line 1.) Let ~C(f,h) = 2^f - C(f,h) for C(5,2) we have: 2^3 (first line) + 2^2 (second line) + 2 (third line ?) * 2 (third line X) + ~C(2,2) If we move from C(5,2) to C(6, 2) we get:

HHXXXX | True
THHXXX | True
?THHXX | True
??THHX | True
???THH | True
Other | False

Which can be examined line this:

HHXXX(X) | True
THHXX(X) | True
?THHX(X) | True
??THH(X) | True
(???THH) | True
Other | False

And so we have C(6,2) = 2 * C(5,2) (X on each line from 1-4) + ~C(3, 2) (last line) From here the recurrence is simply: C(f+1,h) = 2 * C(f,h) + ~C(f-(h+1), h) And then we can use the initial conditions: C(f=h, h) = 1 C(f<h, h) = 0 To find any given C(f, h) using a recurrence relationship. Now that we have a recurrence relationship and we can use eigendecomposition to find an explicit formula. First we have to get rid of the annoying constant: C(f+1, h) = 2 * C(f, h) - 2^(f-(h+1)) + C(f-(h+1), h) C(f, h) = 2 * C(f-1, h) - 2^(f-(h+2)) + C(f-(h+2), h) C(f+1, h) - 2 * C(f, h) = 2 * C(f, h) - 2^(f-(h+1)) + C(f-(h+1), h) - 2 * (2 * C(f-1, h) - 2^(f-(h+2)) + C(f-(h+2), h)) C(f+1, h) = 4 * C(f, h) - 4 * C(f-1, h) + C(f-(h+1), h) - 2 * C(f-(h+2), h) So for any given h we can construct a matrix A that when you multiply {C(f, h), C(f-1, h), ... C(f-(h+2), h)} against it you receive {C(f+1, h), C(f, h), ... C(f-(h+1), h)}, or the next iteration. Given that matrix, we can perform an eigendecomposition, let S be a matrix of the eigenvectors of A, and Λ be a diagonal matrix of the corresponding eigenvalues of A. Then SΛS^-1 = A (by some matrix math) Then because Λ is diagonal, it's very simple to take the nth power of and A^n = S Λ^n S^-1 (Because S and S^-1 cancel when multiplied.) I allowed Mathematica to chew on the condition where h=2, and it spit out: -(1/(4 Sqrt[11]))i (2 i Sqrt[11] (1+2^(3+f))+Root[-1-#1-#1^2+#1^3&,2]^(f-2) Root[704-10128 #1^2+42340 #1^4+#1^6&,2]+Root[-1-#1-#1^2+#1^3&,1]^(f-2) Root[704-10128 #1^2+42340 #1^4+#1^6&,3]+Root[-1-#1-#1^2+#1^3&,3]^(f-2) Root[704-10128 #1^2+42340 #1^4+#1^6&,6]) It's interesting that FractalFusion's answer does contain the x^3-x^2-x-1 pattern, but I'm curious where the strange x^6 formula comes from. You can construct a similar recurrence on h using the following: C(6,2)

HHXXXX | True
THHXXX | True
?THHXX | True
??THHX | True
???THH | True
Other | False

C(6,3)

HH(H)XXX | True
THH(H)XX | True
?THH(H)X | True
??THH(H) | True
(???THH) | False
Other | False

So we can say: C(f, h+1) = (C(f, h) - ~C(f-h, h))/2 With the initial conditions: C(f, h=0) = 2^f C(f, h=1) = 2^f - 1 So: 2 * C(f, h+1) = C(f, h) - 2^(f-h) + C(f-h, h) 2 * C(f, h) = C(f, h-1) - 2^(f-(h+1)) + C(f-(h+1), h) 2 * C(f, h+1) - 4 * C(f, h) = C(f, h) - 2^(f-h) + C(f-h, h) - 2 * (C(f, h-1) - 2^(f-(h+1)) + C(f-(h+1), h)) 2 * C(f, h+1) = 5 * C(f, h) - 2 * C(f, h-1) + C(f-h, h) - 2 * C(f-(h+1), h) C(f, h+1) = 5/2 * C(f, h) - C(f, h-1) + 1/2 * C(f-h, h) - C(f-(h+1), h) And the matrix can be set up in the same way, let's call this one B with eigenvector matrix T, and eigenvalue matrix M. Now I'm stuck. I have two matrices, and two degrees of freedom, but the matrix size of the f formula depends on the size of h, and vice versa. How do I put these together to find an explicit formula in two variables of C(f, h)?

Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.

Posted: 8/31/2018 2:41 AM
(Edited: 8/31/2018 11:36 PM)

Quote

FractalFusion

Editor, Expert player (2079)

Joined: 6/15/2005
Posts: 3282

p4wn3r wrote:

Can't you find a recurrence relation for the coefficients of z^n on F(z) instead of using complex analysis? Normally if you play with the generating functions you can derive differential equations between them, which translate to recurrence formulas.

I thought about solving it with the normal recurrence method (which is similar to the differential function method). You can easily find a recurrence characteristic of r^15-r^14-r^13-...-r-1 (or alternatively r^16-2r^15+1) which gives the form f(n) = sum[α]( C_α * α^n ) over all roots α of r^15-r^14-r^13-...-r-1, where the C_α are constants that need to be found. Note that these roots are not the roots of 1/F(z) in my previous post, but the reciprocal of them. However, because r^15-r^14-r^13-...-r-1 (or r^16-2r^15+1) can't seem to be factored algebraically, I wasn't able to figure out the constants C_α using the normal linear equation method on the initial conditions (since you need to know the roots α for that). The values should turn out to be the residues from my above post but there doesn't seem to be a way to know that with the normal recurrence method. That is one reason why I favored the complex analysis approach. The other reason is that to get the asymptotic behavior of f(n), you need to know the root of r^15-r^14-r^13-...-r-1 which is largest in complex absolute value, so that it dominates all the others. The largest one is a real number near 2 (about 1.9999694754, precisely the reciprocal of the ζ in my previous post) and the others are within the unit disk (|z|<1). Although WolframAlpha can verify this for the particular case h=15 (as in the image below), and seems to indicate that this is true for all sufficiently large h, I wanted to find a proof that this works, and Rouché's theorem was the only way I could find to do this.

OmnipotentEntity wrote:

From here the recurrence is simply: C(f+1,h) = 2 * C(f,h) + ~C(f-(h+1), h)

Do you mean C(f+1,h) = 2 * C(f,h) + ~C(f-h, h)? This one instead would agree with your calculation C(6,2) = 2 * C(5,2) + ~C(3, 2) when f=5, h=2.

OmnipotentEntity wrote:

So we can say: C(f, h+1) = (C(f, h) - ~C(f-h, h))/2

Some of my calculations don't seem to agree with this. For example: C(4,2)=8 (HHHH HHHT HHTH HHTT THHH THHT HTHH TTHH) C(4,1)=15 (everything but TTTT) ~C(3,1)=1 (TTT) 8≠(15-1)/2=7

Posted: 8/31/2018 2:28 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

I was thinking of something like F(z) = 1 - z + 2zF(z) - z¹⁶F(z) You can substitute the Taylor expansion for F, shift the coefficients, compare the z^n terms and find the relation. Of course, you still have to calculate the first 15 or 16 somehow, and as noted, when n is large, it's dominated by a root. But the fact that the polynomial can't be factored doesn't stop you from finding the linear relation, if you want to compute the values exactly.

Posted: 8/31/2018 6:32 PM

Quote

OmnipotentEntity

He/Him

Player (36)

Joined: 9/11/2004
Posts: 2631

FractalFusion wrote:

Do you mean C(f+1,h) = 2 * C(f,h) + ~C(f-h, h)? This one instead would agree with your calculation C(6,2) = 2 * C(5,2) + ~C(3, 2) when f=5, h=2.

Yes, you are correct, I made a mistake copying from my notes.

FractalFusion wrote:

Some of my calculations don't seem to agree with this. For example: C(4,2)=8 (HHHH HHHT HHTH HHTT THHH THHT HTHH TTHH) C(4,1)=15 (everything but TTTT) ~C(3,1)=1 (TTT) 8≠(15-1)/2=7

That part may be entirely incorrect, as I didn't use or test out the h side in recursion, and I might have made a simple math error of some sort. Or it may simply be that the identity does not hold in certain cases. I never actually proved anything, I just saw a pattern and extrapolated. In this case: C(4, 1):

HXXX | True
THXX | True
?THX | True
??TH | True
Other | False

C(4, 2):

H(H)XX | True
TH(H)X | True
?TH(H) | True
(??TH) | False
Other | False

The assumption ? in the third lines take on different values between the lines. In C(4,1) the ? can only be T whereas in C(4,2) it can be T or H, which is where the missing combination came from. So it seems as if the relationship I gave earlier does not hold for any case where the patterns on the ? changes with the changing h, which is actually quite often. Hell, it does not even hold for the original example I gave (C(6,2) -> C(6,3) the ?s on the 4th line change from 3 to 4 possibilities.) I apologize for that and thanks for catching it.

Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.

Posted: 8/31/2018 11:44 PM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Alright, I thought a bit about the problem and it's much simpler than you guys think. Let a_n denote the number of sequences of n flips without 15 consecutive heads. We have, for n between 0 and 14, inclusive (we define a₀ for convenience): a_n = 2^n. Also, a₁₅ = 2^15 - 1 For larger values of n, a_n = 2a_n-1 - a_n-16 To prove this, you can evaluate the generating function, use the relation in my previous post and compare terms in the Taylor expansion... Or use high school combinatorics. Suppose you have a valid sequence of length n-1. If you append a head or tail flip you generate a valid sequence of length n, except in one case, where the last 14 flips were heads and you put another head and got the last one. In that case, the flip before the final heads has to be tails, or else the sequence of n-1 flips would be invalid. So, by multiplying by 2 the number of sequences of length n-1 you overcount sequences where the last 16 flips are predetermined and the previous flips can form any valid sequence. So, you simply subtract the sequences of length n-16 and the job is done. That's it, really. Doing it for the probability is just dividing by 2^n and the asymptotic value can be found using well known methods for linear recurrences.

Posted: 9/1/2018 12:08 AM

Quote

FractalFusion

Editor, Expert player (2079)

Joined: 6/15/2005
Posts: 3282

p4wn3r wrote:

I was thinking of something like F(z) = 1 - z + 2zF(z) - z¹⁶F(z) You can substitute the Taylor expansion for F, shift the coefficients, compare the z^n terms and find the relation.

You can find the recurrence relation this way. That is, f(n)=2f(n-1)-f(n-16) when n≥16, and f(0)=1 and f(n)=2^(n-1) when 1≤n≤15. (The sequences I defined other than the empty sequence at n=0 must end with a tails.) However, because OmnipotentEntity specifically asked whether there were exact formulas that were "not recursive" (i.e. not in the form of a recurrence relation), I decided to do a full analysis of it. Of course, since there are only 15000 flips, you could use a computer to compute it (which is how I suppose OmnipotentEntity wrote down the exact answer here), but I wanted to see if there was a reasonable way at least to estimate it in general in case someone asks "Well what about 15000000 flips? 15000000000?". To add to this, while it is possible to get recurrence relations from generating functions, for the purpose of finding recurrence relations I would avoid generating functions and prove it directly. In this case, it is very easy to prove that f(n)=2f(n-1)-f(n-16) when n≥16, and f(n)=2^(n-1) when 1≤n≤15, assuming you define f(0)=1. By the way, my previous post had a broken image link which I fixed. The roots of the characteristic r^16-2r^15+1 are now shown properly in the image:

Edit:

p4wn3r wrote:

Alright, I thought a bit about the problem and it's much simpler than you guys think. ...

Yes, I knew all of this already, in case none of what I posted previously clearly indicated that this was so.

Posted: 9/1/2018 1:17 AM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

Maybe I'm not understanding the issue here. At least from my perspective, finding the recurrence relation is harder than finding the generating function. If you already have the relation, why not simply compute the numerator from the initial conditions and substitute the dominant root to find the residue? OmnipotentEntity was already diagonalizing matrices to get a formula from eigenvalue decomposition, which is completely equivalent to this method, so I am really confused...

Posted: 9/1/2018 5:00 AM

Quote

OmnipotentEntity

He/Him

Player (36)

Joined: 9/11/2004
Posts: 2631

I can diagonalize the matrix, but that requires fixing a value of h. I thought I could get a recurrence for h as well then somehow combine the two methods to get a single function in both f and h, but I couldn't figure it out. By continuing down this path I'm not suggesting that FractalFusion's answer is wrong or insufficient. (On the contrary, it's far and away more elegant than mine.) I was just trying to suss out why my answer wasn't working, and/or how to make it better.

Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.

Posted: 9/1/2018 7:05 AM

Quote

p4wn3r

Player (42)

Joined: 12/27/2008
Posts: 873
Location: Germany

FWIW the sequence of valid coin flips can also be taken as a (shifted) generalized n-bonacci sequence. That means, if you want to ban two consecutive heads, it's Fibonacci, three consecutive Tribonacci, four Tetranacci, and so on. These sequences are easier to work, even when they are a bit shifted compared to our problem, because their generating function is simpler. Fibonacci: z/1-z-z^2 Tribonacci: z^2/1-z-z^2-z^3 Tetranacci: z^3/1-z-z^2-z^3-z^4 And so on. This is a well studied problem. There doesn't seem to exist a simple recursion between different sequences. However, there is a series expansion for the dominant root. See theorem 3.9 here: http://www.fq.math.ca/Scanned/36-2/wolfram.pdf So, apparently, the easiest way to evaluate it at the asymptotic regime is to evaluate the root using a series expansion, factor the polynomial in the denominator of the GF using briot-ruffini or something similar, and plug this value to find the residue. EDIT: Actually, eq (9) in the linked paper already gives the coefficient for the sequence, so no need to do the procedure I outlined above.

Posted: 9/1/2018 5:20 PM

Quote

FractalFusion

Editor, Expert player (2079)

Joined: 6/15/2005
Posts: 3282

p4wn3r wrote:

Maybe I'm not understanding the issue here. At least from my perspective, finding the recurrence relation is harder than finding the generating function. If you already have the relation, why not simply compute the numerator from the initial conditions and substitute the dominant root to find the residue?

Sorry, I misunderstood your posts and thought you were asserting that finding the recurrence relation and using a computer to calculate f(1), f(2), ..., f(15000) from this relation was, in and of itself, the solution to the problem. It's because I was unable to figure out what exactly you wanted from your posts. You probably know me as a stickler in some of my posts around here. Perhaps the proof could be made more concise and complex analysis is not necessary. The reason I went through my reasoning in detail is because I wanted to understand certain aspects of the problem, such as why the residues/coefficients are why they are and how we know the dominant root near 2 is indeed the dominant root, with all other roots less than 1 in absolute value, without accepting it blindly. So it was partially for my understanding of the problem. If it is just a matter of using an algorithm to compute the numerator, without worrying about proof, then almost all of my post is unnecessary; just using the final answer that I posted is sufficient.

Forum Off topic some math challenges.

Forum

Off topic

some math challenges.