Regarding The Three Indistinguishable Dice Puzzle: Reasoning

In my previous post, I gave my solution to the problem presented here, but I thought that it would be good to show the logic behind how I got the solution that I got. 
In the quest for an elegant solution, I was playing around with various functions over a,b,c.  One that I thought would be a good starting point was max(a,b,c)+min(a,b,c), since it would give a number 2 through 12 and wouldn't be biased upwards or downwards, since the median of a,b,c was what was being ignored.  I noticed that the distribution of results, if triples were ignored, was, indeed, symmetrical around 7, with 6, 7, and 8 occurring too often by multiples of 6, and with 2, 3, 4, 10, 11, 12 occurring too rarely by multiples of 6.  Of course, on this map, the excess from 6, 7, and 8 was 6 short of the deficit from the rest, but that's made up when we add the triples back in. 
I then looked at the patterns of groups that would result in 6, 7, or 8 and tried to find elegant ways to migrate them to the results that were coming up short.  This was pretty much trial and error, so one thing that I did was aim to end up with a rule saying that three of a kind makes 3, since that would be easy to remember. 
Any set of non-triples a,b,c is either a pair and another digit, which occurs 3 times out of every 216, or three different digits, which occurs 6 times out of every 216, so it was easy to move these things in whole lots of 6, and even to move them in lots of 3.  For instance, the rule that, if max(a,b,c)+min(a,b,c)=7 and a=b or b=c or c=a, then f(a,b,c)=min(a,b,c)+9 actually migrates pair of sets of 3, such as causing f(6,6,1) (or 6,1,6 or 1,6,6) and f(6,1,1) (or 1,6,1 or 1,1,6) to both be 10. 
So, hey, if you want to make a more elegant variation of my solution, mess around with ways to twist a,b,c where 5<max(a,b,c)+min(a,b,c)<9 to give the right number of missing results for 2,3,4,10,11,12 and put the triples somewhere and see if you can make one that uses fewer rules. 
Caveat:  Elegance is a matter of opinion.  I'm pretty sure that what I devised uses the simplest rules (though I could be wrong), so I'd anticipate that the other way to make a more elegant solution would be to have no if conditionals at all, though it probably involves math that's harder to do on the spot.  (I'm almost certain that such a solution would involve modular arithmetic, too, but I haven't actually looked at anyone else's solutions yet.)  So, I'd expect a "more elegant" variant of my solution to get it down to 3 or 2 rules, instead of my current 4. 
OK, have fun with that. 

Regarding The Three Indistinguishable Dice Puzzle

Recently, YouTube started recommending videos for me from Standup Math S.  Recently, I saw this video which presented an interesting problem.  Basically, it goes like this:  You roll three indistinguishable dice, to the point that you don't even know the order in which they returned results.  However, you want results as if you'd rolled 2d6.  That means not only that the results range from 2 to 12, but also that they be distributed like 2d6, i.e., that the odds of getting 3 be twice the odds of getting 2, that the odds of getting 4 be the same as the odds of getting 2 or 3, etc.  It's clearly possible with a lookup table, but the asker seeks a more elegant solution.

Last Friday at lunch, I came up with a fairly elegant solution, but I've been pretty busy, so I haven't gotten a chance to post it until now.  Here it is:

Let a, b, c represent the results of the dice, each an integer 1-6 inclusive, in any order.

f(a,b,c) =

• if a=b=c
• 3
• if a=b or b=c or c=a and max(a,b,c)+min(a,b,c)=7
• min(a,b,c) +9
• a≠b≠c≠a and either a=2i, b=2j, c=2k or a=2i+1, b=2j+1, c=2k+1, where i,j,k∈ℤ
• 2min(a,b,c)
• otherwise
• max(a,b,c) + min(a,b,c)

In layman's terms:

• If you get triples, then the answer is 3.  
• If you get doubles where low+high=7, then the answer is low+9 (a.k.a. high+low+low+2).  
• If you get all 3 even numbers or all 3 odd numbers, then the answer is 2*low.  
• Otherwise, add the highest and lowest numbers.  

