GingerAle
Oct 14, 2018

#2**+2 **

Solution:

The Traveling Salesman Problem (TSP) is **not** NP-complete. It is not solvable, nor is its solution verifiable in **polynomial time**. The time complexity for brute force analysis is **O(n!).**

\({}\)

For this question, a close approximation for brute force analysis time is \( \dfrac {(11-1)!} { (7-1)!}* (8.5E-3) = 42.85 \text { seconds.} \)

For comparison, if there were (21) cities then the computation time would exceed (910,761) **years**.

Here is an animated graphic giving a visual representation for the analysis of a seven-city TSP.

https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computing_a_solution

The Wiki article also gives a comprehensive overview for the Traveling Salesman Problem.

GA

GingerAleFeb 8, 2020

#9**+1 **

Solution for #2:

\({}\)

Solve this using the derangement formula:

\(!n = \left [\dfrac{n!}{e} \right] \qquad | \qquad \text { where [ ] is the nearest integer, and (e) is Euler’s Number ~(2.71828...).} \\\)

*In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points. *Source: https://en.wikipedia.org/wiki/Derangement

\(!6 = \left [\dfrac{6!}{e} \right] = 265 \; \text {sets where no color occupies its original position.}\\ \)

GA

GingerAleFeb 5, 2020

#3**0 **

~~The two solutions presented above are wrong.~~

**Apologies: I’m so use to seeing wrong answers, and the large drop in the x value (weight) are common for these types of questions;**

**I failed to check and verify my own work. **

**These types of questions require careful reading to understand what it is asking for. **

Such questions are common in science and statistics, both in academics and in the real-world.

**The mathematical solution seems paradoxical, but it’s not; it’s the language of the question that gives this illusion.** Banana Paradox

\( {\text { Deleted Equation }}\)

\(\text { Here’s the correct equation. }\\ x=8+\dfrac{90}{100}x\\ x=80.0 \;Lbs\\ \text { The weight of the grapefruit is $80.0$ Lbs } \)

This now agrees with Badada’s and EP’s solutions above, and Dragan’s solution below.

Related question, with an expanded solution method.

https://web2.0calc.com/questions/help-asap-thanks_2#r5

GA

GingerAleJan 21, 2020