combinatorics bomb problem

[hyksos]

A time bomb is set to go off. There are 26 unique boxes with sockets in them. The bomb has 8 plugs labelled 'a' through 'h'. You can disable the bomb if you place the right plugs into the right sockets. You know that all 8 plugs must be attached to a box to disengage the bomb.

How many total combinations are there?

http://i.imgur.com/3GodOzP.png

Explain your answer.

[Dave_Oblad]

Hi hyksos,

I didn't want to spoil your puzzle.. so I PM'd you my answer and explanation.
Hope I got it right (I suck at math).

Was going to solve it via writing a search program in base(26) but while prepping to code I saw a pattern and finished by Hand & Calculator, wasn't very hard (assuming I got it right...lol).

Took about 3 minutes to solve and 15 minutes to type an explanation.

Sidebar: I estimate it would have taken about 40 minutes to write & debug the code for a brute force search program but in retrospect.. the program would probably have taken several days to run its full search :(

Best Regards,
Dave :^)

[hyksos]

Dave_O,

You can repost your solution here in the thread and it won't spoil the problem for anyone. (Although it may lead some astray, and that could get interesting..)

[vivian maxine]

I once read a novel in which this actually happened. I know what the answer was there but you spoiled it by asking us to explain our answers. I didn't understand the answer when I read it in that novel. :-(

[hyksos]

Information for others who may visit this thread :

1. Dave_Oblad has not solved the problem.

2. A computer search is entirely plausible to get an answer. Although likely not instantaneous, it would definitely not take days to run it.

[Lomax]

Hi Hyksos,

Am I right in thinking the answer for permutations is just



or 62,990,928,000, and the answer for combinations is just




or 1,562,275? Intuitively for permutations of x boxes and y sockets the formula is just x!/(x-y)!, because there are x box options for socket 1, and for each possibility, there are one fewer options for socket 2, and so on. The number is trimmed down by the low availability of sockets which is why we have to divide by (x-y)!.

It was easier for me to think of combinations in terms of probability. Suppose you have to correctly choose (in any order) 8 balls out of 26 in order to win the lottery. You have a 1-in-26 chance of getting the first ball right (times 8, because you get 8 guesses, and the order doesn't matter); therefore only 25 balls and 7 guesses remain, so you have a 7-in-25 chance, and so on. Again our overall odds only require us to get the first 8 terms right, so we're only multiplying (26/8) x (25/7) x (24/6) x ...until we have eight bracketed terms - in other words we're only diving overall by y!

So I think (and I should know from memory, but my memory sucks) that the formula for combinations of x boxes in y sockets is



Or



There's probably a simpler way to express that but I don't have a chance - cognitively speaking - before lunch.

[Dave_Oblad]

Hi Hyksos,

Ok, my hand shortcut was off a bit. I did a brute force search program and it came out with:
30223145490365684577468 combinations.

I used 8²⁶ possible combinations as: 302231454903657293676544

But this includes illegal situations of Multiple Cables into shared sockets.

My program counts the number of illegal combinations as: 5609099076

Thus if I remove the Illegal combinations from the Max I get:
302231454903657293676544 (max)
-5609099076 (illegal)
----------------------------------
30223145490365684577468 legal combinations.

Is that better, or have you got a different answer?

Note: The algorithm took about 4 hours to run as a brute force search.

Regards,
Dave :^)

[hyksos]

The only way to get 8²⁶ is if you are considering 26-letter words made up of 8 symbols. Here is a random one :

Code: Select all

aeac eehb dagd bgdf deff gdcb ge


If you continue to hold on to strings you should instead be thinking of strings that look like this:

Code: Select all

xxxa bcde fghx xxxx xxxx xxxx xx


The x here denotes a socket with nothing in it.

An automated search program should only consider strings valid if they contain all letters a through h and x, and contain exactly (26-8)=(18) x's

[Dave_Oblad]

Hi Hyksos,

I start with 8 cables.
Each cable can be plugged into any of 26 sockets.
That's where I get 8²⁶ = 30223145490365684577468

Stand-by.. checking for 5 cables that I can count..

Regards,
Dave :^)

[hyksos]

There's probably a simpler way to express that but I don't have a chance - cognitively speaking - before lunch.

