Test your knowledge of passwords

WBahn

Joined Mar 31, 2012
29,979
Okay, while you are waiting to hear from the exalted exam board about THEIR question, let's discuss a completely different question.

Here are the rules:

1) The password has four characters, all of which are hexadecimal digits, (i.e., 0123456789ABCDEF}.
2) The second character must be a decimal digit.
3) The third character must be even.
4) The fourth character must be an odd decimal digit.
5) At least one character must be a non-decimal digit.
6) No character may be used more than once.

How many legal passwords are there?

And I WILL post my solution tomorrow (i.e., Saturday) -- unless we lose internet again -- even if something happens to make me think I might be wrong.
 
Last edited:

joeyd999

Joined Jun 6, 2011
5,237
Here are the rules:

1) The password has four characters, all of which are hexadecimal digits, (i.e., 0123456789ABCDEF}.
2) The second character must be a decimal digit.
3) The third character must be even.
4) The fourth character must be an odd decimal digit.
5) At least one character must be a non-decimal digit.
6) No character may be used more than once.
I solved this in order: OD AD AE A or {4,2,3,1} where O=odd, D=digit*, E=Even, A=Any, and for below, H=Hex:

The branches are:

OD AD EH AH = 5P1*9P1*3P1*5P1 = 675
OD ED ED AH = 5P1*5P1*4P1*5P1 = 500
OD OD ED AH = 5P1*4P1*5P1*5P1 = 500
OD AD EH AD = 5P1*9P1*3P1*8P1 = 1080

For a total of 2,755.

My confidence level is high, but I don't have time to double check my answer.

*Edit: The definition of D is "decimal" not "digit". Otherwise, answer stands as is.
 
Last edited:

joeyd999

Joined Jun 6, 2011
5,237
The branches are:

OD AD EH AH = 5P1*9P1*3P1*5P1 = 675
OD ED ED AH = 5P1*5P1*4P1*5P1 = 500
OD OD ED AH = 5P1*4P1*5P1*5P1 = 500
OD AD EH AD = 5P1*9P1*3P1*8P1 = 1080

For a total of 2,755.
And this can be slightly condensed:

OD AD EH AH = 5P1*9P1*3P1*5P1 = 675
OD ED ED AH = 5P1*5P2*5P1 = 500
OD OD ED AH = 5P2*5P1*5P1 = 500
OD AD EH AD = 5P1*9P1*3P1*8P1 = 1080

Same total.
 

joeyd999

Joined Jun 6, 2011
5,237
The branches are:

OD AD EH AH = 5P1*9P1*3P1*5P1 = 675
OD ED ED AH = 5P1*5P1*4P1*5P1 = 500
OD OD ED AH = 5P1*4P1*5P1*5P1 = 500
OD AD EH AD = 5P1*9P1*3P1*8P1 = 1080
Dang nabit. I think I messed up on the AH's:

OD AD EH AH = 5P1*9P1*3P1*5P1 = 675
OD ED ED AH = 5P1*5P1*4P1*6P1 = 600
OD OD ED AH = 5P1*4P1*5P1*6P1 = 600
OD AD EH AD = 5P1*9P1*3P1*8P1 = 1080

My answer now is 2,955.
 

joeyd999

Joined Jun 6, 2011
5,237
FYI, for the peanut gallery:

I determine the order in advance by starting with the most restrictive rule and then proceed with each successively less restrictive rule. This seems to keep the number of branches in the tree to a minimum.

If there is a rule about this, I am unaware of it. One could probably write a proof, but that ain't me (I are a engineer, not a mathematician).
 

joeyd999

Joined Jun 6, 2011
5,237
When I was a kid, IIRC I was about 14 or 15, I wrote a graphical 5 card stud poker slot machine game for the TRS-80 Model 100 (really sweet, btw!).

I wanted it to be realistic, including the option to set the "house advantage", so I had to figure the odds of each winning hand.

