## Welcome to BrainDen.com - Brain Teasers Forum

 Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-)
Guest Message by DevFuse

# Quantum.Mechanic

Member Since --
Offline Last Active Nov 15 2013 12:58 PM

### In Topic: How many taxis are there?

15 November 2013 - 12:59 PM

I appreciate the numerical theory in the answer, but I don't buy into that. A Monte Carlo run shows that 90 is the most likely value, though this decreases slowly. Picking 5 random values from a list, where N is the highest value in the original list, and 90 is the highest of the 5 observed values, and running for 1 million trials, I get a table that looks like this. (I've not listed all values to 190, the last N that had any hits.)

N *** % 90 4.63% 91 9.01% 92 13.13% 93 17.02% 94 20.74% 95 24.21% 96 27.53% 97 30.72% 98 33.71% 99 36.58% 100 39.30%

From this run, the chances are even that N is less than or more than 105.

How to reconcile this result with the numerical analysis?

Also, if the numerical analysis has 2 valid answers, then there must be a range of valid answers in that region. It seems to me that this problem doesn't have an answer, but a handwaving "something about here" result.

### In Topic: dice problem

18 October 2013 - 03:06 PM

It seems that this puzzle is NP-hard and not NP-complete (if I understand this correctly), as there is not an efficient way to prove that the solution is minimal, without an exhaustive search for a better one. (Though a solution can be proved to be valid easily enough, just not minimal.)

Actually it's O(1).

Your comment got me thinking, I couldn't say that it's in NP because there is no n in the problem, We have 130 as a starting point and we want to see if any of the binome(129,8) dice combinations have 120 different sum...

Unless you are referring to the problem with "N-sided Dice", then yeah that's crazy exponential...

If you assume a specific problem, with specific inputs, then yes, people get lazy and say O(1), because the problem itself is a constant. That's cheating.

NP-complete requires a polynomial method to prove that a given solution is valid for a problem in NP. And these are generalized problems, so we never use O() notation for the specific ones (what would be the point?).

To be NP-complete, verifying a solution to the "smallest max face value for distinct sums of (s=sides, d=dice)" would have to scale as some power of s and/or d. There seems to be no way to do this short of duplicating the search, and the search is exponential (perhaps (s**d)**k?)

### In Topic: A Prisoner Problem

18 October 2013 - 02:37 PM

Spoiler for This is essentially a duplicate of

### In Topic: dice problem

09 October 2013 - 08:42 PM

Spoiler for Almost there...?

Still, lots of brute forcing, not much elegance.

### In Topic: dice problem

30 September 2013 - 01:00 PM

It seems that this puzzle is NP-hard and not NP-complete (if I understand this correctly), as there is not an efficient way to prove that the solution is minimal, without an exhaustive search for a better one. (Though a solution can be proved to be valid easily enough, just not minimal.)