Speaking of simpler , this problem does not require the use of fancy formulae. It could be solved by a sufficiently clever high school student.

[Dave_Oblad]

Hi all,

Ok.. got it figured out.. 2 mistakes:

1st:
Total is not 8²⁶ but rather 26⁸
Much smaller.. as 208827064576 combinations Max.
This I can count using double precision without overflow.

2nd:
Typo bug in program.. was supposed to be a 6 and I had an 8.. couldn't see it.. weak eyes.

I Ran it for 5 cables.. very quickly.. and got the right answer..
This time.. it better be right.. lol.

Now going to run it for 8 cables.. should not take long.. back in a bit.

Regards,
Dave :^)

[Lomax]

Hi all,

Ok.. got it figure out.. 2 mistakes:

1st:
Total is not 8²⁶ but rather 26⁸

I see where you're coming from now, but wouldn't 26⁸ imply the same box can be attached to more than one socket?

[Dave_Oblad]

Hi Lomax,

Yes.. but I ran a 5 cable version (faster) and it could count all combinations (legal or not) and it came to a total of 11881376 total count. That's 26⁵ not 5²⁶.. so realized I was starting with the wrong total.

So now I know my grand total will be 26⁸. That helps to know.. because I'm running an 8 digit counter in base 26. That will give me a total count of 208827064576.
I test for illegal conditions of more than 1 cable in a socket as exclusions.
Thus if I take the total and subtract the illegals.. I should get the valid number of legal combinations.

As an extra test.. It tried 8⁸ which I know is 16777216.
The illegal count was 16736896.
The difference was 40320, which I know is right from another problem years ago (8-Queens).

So I needed that Total Count for this problem.. stripped out all the tests to just make it a 8 digit counter in base 26 and it came out 208827064576 total counts, which is 26⁸... yea... lol.

It was running the test for 5 cables that showed me my counter was off .. and lo.. a stupid typo in the program. Now all is fixed and I'm just waiting for the brute force program to give me the right answer.

Anyway,

I know I could probably find the correct simple equation on the Net and do this problem in just a few quick steps.. but I liked the challenge of doing it myself, without help. I may not be the sharpest pencil in the box.. but I'm certainly tenacious. If I set out to do something.. I don't give up until I've succeeded.

Just wished my Brain still worked as well as a few years ago.. sigh.. I'm so prone to dumb mistakes now days that I'm really looking forward to a simple retirement.

So.. I'll be back in a little while, when my program completes, and hopefully give the correct answer this time. Then I may be of mind to see how it's done the right way :)

Best wishes,
Dave :^)

[Lomax]

Anyway,

I know I could probably find the correct simple equation on the Net

I think I had it a few posts back. Hyksos hasn't contradicted me yet, anyway.

[Lomax]

There's probably a simpler way to express that but I don't have a chance - cognitively speaking - before lunch.

Speaking of simpler , this problem does not require the use of fancy formulae. It could be solved by a sufficiently clever high school student.

I don't think the formula I gave is fancier than anything I learned at high school. Just (26/8) x (25/7) x (24/6) x (23/5) x (22/4) x (21/3) x (20/2) x (19/1). Assuming you're not actually after permutations (rather than combinations) as the 4th sentence of your OP implies. In which case it would just be 26 x 25 x 24 x 23 x 22 x 21 x 20 x 19. I reckon.

[hyksos]

Sorry. After some minutes of thought I totally see where Lomax is coming from with combinations versus permutations.

Combinations
This would mean the bomb will not go off if you plug in the cables in the wrong order. Number of total combinations means that the act of plugging a cable into the wrong box will set off the bomb, but when you do so does not matter.

Permutations
This means that you must insert the right lettered cable into the right box at the right time, otherwise the bomb goes off. Where "time" means the order you insert them. The bomb may require that you plug cable b in first, and cable g in second, and so on. That number is much larger.

The problem as stated makes this ambiguous. Sorry about that!

The problem is asking for the total number of combinations, where no mistakes ever punish you by making the bomb go off early. So you can try as many plugs into whatever box you want, or remove them at will, as long as you stumble upon the right combination before the time runs out.

[Dave_Oblad]

Hi all,

Well finally the darn program finished after about 10 hours.

The output was:
Except = 145836136576
Counter = 208827064576

