May 2019 - Challenge
Several people want to cross a river from one bank to the other using a boat that can carry at most two people.
There are some restrictions on who can be left on the bank, and the travelers want to use as few boat trips as possible.
Your task this month is to discover the restrictions on eight people that will make the shortest solution at least 73 trips long.
Here's a simpler example of this problem: Let's say you wanted to move six people from one river bank to the other, with the stipulation that the shortest solution includes at least 11 boat trips. This scenario could include three parents (A, B, C) and their respective children (a, b, and c respectively), when no child is willing to stay on either bank of the river with any other parent unless his or her own parent is also present on the same bank.
Please supply your answer as a 32-digit hexadecimal number that represents 128 bits: one for each possible subset of seven people that cannot be on the same river bank with the eighth person.
To exemplify the format, here is the six-person example presented above in this format:
The legal subsets of people include the following 22 sets:
...... abcABC ...ABC abc... .bcABC a..... a.cABC .b.... ab.ABC ..c... .bc.BC a..A.. a.cA.C .b..B. ab.AB. ..c..C a..ABC .bc... .b.ABC a.c... ..cABC ab.... 11 of them contain "a": abcABC abc... ab.ABC ab.AB. ab.... a.cABC a.cA.C a.c... a..ABC a..A.. a.....
This corresponds to the indices 31, 24, 23, 22, 16, 15, 13, 8, 7, 4, 0. Since we asked for 1 bit for every illegal set, the binary number has zeros in these places, so it is 01111110001111100101111001101110, which is, in hexadecimal: 7e3e5e6e.
By the way, there is a better solution for six people that requires 19 boat trips. What is it?
To give yet another example, for eight people, the hexadecimal number 4672616e63657320452e20416c6c656e yields a shortest path of length 13.
Bonus question: a name is hidden in the last example; she is the sixth in a list of 19 people (till today). Can you list them all?
Update (27/5): Since May's challenge was harder than usual - we are giving one more month to solve it.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
29/04/2019 @ 12:00 PM EST
Solution:
03/07/2019 @ 12:00 PM EST
List Updated:
03/07/2019 @ 12:00 PM EST
People who answered correctly:
Thomas Huet (04/05/2019 08:42 PM IDT)
*Alexander Daryin (08/05/2019 05:16 PM IDT)
Oleg Vlasii (09/05/2019 02:04 PM IDT)
Bert Dobbelaere (09/05/2019 10:24 PM IDT)
Jingran Lin (10/05/2019 02:39 AM IDT)
*Haye Chan (17/05/2019 09:41 AM IDT)
Eden Saig (17/05/2019 05:16 PM IDT)
Deane Stewart & Deron Stewart (22/05/2019 07:25 AM IDT)
*Kang Jin Cho (23/05/2019 03:48 AM IDT)
*David Greer (24/05/2019 04:58 PM IDT)
Michael van Fondern (26/05/2019 12:39 AM IDT)
Lorenz Reichel (26/05/2019 08:45 PM IDT)
Daniel Bitin (27/05/2019 02:28 AM IDT)
*Chris Shannon (28/05/2019 04:59 AM IDT)
*Alper Halbutogullari (28/05/2019 10:53 AM IDT)
Uoti Urpala (29/05/2019 08:36 AM IDT)
Guenter Nowak (30/05/2019 12:39 AM IDT)
Anders Kaseorg (31/05/2019 12:50 PM IDT)
Andreas Stiller (31/05/2019 06:40 PM IDT)
Todd Will (23/06/2019 09:32 PM IDT)
Vladimir Volevich (24/06/2019 10:10 AM IDT)
Reiner Martin (27/06/2019 01:05 PM IDT)
JJ Rabeyrin (29/06/2019 12:39 AM IDT)
Dieter Beckerle (30/06/2019 04:39 PM IDT)
People who answered correctly the 19 trips for 6 persons problem:
*Alper Halbutogullari (15/05/2019 04:12 PM IDT)
Eden Saig (17/05/2019 05:16 PM IDT)
*Deron Stewart & Deane Stewart (21/05/2019 12:42 AM IDT)
*Kang Jin Cho (23/05/2019 03:48 AM IDT)
*Nyles Heise (23/05/2019 07:23 AM IDT)
Lachezar Hristov (23/05/2019 03:26 PM IDT)
*David Greer (24/05/2019 04:58 PM IDT)
Tom Chen (25/05/2019 09:24 AM IDT)
Michael van Fondern (26/05/2019 12:39 AM IDT)
Lau Chi Yung (26/05/2019 10:24 AM IDT)
Lorenz Reichel (26/05/2019 08:45 PM IDT)
Marco Bellocchi (27/05/2019 02:10 AM IDT)
*Andreas Stiller (27/05/2019 02:20 AM IDT)
Daniel Bitin (27/05/2019 02:28 AM IDT)
*Chris Shannon (28/05/2019 04:59 AM IDT)
Dieter Beckerle (28/05/2019 10:52 AM IDT)
Uoti Urpala (29/05/2019 08:36 AM IDT)
Vladimir Milovanović (29/05/2019 06:13 PM IDT)
Guenter Nowak (30/05/2019 12:39 AM IDT)
Anders Kaseorg (31/05/2019 12:50 PM IDT)
*Boris Silantev (31/05/2019 05:51 PM IDT)
Maximilian Maczasek (02/06/2019 03:19 PM IDT)
Andreas Stiller (27/05/2019 11:44 AM IDT)
Guillaume Escamocher (04/06/2019 06:57 PM IDT)
JJ Rabeyrin (08/06/2019 03:41 PM IDT)
*Daniel Chong Jyh Tar (26/06/2019 06:12 PM IDT)
David F.H. Dunkley (30/06/2019 09:37 AM IDT)