I think that this solution is fairly elegant, even though it's in the form of 4 branches, because it's something easily understood (it doesn't even require exponents or modular arithmetic, let alone anything actually complicated) and 2 of the 3 non-main branches (triples and jumping straights) are fairly rare, all 4 branches are easy to solve, and there's some work overlap:  If you see doubles and add high+low to see if they're 7, if they're not, then you already did the math for your final answer.

And yes, I know that this is terribly informal and I didn't dig up all of the math symbols, but it's been a while since I did serious math, so I'm a bit rusty. 

EDIT 2016/Apr/30:  discovered and removed a touch of redundant text:  I had parenthetically said, in "if a=b or b=c or c=a and max(a,b,c)+min(a,b,c)=7", "(but not a=b=c)", but the max and the min would have different parity, so, duh.  

The Self-Referential Number

Recently, singingbanana (who goes by @jamesgrime on twitter) actually managed to post a video.  In this case, it was a puzzle.  The quest is to find a self-referential number, defined as a 10-digit number (implied to be in base 10) where the 1st digit says how many digits in the number are '0', the 2nd digit says how many digits in the number are '1', and so on.
You might want to try this problem yourself, so consider this your spoiler warning.  
Spoilers follow.
































The answer that I found was 6,210,001,000.  I suspect that this is the only solution, but I haven't proven that yet.  Maybe later.
I defined each digit with a letter, such that the number will be a,bcd,efg,hij.  Since the number has 10 digits, a+b+c+d+e+f+g+h+i+j=10.
Then, I put limits on how high each digit could be, just using itself and how many of its thing it represents.  For instance, a<=10 (even though 10's not a digit), because 10+10*0<=10.  Similarly, b<=5 because 5+5*1<=10, and c<=3 because 3+3*2<=10.
a<=9
b<=5
c<=3
d<=2
e<=2
f<=1
g<=1
h<=1
i<=1
j<=1
Basically, there can't be more than 1 of anything that counts 5s or larger, because having 2 of the thing that it counts (I probably should have come up with symbology for that) would be at least 10, and adding the counter then exceeds 10.
This also applies to the collection, though, so f+g+h+i+j<=1.
This also means that there are at least 4 0s, so 4<=a<=9.
If e=1, then e+4=5, so that would also force f through j to be 0.  Thus, e+f+g+h+i+j<=1.
This means that there are at least 5 0s, so 5<=a<=9.
Since a>4, it follows that some member of {f,g,h,i,j} is at least 1, and thus exactly 1.  This also means that e=0, so there are no 4s in this number.
Since there's at least one 1, b>=1.
If b were to be 1, though, then there would be at least two 1s, forcing b to be at least 2.  This would cause a problem for b, but wait, there's a 2, so c>=1.
Suppose that c=1 and b=2.  Using X as a placeholder for a, the number looks like this:
X,21?,0[01][01],[01][01][01]
where only 1 of those [01]s is actually a 1, and the rest 0.  
I don't see any 3s, so suppose that d=3.  We now know that there are 6 0s.  Thus, a=6.
Since there's one 6, g=1.  This gives us:
6,210,001,000

QED

P.S.:  The writing on this is a bit sloppy, but I'm using  plain text and I'm in a hurry.  I might edit this later for formality. 

UPDATE 2016/Jan/13:  So, the morning after I posted this (so the 8th), I thought of a proof that a<7.  And now I have a spare moment!  :D 

Assume that a > 6.  Then, hij=001, 010, or 100.  Then, b>0.
b=1 and (h=1 xor i=1 xor j=1) ==> b>1 ==> c>0 or d>0.  (See above that e+f+g+h+i+j <=1.) 
Since a≠0, b≠0, c≠0, and 1 of h, 1, or j ≠0, there are at least 4 non-0 digits, so there are no more than six 0 digits.  Thus, a, the number of 0 digits, cannot exceed 6.  

QED

On the Average Results of Savage Worlds Dice

Something occurred to me the other day, regarding the average results of dice in Savage Worlds.  For those who don't know, in Savage Worlds, each die (with the possible exception of damage dice - I forget) can explode.  For those who don't know what that means, if a die rolls its highest result, that result is kept and then added to a new roll of that die.
Obviously, the minimum result of any roll (except 1d4-2) is a 1, and the maximum result is an arbitrarily large number.  However, what's the average result of any die roll?

Consider a 1d6 roll, the most common roll in Savage Worlds.
Let x be the average result, which we seek.



We're re-using x on the right, since the average roll being added to 6 in the best case is, itself, the average case of a new die roll.  Thus, we can use basic algebra to solve for x:






In this specific case, the result is x = 21/5 = 4.2.  However, I've left the sum to reveal the generalized form.  For a die of size k, the average result is

While I don't think that this is new knowledge, I also suspect that tables are commonly referenced, so I thought that I'd put this generalized form out there.

EDIT:  I had a botched example result; I was thinking of the d8 case.  
EDIT:  I discovered that the fancy math stuff is rendering weirdly on Blogger.  I'll fix it later; for now, you can click on it if it's illegible:  The page where you land will have it (correctly) in about the middle.  

Regarding Non-Alphabetical Ordering of Reduced Fractions as Strings

I ran across a programming problem a while back, and I've been meaning to post about the consequences of it.  There is a situation in which there are fractions that are represented as strings and that, by default, sort alphabetically.  The representations were immutable, but were usually reduced, so an ordering flag had to be added that would apply before the alphabetization.  I'll try to describe the problem mathematically below. 

Let F(n) be the set of fractions m/n such that m,n , n > 1, n is not prime, 0 < m < n. 
Note:  If n were prime, then the solution would be trivial, since the fractions cannot be reduced, and therefore the proper order and alphabetical order would be the same.   
Assume that either (1) we use a high enough base that n is always a single character, or (2) every string representation of the fraction m/n, for every value of m, is equally and sufficiently 0-padded in both the numerator and the denominator.  (For an example of (2):  If n=10, then 9/10 would be "09/10", and 8/10=4/5 would be "04/05".)  For a given m, what is the minimum number of ordering flags such that, if each fraction m/n is associated with one, then sorted first by flag and then alphabetically, the fractions, even reduced, would be in ascending order? 

An Example: 
Let n = 8. 
F(n) = {1/8, 2/8, 3/8, 4/8, 5/8, 6/8, 7/8} = {1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8}. 
If sorted alphabetically, then these fractions would come out as "1/2, 1/4, 1/8, 3/4, 3/8, 5/8, 7/8". 
Assume that 3 flags is sufficient.  Call them "a", "b", and "c".  Clearly, 1/8 will need "a", 1/4 will need "b", and 1/2 will need "c".  Similarly, 3/4 will need either "a" or "b", and 3/8 will need either "b" or "c", but they cannot both take "b". 
For brevity and clarity, I will simply tack the flag on the front of the fraction, so that alphabetical order will put them in the proper order.  One valid association, then, produces "a1/8, b1/4, b3/8, c1/4, c5/8, c3/4, c7/8".  (In fact, I just realized that this is the only valid association on 3 flags, but I'll leave this as an exercise.)  
2 flags is not sufficient for this set:  If any {1/2, 1/4}, {1/4, 1/8}, or {1/2, 1/8} get the same flag, then they will resolve in the wrong order. 

When looking at the set, reduced, the minimum  number of flags is at least the largest number of common numerators (3, in the above example, as 3 of the reduced fractions had 1 as their numerator).  However, is there a good way to determine this purely from looking at n? 

Note:  I've also determined that 3 flags is sufficient when n=9, when n=10, and when n=6.  Demonstration of this is left as an exercise. 

Another example: 
Let n = 4. 
F(n) = {1/4, 2/4, 3/4} = {1/4, 1/2, 3/4}. 
2 flags is sufficient:  "a" must go with 1/4 and "b" with 1/2 (and 3/4), sorting them as "a1/4, b1/2, b3/4". 

Note:  In any case where 1 flag is sufficient, the solution is trivial.  That is, flagging is unnecessary. 

Conjecture:  The minimum number of flags needed to sort the reduced fractions alphabetically is x, where x is one less than the number of factors (prime or otherwise) of n. 

An example that attempts to exercise the conjecture: 
Let n = 12. 
Let H(n) be the set of factors of n.  For n=12, H(12) = {1, 2, 3, 4, 6, 12}.  The size of H is 6, so x=5. 
F(12) = {1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12} = {1/12, 1/6, 1/4, 3/4, 5/12, 1/2, 7/12, 2/3, 3/4, 5/6, 11/12}. 
This resolves as:  "01/02, 01/03, 01/04, 01/06, 01/12, 02/03, 03/04, 05/06, 05/12, 07/12, 11/12". 
Let us try to minimally alphabetize it: 
a01/12, b01/06, c01/04, d01/03, d05/12, e01/02, e07/12, f02/03, f03/04, f05/06, f11/12. 
5 flags was insufficient, as I had to go to 6 to put 2/3 after 7/12, so the conjecture is incorrect. 



Well, that's all for now.  I might revisit this problem at a later date.  We'll see.