All it did was count in base 26 until a overflow stops it (a carry to the 9th digit).
Meanwhile a decimal Counter counted the total iteration loops.
The content value for each digit in base 26 represents the socket.
The weight position in the 8 digits represents the cable.

Since there just happens to be 26 sockets and 26 letters to our alphabet.. I can represent Base-26 using the letters of our alphabet, so the range was AAAAAAAA to ZZZZZZZZ.

Thus a random sample might be:
BARKXYSO and this combination would pass.. as there are no duplicate letters.
ABCDEFGA fails.. as it has duplicate "A"s. (1st cable & 8th cable in same socket "A")
The program counts these fails as 145836136576 exceptions to the total.

So:
Counter - Exceptions = Answer.

So:
208,827,064,576 (counter)
-145,836,136,576 (except)
------------------
= 62,990,928,000 legal combinations.

So that's the answer finally (barring further bugs that got past me.. not unusual).

I wrote the program to be as efficient as possible and it only took 10 hours to get an Answer.

I assume the Bomb Timer would stop when one of these combinations was correct.

About 63 Billion combinations have to be tried.

The Timer in the image seems to read 104:51 (Hours:Minutes?) or (Minutes:Seconds?).
This brute force method by computer ran at 1,749,748 legal combinations per second.
(actually about 3x faster than that.. since it tried searching all combinations, even illegal ones)

If you have to wait per single combination to see if the timer stopped.. your doomed ;-)

I hope I got it right this time (I'm pretty sure.. but I've said that before.. lol).

Also, Lomax answered earlier with his:
26 x 25 x 24 x 23 x 22 x 21 x 20 x 19 = 62,990,928,000 solution.

Since our answers agree.. I have additional hope.. yippie..

I'll try to remember that technique (at least until tomorrow when my mind gets erased again)
(Ever see "50 First Dates"?.. I feel like Drew Barrymore's character a lot lately.. lol)

Good night.. (my time).

Best wishes all and thanks to Hyksos for the fun problem.
Dave :^)

[hyksos]

The question was posted five days ago. It looks like interest in it has calmed down to a simmer. I will go ahead and present some interesting solutions below. Hopefully not spoiling this for anyone else who comes along.

[hyksos]

(weird zany solutions I.)

This solution could be produced by a high school kid, and requires no formulas.

Reduce the question to a simpler question : "How many combinations would there be if I only had 1 plug, plug a?" The answer pops out immediately as 26.

"What if I only had plug_a and plug_b? How many combinations?"
Well the first plug is 26 choices, and the second one is 25 choices left over. 26x25 = 650

Now ratchet up. What if I only had plug_a, plug_b, and plug_c? How many?
First is 26 choices, and the second one is 25 left over, and the plug_c will have empty 24 sockets left over. So 26x25x24 = 15600

A pattern should have emerged by now. If I have 8 plugs, we should get 26x25x24x23x22x21x20x19 = 62,990,928,000

[vivian maxine]

(weird zany solutions I.)

This solution could be produced by a high school kid, and requires no formulas.

Reduce the question to a simpler question : "How many combinations would there be if I only had 1 plug, plug a?" The answer pops out immediately as 26.

"What if I only had plug_a and plug_b? How many combinations?"
Well the first plug is 26 choices, and the second one is 25 choices left over. 26x25 = 650

Now ratchet up. What if I only had plug_a, plug_b, and plug_c? How many?
First is 26 choices, and the second one is 25 left over, and the plug_c will have empty 24 sockets left over. So 26x25x24 = 15600

A pattern should have emerged by now. If I have 8 plugs, we should get 26x25x24x23x22x21x20x19 = 62,990,928,000

Oh, for the joys of a math intellect. :-)

[hyksos]

(weird zany solutions II.)

We ask ourselves: what is the smallest integer which could produce a shuffling of the plugs amongst the sockets?

Shuffling by an integer works as follows: Say we have 6 playing cards from a card deck.

KD, QH, 4S, 6D, 6H, 9C

We want to shuffle them by means of an integer 513. We divide by integer arithmetic, and consider the remainder. We then swap the card on the far right with the card at that position. At each iteration of this procedure, the "far right" shrinks by 1 location. So it is 5 at the first iteration, 4 at the next, 3 at the next etc.

Code: Select all

