Peter Taylor
Reputation
5,400
Top tag
Next privilege 10,000 Rep.
Access moderator tools
1 14 29
Impact
~121k people reached

 Sep 9 comment Find a polynomial with evaluation equal to # of partitions of n into at most k parts Perhaps instead of $p(n;\le k)=P(n)$ the question statement should say that $p(n;\le k)=\mathrm{round}(P(n))$? E.g. for at most three parts, $p(n;\le 3)$ is the nearest integer to $(n+3)^2/12$ Sep 9 comment How many different sums of parts of a vector If you plot $S_j$ against $j$ then you get (in general) a zigzag, where each step goes up or down $2$. Now, $S_{n-1} - S_0 = 2 \sum_{i=1}^{n-1}v_i$ so, unless that sum is zero, $S_{n-1}$ and $S_0$ have opposite sign. If you split the line into three by dividing it at the first and last changes of sign (with a special case for sum is zero, sign never changes), you can show that it's only necessary to consider cases where $(\sum_{i=1}^{n-1}v_i) \in \{0,1,2\}$, since any crossing set found with a larger value than those can be "simulated" with a smaller value of the same parity. Aug 31 comment Would this proof strategy work for proving the lonely runner conjecture? @DavidvonRudisill, following r.e.s.' reasoning, we can consider the general case for three runners of speeds $0$, $a$, $b$. Then wlog the equispacing would have $at = \frac{3\alpha + 1}{3}$ and $bt = \frac{3\beta + 2}{3}$ with $\alpha, \beta \in \mathbb{N}$. But then $\frac{a}{b} = \frac{3\alpha + 1}{3\beta + 2} \in \mathbb{Q}$, so your strategy can at best work for a subset of runner speeds which has measure $0$ in the space of all possible runner speeds. This is (related to) the point James Hines was trying to make with the comment on irrational speeds. Aug 23 comment How many legal states of chess exists? web.archive.org/web/20140601124247/http://homepages.cwi.nl/… Aug 10 comment Complexity of subset-generation algorithm At a high level, $2^n$. At a low level, it depends on implementation details. There are probably some questions about it on the sister site stackoverflow.com Aug 9 comment A combinatorial identity 1. Not a typo: the $!!$ is a double factorial. 2. You're quite right. I've edited. Aug 9 comment Complexity of subset-generation algorithm It's not very clear to me what most of the operations are, or what the purpose of k is (it seems to be unused). If what you want is a way to iterate through a powerset efficiently then you should look into Gray codes. Aug 9 comment Complexity of subset-generation algorithm $\binom{i}{i} = 1$, so the sum is equal to $N + 1$. I think you've probably made a mistake in your analysis. Aug 4 comment What is the mixed strategy equilibrium bid, if any, for complete information auction games with minimum bid? I think you might be misunderstanding the extreme equilbria. They're the vertices of a polytope (or, in this case, a triangle) such that any point in the polytope is a Nash equilibrium. So in the discrete case there are mixed strategies which are equilibria, being any convex sum of the three extrema, but it just happens that the extrema are pure. Aug 3 comment What is the mixed strategy equilibrium bid, if any, for complete information auction games with minimum bid? That depends on whether you consider pure strategies to be a subset of mixed strategies or whether you consider the two sets to be disjoint. Jul 31 comment What is the mixed strategy equilibrium bid, if any, for complete information auction games with minimum bid? Does "complete-information" mean that both players know the values of $a$ and $\bar b$? If so, why are the bids not expressed as $b_i\in[\bar b, a)$? If not, what do they actually know? Jul 30 comment Representing all pairs shortest path in a graph with a matrix You will, at the very least, need to add an assumption that there are no negative-weight cycles, since otherwise the shortest paths are not well defined. Jul 26 comment Generate all De Bruijn sequences @qwr, DFS as typically described in algorithms text visits each edge only once and each node only twice. I can see how tracing an Eulerian path could be thought of as both depth-first and a search, but to call it DFS is to invite confusion. And to generate all Eulerian cycles you need to backtrack. Jul 18 comment Generate all De Bruijn sequences Jul 13 comment Game on simple finite graphs I'm glad that I now know why our calculations disagreed. Jul 13 comment Game on simple finite graphs @hardmath, "the smallest non-negative integer that is not already assigned to its neighbours". Since the only integers assigned to the neighbours are 2 and 2, the smallest unassigned non-negative one is 0. Jul 13 comment Game on simple finite graphs @hardmath, with both path(A,-1,K) and path(A,2,k) the value which will be played into the gap next to B can only be 0 or 1, and in particular is never -1 or 2 in either case; in fact, we could go further and say that for any $B \not\in \{0,1\}$, path(A,-1,K) = path(A,B,K). path(2,2,1) has only one possible move, which is to play 0 into the gap and lose, exactly as with path(-1,-1,1). Other discrepancies are (1,0,3), (1,0,5), (1,0,7), (2,0,7), (1,1,2), (1,1,7), (2,1,1), (2,1,5), (2,1,7). Jul 2 comment Game on simple finite graphs When working with paths, $a$ and $b$ are only going to be $0$ or $1$ for the most part: the exceptions are that filling the hole in $0?1$ requires a $2$ (although that's then a finished segment), and the $-1$ endpoint special case. One thing I don't understand from your table is that I think that $-1$ should be equivalent to $2$: in both cases, the node next to it will be either $0$ or $1$, with $1$ occurring only when the node at distance $2$ is $0$. Jun 30 comment Game on simple finite graphs Ah, hang on. That's not true for large values of $k$, because then a $0$ can be inserted in the middle of the path and the value of $b$ matters. I apologise for sending you down a blind alley. Jun 30 comment Game on simple finite graphs The $p(a,b,k)$ notation can be improved slightly by observing that the actual values of $a$ and $b$ don't matter: all that matters is $a - b$ and $b\mod 2$.