# Department of Science, Math, & Technology

E = mc²

Science journals of interest: Scientific American - Nature - New Scientist - Science AAAS - Science Daily

LAST EDITED: March 17, 2015

Yeano's thread: Proving Something is Independent of our Axioms.
Yeano's thread: Algebraic Topology and Model Theory

We have LaTeX running on GT! Thanks to Xhin!

Team Building Puzzle
Posted: Posted October 10th, 2017 by EN
 Successfully navigating the waters during sea voyages is a challenging task. A captain’s most important decision is selecting the right crew for the voyage. A mix of different skill sets are required to sail the ship efficiently, navigate to the destination, and fish for food along the way. The table shows a list of crew members that are available for you to hire for the voyage. Each crew member demands a salary for the voyage and has different skill levels of Fishing, Sailing, and Navigation. In order for your journey to be successful, you must have a cumulative skill of 15 or more in each of the three skill categories from all of your chosen crew members. You may choose as many crew members as you like. What is the minimum achievable cost for the voyage? How do you get it?
settingsOptions
There are 17 Replies

Most people would try to brute force the answer (especially with our computers to do it). Would you suggest there is a better way of going about it?

Posted October 10th, 2017 by Kohlrak

There are a couple of useful techniques mentioned in the thread below. I also want to see what other creative ways people might try to solve it.

Posted October 10th, 2017 by EN

I did some analysis on the data (will attach a CSV at some point) and determined a few things:

Best fishermen -- Dan, Eva, Henry, Amy | Carl, Ida, Greg, Bill | Fred
Best Sailors -- Amy, Carl, Dan, Henry | Fred, Ida, Bill, Eva | Greg
Best Navigators -- Bill, Fred, Greg, Ida | Eva, Carl, Henry, Dan | Amy

Best all around: Carl, Eva, Dan, Ida | Henry, Amy, Bill, Fred | Greg

"Best" in this case means that they have the lowest score -- scores were calculated by dividing the salary (without the 000) by the proficiency in any area. All around bests were calculated by totaling all three scores.

I realized later that a better idea would be to crunch the salaries together and subtract the minimum salary so it looks like the 1-5 of the proficiency scale and then get a better way of comparing them.

Buuuut this didn't help so I'm going to do this a different way.

Posted October 11th, 2017 by Xhin
Xhin
The planets are aligned

I decided to look only at each individual proficiency...

Henry, Dan, Eva, and Amy are the minimum team to reach 15 in fishing. This is true on both actual data and score.

Amy,Carl,Henry,Dan are the minimum for sailing. Again, true in both ways.

Bill, Fred, Greg, Ida are the minimum for navigation

It's worth noting that while there are differences between the ranking in absolute proficiency and ranking in score, the differences are evidently small enough that the same three lists shows up every time.

Posted October 11th, 2017 by Xhin
Xhin
The planets are aligned

Best list

If you go by the best list, you need a minimum of Carl, Eva, Dan, Ida, Henry, Amy, Bill to reach 15 in all categories.

Fishing: 23
Sailing: 23

Salary: 339,000

This doesn't seem optimal.

One problem is that getting fishing and sailing to 15 together is easy, but the navigation list is the complete opposite. So just to confirm, I'm going to try to hit 15 by hitting 15 by navigation first and building from there..

Bill,Fred,Greg,Ida,Dan,Amy = (15,17,19), $308,000 I think this is probably optimal. For one thing, Dan and Amy are in both lists. Reaching 15 on sailing and fishing simultaneously is easy, reaching 15 on navigation is hard, so it makes sense to get that out of the way first and then hit the bests on the other categories. Of the bests lists, Dan/Amy/Henry seem to be universal, so I'm going to try it with all variations of those three: Bill,Fred,Greg,Ida,Dan,Amy = (15,17,19),$308,000
Bill,Fred,Greg,Ida,Dan,Henry -- (17,16,20) $326,000 Bill,Fred,Greg,Ida,Henry,Amy -- (16,18,20)$336,000

Posted October 11th, 2017 by Xhin
Xhin
The planets are aligned

Greg has a terrible total score but there's no replacement for him -- on any list that has Bill and Ida already, you would need THREE people to replace him to reach 15 on navigation.

So you definitely need Greg.

Fred is similarly terrible, but if you have Greg, Bill and Ida already you need at least two people to replace him.

Bill needs three people to replace him, Ida needs two people to replace her.

I can't imagine reaching 15 on navigation without Bill, Ida, Greg *and* Fred.

At that point your scores are (8,9,17) and you need 7 more fisherman and 6 more sailor skills to hit 15 on those categories. That's going to take a minimum of 2 people.

I chose Dan and Amy for those two people because the total of their Fisherman+Sailor scores were the lowest. Henry actually has more proficiency in both but his salary is much higher than Dan or Amy and that shows when you add the totals together.

I think this is probably your optimum list. I've been trying to find a flaw in it and have been unsuccessful.

Bill,Fred,Greg,Ida,Dan,Amy = (15,17,19), 308,000 Posted October 11th, 2017 by Xhin Xhin The planets are aligned Here's a CSV of the data table I was using: http://gtx0.com/rendered/team_building.csv name -- straightforward fishnum -- fishing proficiency sailnum -- sailing proficiency navnum -- navigation proficiency salary -- salary with the extra zeroes removed fish -- salary/fishnum sail -- salary/sailnum nav -- salary/navnum total = fish + sail + nav Posted October 11th, 2017 by Xhin Xhin The planets are aligned I like the way you think. Greg definitely is a powerhouse. To compare, I was able to find a five person crew for40000 less than what you currently have.

Posted October 11th, 2017 by EN

I went ahead and made a program to find your variation (and all possible variations). Here's the output:
http://gtx0.com/rendered/sail.htm

Posted October 12th, 2017 by Xhin
Xhin
The planets are aligned

I have no idea how you'd solve this with math -- unless you altered my algorithm to turn it into a matrix and used matrix math.

Posted October 12th, 2017 by Xhin
Xhin
The planets are aligned

By the way I don't know what the correct way of programming permutations is, but the way I did it was to run every number from 1 to 511, convert it to binary, and use each bit to determine whether that person was in the team or not. 511 is (2^9)-1, with 9 being the number of people.

Posted October 12th, 2017 by Xhin
Xhin
The planets are aligned

That's the solution I found, too. Technically what you generated were combinations. not permutations, since the order of the crew doesn't matter. But that's a pretty clever way of generating them.

Posted October 12th, 2017 by EN

It may be cheating, but using LINGO I wrote up an integer optimization program that gives me the following results:

Objective Value: 268k

Crew members: Amy, Bill, Carl, Greg, Henry

Posted October 14th, 2017 by Malas

I don't think that's cheating. I used Python. I don't know of an easy way to do this without computers.

Posted October 15th, 2017 by EN

By the way Xhin, this type of problem can also be flipped around. Instead of trying to find out the minimum amount to spend to meet a certain point requirement, you can maximize points given a cost limit. This can be applied to games, maybe even ones you run here. Given different items/stats that you can buy in different areas, you could find out the most (or "best") that you could do given a certain amount of money.

Posted October 15th, 2017 by EN

I originally tried doing it on paper as a standard optimization problem (Kuhn-Tucker conditions) but I haven't the least idea how to solve the problem, on paper, when the optimal set is restricted to integers.

Posted October 15th, 2017 by Malas

Yep. Integer programming is just that much more difficult than regular linear programming.

Posted October 15th, 2017 by EN