0 , 1 , 2 , 3 , 4 , 5
KD, QH, 4S, 6D, 6H, 9C

513/6  =  85  +   (rem 3)     
Swap 5 with 3.
0 , 1 , 2 , 3 , 4 , 5
KD, QH, 4S, 9C, 6H, 6D

85/5 = 17 + (rem 0)
Swap 4 with 0
0 , 1 , 2 , 3 , 4 , 5
6H, QH, 4S, 9C, KD, 6D

17/4 = 4 + (rem 1)
Swap 3 with 1
0 , 1 , 2 , 3 , 4 , 5
6H, 9C, 4S, QH, KD, 6D

4/3 = 1 + (rem 1)
Swap 2 with 1
0 , 1 , 2 , 3 , 4 , 5
6H, 4S, 9C, QH, KD, 6D

1/2 = 0 + (rem 1)
Swap 1 with 1  .. with itself.
0 , 1 , 2 , 3 , 4 , 5
6H, 4S, 9C, QH, KD, 6D


In the code box above, we shuffled our "deck" of playing cards by means of the integer 513. But notice that repeated divisions ran 513 'dry' after so many divisions. That is, we started to get zeroes near the end. This indicates that 513 is too small of a number to 'encapsulate' the shuffling of six cards. We could have used an enormous integer to start and not run into this problem. Therefore there must exist a smallest sufficient integer for shuffling. Turns out that integer is 720. To get good shuffling amongst six cards, we would need an integer that is at least 720 (but as large as 1440).

For the bomb problem we imagine a string representing 26 empty sockets, where a period is an empty socket.

Code: Select all

"..... ..... ..... ..... ..... ."


Place our plugs at the right to start out.

Code: Select all

"..... ..... ..... ...hg fedcb a"


Now perform the shuffling algorithm. Take an enormous integer to start out , 9,473,684,210,526

Divide by 26, and consider the remainder.
9,473,684,210,526/26 = 364,372,469,635 + (rem 5)

Swap 'a' plug with the letter at position 5.

Code: Select all

"..... a.... ..... ...hg fedcb ."


Now divide by 25, and consider the remainder. Swap b with that remainder.

Continue this shuffling procedure untill all plugs are "swapped" into the grid of sockets.
We can consider what we divided by in this procedure. And ask what the smallest integer which could 'encapsulate' a shuffling of the plugs? The answer is 26x25x24x23x22x21x20x19 as those are the numbers we would have divided by. QED.

[Dave_Oblad]

Hi all,

Captain Kirk:
"We must save this planet and find the right combination to disable this bomb."

Officer Spock:
"Having observed your random methodology, I noted you repeated yourself 10 times in the last hour."

Captain Kirk:
"What methodology would you propose Spock?"

Officer Spock:
"In the early part of the 21st Century, the Mathematician Hyksos suggested a swapping method to avoid redundant combinatory patterns."

Captain Kirk:
"I remember that from the Cadet Academy Combinatorics Class, I'll start over and try that method."

Captain Spock:
"I've further observed you are averaging 1 combination per second."

Captain Kirk:
"What of it Spock?"

Officer Spock:
"At the observed rate, I calculate it will take you 1996.06205 Years to complete all combinations."

Captain Kirk:
"Experience has shown that I'm extremely lucky in such situations."

Officer Spock:
"Jim, these are not members of the opposite gender, thus I doubt past experience will suffice."

Captain Kirk:
"I don't know.. I've successfully plugged a lot of sockets in the past 5 years."

Officer Spock:
"Would you like me to calculate the odds for your success on this mission, Jim?"

Captain Kirk:
"That won't be necessary Spock. What would you suggest we do?"

Officer Spock:
"In such past situations, we have always had success by cutting the Red wire to the Battery."

Captain Kirk:
"Ok, here goes...."

<bomb disables>

Captain Kirk:
"As always Spock, your Logic is impeccable."

Officer Spock:
"Shall I request Scotty to beam us up now?"

Captain Kirk:
"You go on ahead Spock, I suspect the Ambassador's Daughter will be most grateful to hear my news."

Officer Spock:
"As you wish Jim. <beep beep> Scotty.. one to beam up."

<Episode theme music fills the air>

Best wishes all,
Dave :^)

[hyksos]

lol wut