There was no internet in those days, books were expensive, and I had no way to get to the library. So I just sat down and figured it out. This was before I took any P&S classes (which I didn't get until college).

Edit: I don't have the code anymore, so I cannot know if my solutions were correct -- but I did give myself an education!
 
Last edited:

joeyd999

Joined Jun 6, 2011
5,237
Also, I've developed my own Black Jack "system". I've play it vs. simulations for years, and it's never failed.

But I don't gamble with money, so I have no idea if it would hold up in a casino (and, it does take some concentration -- including remembering a bit of the history, for it to work).
 

WBahn

Joined Mar 31, 2012
29,979
FYI, for the peanut gallery:

I determine the order in advance by starting with the most restrictive rule and then proceed with each successively less restrictive rule. This seems to keep the number of branches in the tree to a minimum.

If there is a rule about this, I am unaware of it. One could probably write a proof, but that ain't me (I are a engineer, not a mathematician).
That's definitely the way I do it, too.

Unless things jump out at me -- which they often do -- I take a fairly formulaic approach which, not surprisingly, is usually not optimal (but it usually doesn't miss things, either).

I set up disjoint groups so that each choice can be mapped to a union of one or more of those groups. In this case I broke it up as follows:

OD - odd decimal digits: {13579}
ED - even decimal digits: {02468}
OA - odd alpha digits: {BDF}
EA - even alpha digits: {ACE}

That lets me set up the individual character constraints pretty easily:

1: (OD+ED+OA+EA)
2: (OD+ED)
3: (ED+EA)
4: (OD)

The constraint that at least one of the characters must be an alpha digit is then obviously seen as needing to be either position 1 or 3.

Like you, position 4 is the most restrictive, so I put it first:

(OD)

Next I put position 2 since that will leave positions 1 and 3, the two that are impacted by the "at least one alpha" requirement, for last.

(OD)(OD)
(OD)(ED)

Next I put position 3 because it has the fewest options and thus the fewest new branches

(OD)(OD)(ED)
(OD)(OD)(EA)
(OD)(ED)(ED)
(OD)(ED)(EA)

Now I can add the branches for the final character while being sure that the "at least one alpha" requirement is met:

(OD)(OD)(ED)(OA+EA)
(OD)(OD)(EA)(OD+ED+OA+EA)
(OD)(ED)(ED)(OA+EA)
(OD)(ED)(EA)(OD+ED+OA+EA)

There are a number of ways to split this up and regroup things, but this is good enough as is to put numbers to things:

(OD)(OD)(ED)(OA+EA) = (5)(4)(5)(3+3) = (5)(4)(5)(6) = 600
(OD)(OD)(EA)(OD+ED+OA+EA) = (5)(4)(3)(3+3+5+2) = (5)(4)(3)(13) = 780
(OD)(ED)(ED)(OA+EA) = (5)(5)(4)(3+3) = (5)(5)(4)(6) = 600
(OD)(ED)(EA)(OD+ED+OA+EA) = (5)(5)(3)(4+4+3+2) = (5)(5)(3)(13) = 975

Yielding a total of 2955

In the case of the second and fourth lines above, that the final multiplier is 13 can easily be seen (and used as a sanity check, which actually caught a mistake I made) because in those two rows the there are no constraints on the last choice (which is position 1) other than it not be one of the three previous choices drawn from the total pool of sixteen.

To head of claims that order counts and that this approach ignores that, I also did it while explicitly staying in order. You end up with a bunch more branches, but the same total result. This is actually how I did it first since I knew that I would need to show that at some point. I actually came up with a somewhat smaller number because I entered one of the counts incorrectly in my spreadsheet (I got something just under 2600 if I recall). I then wrote a Python script similar to the other one and it gave me a much larger number. I looked though it carefully and spotted some mistakes and after fixing them got 2955 and couldn't see any other mistakes, so I looked back at my spreadsheet and almost immediately spotted the typo and then it yielded the same 2955. For kicks, I did another Python script that first enumerated all 65,536 possibilities and then checked each against the rules and, not surprisingly, it also claimed 2955.
 

joeyd999

Joined Jun 6, 2011
5,237
Your formal analytic skills far exceed mine, WBahn.

I more of a seat-of-the-pants kind of problem solver. Most solutions to me just seem logically intuitive, without any rhyme or reason. I've been this way since I was a kid.

It's funny because a lot of times I'll think that I've solved a problem in some unique way, only to find later that, formally, that is how the problem is solved.

But I have come up with many unique solutions to some very intractable problems.
 

joeyd999

Joined Jun 6, 2011
5,237
And, Studiot, I haven't forgot about you.

There is no guilt in being wrong -- if you accept it and learn from it.

But I have no tolerance for those who purposely evade objective reality.
 

WBahn

Joined Mar 31, 2012
29,979
Your formal analytic skills far exceed mine, WBahn.

I more of a seat-of-the-pants kind of problem solver. Most solutions to me just seem logically intuitive, without any rhyme or reason. I've been this way since I was a kid.

It's funny because a lot of times I'll think that I've solved a problem in some unique way, only to find later that, formally, that is how the problem is solved.

But I have come up with many unique solutions to some very intractable problems.
My intuition isn't bad, but it often is not good enough to rely on it alone and, worse, will often lead me in the wrong direction. So I tend to rely more on being methodical and reasonably rigorous. Often times the methods I use are not the most sophisticated or elegant because I either don't know the better ways or I don't recall the fine details. You'll notice that I haven't invoked permutations or combinations in any of my developments -- that's not because I don't know about them. I can derive the formulas for them directly from first principles in short order. But I use them infrequently enough that it is just easier for me to take a more brute force route most of the time.

As an aside, I'll always remember my first college prob/stats course as being an exercise in which the instructor first demonstrates that the students do not, in fact, know how to count.
 

djsfantasi

Joined Apr 11, 2010
9,156
Great problem! Wish I had the time to tackle it. I don't think starting with the most restrictive is a mathematical principal, unless you're talking game theory. But it certainly makes sense.
 

joeyd999

Joined Jun 6, 2011
5,237
...I can derive the formulas for them directly from first principles in short order....
My all-time favorite professor taught Honors University Physics I & II -- he was brilliant. When ever I get stuck on a problem, his words ring through my head: "Always start from first principles."
 

WBahn

Joined Mar 31, 2012
29,979
Great problem! Wish I had the time to tackle it. I don't think starting with the most restrictive is a mathematical principal, unless you're talking game theory. But it certainly makes sense.
I wouldn't think of it as any kind of a fundamental principle of mathematics, but rather a practical principle of mathematical analysis. It would probably be like nodal or mesh analysis in which the technique is highly formalized, but they do not represent any new fundamental principles, just a methodical way of applying KVL and KCL.
 

WBahn

Joined Mar 31, 2012
29,979
My all-time favorite professor taught Honors University Physics I & II -- he was brilliant. When ever I get stuck on a problem, his words ring through my head: "Always start from first principles."
This was why I majored in physics and not chemistry. I don't do well at memorization and chemistry, at the level when I had to make my choice, was heavily about memorization while physics was about learning fundamentals and then applying them to problems. Much more suited to my temperament and mental framework.
 

djsfantasi

Joined Apr 11, 2010
9,156
I majored in Applied Mathematics and approached problems much more intuitively. No rote memorization for me. I took the principles and applied them puzzle-like to my problems. I had a good friend that worked together with me when we could, and we complemented each other. I'd see the steps toward the proof and he could in a snap name the theorem I described.
 

joeyd999

Joined Jun 6, 2011
5,237
This was why I majored in physics and not chemistry. I don't do well at memorization and chemistry, at the level when I had to make my choice, was heavily about memorization while physics was about learning fundamentals and then applying them to problems. Much more suited to my temperament and mental framework.
Engineering is the perfect discipline for me. It's got exactly the right proportion of theory and practical, and enough "gray areas" to keep me challenged. And, there's always an interesting problem to solve.

This reminds me of a joke I am sure you've heard many times before:

An engineer and a mathematician are each placed in the corners of a square room. A beautiful girl stands in the middle, exactly half way between the two.

They are given instructions: Each can move to a position half way between their current position and the girl at a rate of one move per minute. When they reach the girl, they can kiss her.

The mathematician is despondent. When asked why he is so upset, he says, "But I'll never reach her!"

The engineer smiles. He says, "I'll get close enough."
 
Top