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
Member
 
Posts: 745
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: 2999
Joined: 08 Sep 2010
Location: Southern California
Blog: View Blog (4)


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
Member
 
Posts: 745
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: 2589
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
Member
 
Posts: 745
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: 3240
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: 2999
Joined: 08 Sep 2010
Location: Southern California
Blog: View Blog (4)


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
Member
 
Posts: 745
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: 2999
Joined: 08 Sep 2010
Location: Southern California
Blog: View Blog (4)


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
Member
 
Posts: 745
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: 2999
Joined: 08 Sep 2010
Location: Southern California
Blog: View Blog (4)


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: 3240
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: 2999
Joined: 08 Sep 2010
Location: Southern California
Blog: View Blog (4)


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: 3240
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: 3240
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
Member
 
Posts: 745
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: 2999
Joined: 08 Sep 2010
Location: Southern California
Blog: View Blog (4)



Return to Mathematics

Who is online

Users browsing this forum: No registered users and 7 guests