combinatorics bomb problem

Discussions concerned with knowledge of measurement, properties, and relations quantities, theoretical or applied.

combinatorics bomb problem

Postby hyksos on March 20th, 2017, 2:22 pm 

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?

combinatorics.png


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

Explain your answer.
User avatar
hyksos
Active Member
 
Posts: 1031
Joined: 28 Nov 2014


Re: combinatorics bomb problem

Postby Dave_Oblad on March 20th, 2017, 11:37 pm 

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 :^)
User avatar
Dave_Oblad
Resident Member
 
Posts: 3212
Joined: 08 Sep 2010
Location: Tucson, Arizona
Blog: View Blog (2)


Re: combinatorics bomb problem

Postby hyksos on March 21st, 2017, 2:02 am 

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..)
User avatar
hyksos
Active Member
 
Posts: 1031
Joined: 28 Nov 2014


Re: combinatorics bomb problem

Postby vivian maxine on March 21st, 2017, 4:22 am 

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. :-(
vivian maxine
Resident Member
 
Posts: 2837
Joined: 01 Aug 2014


Re: combinatorics bomb problem

Postby hyksos on March 21st, 2017, 4:36 am 

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.
User avatar
hyksos
Active Member
 
Posts: 1031
Joined: 28 Nov 2014


Re: combinatorics bomb problem

Postby Lomax on March 21st, 2017, 10:19 am 

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.
User avatar
Lomax
Forum Administrator
 
Posts: 3475
Joined: 01 Jul 2010
Location: Nuneaton, UK


Re: combinatorics bomb problem

Postby Dave_Oblad on March 21st, 2017, 1:29 pm 

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 826 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 :^)
User avatar
Dave_Oblad
Resident Member
 
Posts: 3212
Joined: 08 Sep 2010
Location: Tucson, Arizona
Blog: View Blog (2)


Re: combinatorics bomb problem

Postby hyksos on March 21st, 2017, 4:44 pm 

The only way to get 826 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
User avatar
hyksos
Active Member
 
Posts: 1031
Joined: 28 Nov 2014


Re: combinatorics bomb problem

Postby Dave_Oblad on March 21st, 2017, 5:31 pm 

Hi Hyksos,

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

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

Regards,
Dave :^)
Last edited by Dave_Oblad on March 21st, 2017, 6:21 pm, edited 1 time in total.
User avatar
Dave_Oblad
Resident Member
 
Posts: 3212
Joined: 08 Sep 2010
Location: Tucson, Arizona
Blog: View Blog (2)


Re: combinatorics bomb problem

Postby hyksos on March 21st, 2017, 6:00 pm 

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.
User avatar
hyksos
Active Member
 
Posts: 1031
Joined: 28 Nov 2014


Re: combinatorics bomb problem

Postby Dave_Oblad on March 21st, 2017, 7:12 pm 

Hi all,

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

1st:
Total is not 826 but rather 268
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 :^)
User avatar
Dave_Oblad
Resident Member
 
Posts: 3212
Joined: 08 Sep 2010
Location: Tucson, Arizona
Blog: View Blog (2)


Re: combinatorics bomb problem

Postby Lomax on March 21st, 2017, 7:14 pm 

Dave_Oblad » March 22nd, 2017, 12:12 am wrote:Hi all,

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

1st:
Total is not 826 but rather 268

I see where you're coming from now, but wouldn't 268 imply the same box can be attached to more than one socket?
User avatar
Lomax
Forum Administrator
 
Posts: 3475
Joined: 01 Jul 2010
Location: Nuneaton, UK


Re: combinatorics bomb problem

Postby Dave_Oblad on March 21st, 2017, 9:53 pm 

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 265 not 526.. so realized I was starting with the wrong total.

So now I know my grand total will be 268. 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 88 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 268... 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 :^)
User avatar
Dave_Oblad
Resident Member
 
Posts: 3212
Joined: 08 Sep 2010
Location: Tucson, Arizona
Blog: View Blog (2)


Re: combinatorics bomb problem

Postby Lomax on March 21st, 2017, 9:59 pm 

Dave_Oblad » March 22nd, 2017, 2:53 am wrote: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.
User avatar
Lomax
Forum Administrator
 
Posts: 3475
Joined: 01 Jul 2010
Location: Nuneaton, UK


Re: combinatorics bomb problem

Postby Lomax on March 21st, 2017, 11:01 pm 

hyksos » March 21st, 2017, 11:00 pm wrote:
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.
User avatar
Lomax
Forum Administrator
 
Posts: 3475
Joined: 01 Jul 2010
Location: Nuneaton, UK


Re: combinatorics bomb problem

Postby hyksos on March 22nd, 2017, 3:54 am 

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.
User avatar
hyksos
Active Member
 
Posts: 1031
Joined: 28 Nov 2014


Re: combinatorics bomb problem

Postby Dave_Oblad on March 22nd, 2017, 6:19 am 

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 :^)
User avatar
Dave_Oblad
Resident Member
 
Posts: 3212
Joined: 08 Sep 2010
Location: Tucson, Arizona
Blog: View Blog (2)


Re: combinatorics bomb problem

Postby hyksos on March 25th, 2017, 9:33 am 

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.
User avatar
hyksos
Active Member
 
Posts: 1031
Joined: 28 Nov 2014


Re: combinatorics bomb problem

Postby hyksos on March 25th, 2017, 9:43 am 

(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
User avatar
hyksos
Active Member
 
Posts: 1031
Joined: 28 Nov 2014
vivian maxine liked this post


Re: combinatorics bomb problem

Postby vivian maxine on March 25th, 2017, 10:09 am 

hyksos » March 25th, 2017, 8:43 am wrote:(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. :-)
vivian maxine
Resident Member
 
Posts: 2837
Joined: 01 Aug 2014
hyksos liked this post


Re: combinatorics bomb problem

Postby hyksos on March 25th, 2017, 10:34 am 

(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.
User avatar
hyksos
Active Member
 
Posts: 1031
Joined: 28 Nov 2014


Re: combinatorics bomb problem

Postby Dave_Oblad on March 25th, 2017, 2:37 pm 

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 :^)
User avatar
Dave_Oblad
Resident Member
 
Posts: 3212
Joined: 08 Sep 2010
Location: Tucson, Arizona
Blog: View Blog (2)


Re: combinatorics bomb problem

Postby hyksos on March 25th, 2017, 3:19 pm 

lol wut
User avatar
hyksos
Active Member
 
Posts: 1031
Joined: 28 Nov 2014



Return to Mathematics

Who is online

Users browsing this forum: No registered users and 4 guests