A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Tag Info

6

Edit: @SkySpiral has had trouble getting the below formula to work. I currently don't have time to work out what the issue is, so if you're reading this it's best to proceed under the assumption it's incorrect. I'm not sure about the general problem with varying numbers of dice, sides, and drops, but I think I can see an efficient algorithm for the drop-1 ...

5

Solution Let there be $n=4$ dice each giving equal chances to the outcomes $1, 2, \ldots, d=6$. Let $K$ be the minimum of the values when all $n$ dice are independently thrown. Consider the distribution of the sum of all $n$ values conditional on $K$. Let $X$ be this sum. The generating function for the number of ways to form any given value of $X$, ...

1

You can likely encode other known NP-complete problems such as set-cover or 3SAT using a high-dimensional space with binary variables such that finding the global optimum "k-means" clustering solves these problems. For a full proof of NP-hardness, please visit the actual literature on this topic. I am pretty sure your can find papers that show the exact ...

1

I have a reasonably efficient algorithm for this that, on testing, seems to match results of pure brute force while relying less heavily on enumerating all possibilities. It's actually more generalized than the above problem of 4d6, drop 1. Some notation first: Let $X_NdY$ indicate that you are rolling $X$ dice with $Y$ faces (integer values $1$ to $Y$), ...

1

Noticed that no one has answered this question so far... Basically, the question is this: Is there a 0-1 vector $Z$ such that $$y_i = \alpha + \beta x_i + \gamma z_i + \epsilon_i$$ gives a (significantly) better fit than $$y_i = \alpha + \beta x_i + \epsilon_i.$$ "Significantly better" can be captured in terms of sums of squares as an inequality. The ...

Only top voted, non community-wiki answers of a minimum length are eligible