-2
$\begingroup$

In the Bible, a census is taken of the 12 tribes of Israel:

Simeon: 59,300 Levi: 22,000 Judah: 74,600 Issachar: 54,400 Joseph: 72,700 Benjamin: 35,400 Reuben: 46,500 Gad: 45,650 Asher: 41,500 Zebulun: 57,400 Dan: 62,700 Naphtali: 53,400

In the book of Deuteronomy 27: 12-13, the tribes are partitioned into two groups, the first group consisting of Simeon, Levi, Judah, Issachar, Joseph, Benjamin, and the second group consisting of Reuben, Gad, Asher, Zebulun, Dan, Naphtali.

Someone mentioned to me that this particular partition is the optimal in the sense that it minimizes the absolute value of the total number of people in the first group minus the total number of people in the second group. This partition problem is an NP-hard problem. http://en.wikipedia.org/wiki/Partition_problem

Is this calculation correct?

$\endgroup$
  • 2
    $\begingroup$ "Check my answer" questions are off-topic. It's hard to see how "check somebody else's answer" questions could be on-topic. And your title is misleading: solving a single instance of an NP-hard problem is not the same as solving the problem. $\endgroup$ – David Richerby Jun 27 '14 at 21:27
  • 4
    $\begingroup$ My point is that all answer-checking problems are off-topic. It doesn't matter if the answer is yours or somebody else's. As for "solving NP-hard problems", is the Boolean formula $X$ satisfiable? Is the one-vertex graph 3-colourable? Great! We can all solve single instances of NP-complete problems. $\endgroup$ – David Richerby Jun 27 '14 at 21:44
  • 1
    $\begingroup$ But every question is an answer-checking problem, by definition. $\endgroup$ – Craig Feinstein Jun 27 '14 at 22:37
  • 4
    $\begingroup$ Solving an instance of an NP-hard problem is not the same as solving an NP-hard problem. The latter requires being able to solve all instances in polynomial time. $\endgroup$ – mhum Jun 28 '14 at 1:30
  • 1
    $\begingroup$ @babou Well, I guess that when I say "solve", I'm actually implying "solve in polynomial time" which is the context I inferred from the asker's question. If instead "solve" was intended to mean "find a solution", brute force enumeration would be sufficient. $\endgroup$ – mhum Jun 30 '14 at 17:44
6
$\begingroup$

The partition provided in that passage is not optimal:

(Simeon + Levi + Judah + Issachar + Joseph + Benjamin) - (Reuben + Gad + Asher + Zebulun + Dan + Naphtali) = 318400 - 307150 = 11250

(Asher + Benjamin + Joseph + Reuben + Simeon + Zebulun) - (Dan + Gad + Issachar + Judah + Levi + Naphtali) = 312800 - 312750 = 50

$\endgroup$
  • $\begingroup$ I got the same result. Indeed the bible did not solve an optimisation problem. Even if they had, it wouldn't mean anything - they may well have brute forced it. (only need to check 4096 possibilities) $\endgroup$ – d'alar'cop Jun 28 '14 at 1:45
  • $\begingroup$ Naturally, I also brute-forced it. Given how few possibilities there were to check, I'd wonder why anyone would even claim that original partition was optimal (in the sense given by the asker). $\endgroup$ – mhum Jun 28 '14 at 1:52
  • 2
    $\begingroup$ It seems the asker did not know how to verify themselves. And, if I may, this kind of bombastic, fallacious mathematical or scientific claim is quite common among certain religious circles. $\endgroup$ – d'alar'cop Jun 28 '14 at 2:00
  • $\begingroup$ I just heard a rabbi say that one of his congregants told him this. $\endgroup$ – Craig Feinstein Jun 29 '14 at 2:15
  • 1
    $\begingroup$ If Levi is excluded, the optimal partition is obtained by (Benjamin+Asher+Gad+Zeubulun+Simeon+Dan) - (Reuben+Naphtali+Issachar+Joseph+Judah) = 301950 - 301600 = 350. $\endgroup$ – mhum Jun 30 '14 at 17:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.