Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
No edit summary
No edit summary
 
(353 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
The '''missionaries and cannibals problem''', and the closely related '''jealous husbands problem''', are classic [[river-crossing problems]].<ref name=a>[http://links.jstor.org/sici?sici=0025-5572%28198906%292%3A73%3A464%3C73%3A%22JHA%22M%3E2.0.CO%3B2-S "The Jealous Husbands" and "The Missionaries and Cannibals"], Ian Pressman and David Singmaster, ''The Mathematical Gazette'', '''73''', #464 (June 1989), pp. 73&ndash;81.</ref>  The missionaries and cannibals problem is a well-known [[toy problem]] in [[artificial intelligence]], where it was used by [[Saul Amarel]] as an example of problem representation.<ref>[http://www.cc.gatech.edu/~jimmyd/summaries/amarel1968-1.html On representations of problems of reasoning about actions], Saul Amarel, pp. 131&ndash;171, ''Machine Intelligence 3'', edited by Donald Michie, Amsterdam, London, New York: Elsevier/North-Holland, 1968.</ref><ref>p. 9, [http://dx.doi.org/10.1007/11829263_1 Searching in a Maze, in Search of Knowledge: Issues in Early Artificial Intelligence], Roberto Cordeschi, pp. 1&ndash;23, ''Reasoning, Action andj Interaction in AI Theories and Systems: essays dedicated to Luigia Carlucci Aiello'', edited by Oliviero Stock and Marco Schaerf, Lecture Notes in Computer Science #4155, Berlin/Heidelberg: Springer, 2006, ISBN 978-3-540-37901-0.</ref>
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.


==The problem==
If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]]
In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board.<ref name=a />
* Only registered users will be able to execute this rendering mode.
* Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.


In the jealous husbands problem, the missionaries and cannibals become three married couples, with the constraint that no woman can be in the presence of another man unless her husband is also present.  Under this constraint, there cannot be both women and men present on a bank with women outnumbering men, since if there were, some woman would be husbandless.  Therefore, upon changing men to missionaries and women to cannibals, any solution to the jealous husbands problem will also become a solution to the missionaries and cannibals problem.<ref name=a />
Registered users will be able to choose between the following three rendering modes:


==Solving==
'''MathML'''
Amarel devised a system for solving the Missionaries and Cannibals problem whereby the current state is represented by a simple vector <a,b,c>. The vector's elements represent the number of missionaries on the wrong side, the number of cannibals on the wrong side, and the number of boats on the wrong side, respectively. Since the boat and all of the missionaries and cannibals start on the wrong side, the vector is initialized to <3,3,1>. Actions are represented using vector subtraction/addition to manipulate the state vector. For instance, if a lone cannibal crossed the river, the vector <0,1,1> would be subtracted from the state to yield <3,2,0>. The state would reflect that there are still three missionaries and two cannibals on the wrong side, and that the boat is now on the opposite bank. To fully solve the problem, a simple tree is formed with the initial state as the root. The five possible actions (<1,0,1>, <2,0,1>, <0,1,1>, <0,2,1>, and <1,1,1>) are then ''subtracted'' from the initial state, with the result forming children nodes of the root. Any node that has more cannibals than missionaries on either bank is in an invalid state, and is therefore removed from further consideration. The valid children nodes generated would be <3,2,0>, <3,1,0>, and <2,2,0>. For each of these remaining nodes, children nodes are generated by ''adding'' each of the possible action vectors. The algorithm continues alternating subtraction and addition for each level of the tree until a node is generated with the vector <0,0,0> as its value. This is the goal state, and the path from the root of the tree to this node represents a sequence of actions that solves the problem.
:<math forcemathmode="mathml">E=mc^2</math>


==Solution==
<!--'''PNG''' (currently default in production)
The earliest solution known to the jealous husbands problem, using 11 one-way trips, is as follows.  The married couples are represented as ''<math>\alpha</math>'' (male) and ''a'' (female), ''<math>\beta</math>'' and ''b'', and ''<math>\gamma</math>'' and ''c''.<ref name=b>Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia,
:<math forcemathmode="png">E=mc^2</math>
Raffaella Franci, pp. 289&ndash;306, ''From China to Paris: 2000 Years Transmission of Mathematical Ideas'', edited by Yvonne Dold-Samplonius, Joseph W. Dauben, Menso Folkerts, and Benno van Dalen, Stuttgart: Franz Steiner Verlag, 2002, ISBN 3-515-08223-9.</ref><sup>,&nbsp;p.&nbsp;291.</sup>


{| class="wikitable"
'''source'''
! Trip number
:<math forcemathmode="source">E=mc^2</math> -->
! Starting bank
! Travel
! Ending bank
|-
| (start)
| <math>\alpha</math>a  <math>\beta</math>b <math>\gamma</math>c
|
|
|-
|1
|<math>\beta</math>b <math>\gamma</math>c
|<math>\alpha</math>a →
|
|-
|2
|<math>\beta</math>b <math>\gamma</math>c
|←<math>\alpha</math>
|a
|-
|3
|<math>\alpha</math> <math>\beta</math> <math>\gamma</math>
|bc →
|a
|-
|4
|<math>\alpha</math> <math>\beta</math> <math>\gamma</math>
| ← a
|b c
|-
|5
|<math>\alpha</math>a
| <math>\beta</math><math>\gamma</math> →
|b c
|-
|6
|<math>\alpha</math>a
|← <math>\beta</math>b
|<math>\gamma</math>c
|-
|7
|a b
|<math>\alpha</math><math>\beta</math> →
|<math>\gamma</math>c
|-
|8
|a b
|← c
|<math>\alpha</math> <math>\beta</math> <math>\gamma</math>
|-©
|9
|b
|a c →
|<math>\alpha</math> <math>\beta</math> <math>\gamma</math>
|-
|10
|b
|← <math>\beta</math>
|<math>\alpha</math>a <math>\gamma</math>c
|-
|11
|
|<math>\beta</math>b →
|<math>\alpha</math>a <math>\gamma</math>c
|-
|(finish)
|
|
|<math>\alpha</math>a <math>\beta</math>b <math>\gamma</math>c
|}


This is a shortest solution to the problem, but is not the only shortest solution.<ref name=b /><sup>,&nbsp;p.&nbsp;291.</sup>
<span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples].


If however, only one man can get out of the boat at a time and husbands must be on the shore to count as with his wife as opposed to just being in the boat at the shore: move 5 to 6 is impossible, for as soon as ''<math>\gamma</math>'' has stepped out ''b'' on the shore won't be with her husband, despite him being just in the boat.
==Demos==


As mentioned previously, this solution to the jealous husbands problem will become a solution to the missionaries and cannibals problem upon replacing men by missionaries and women by cannibals.  In this case we may neglect the individual identities of the missionaries and cannibals.  The solution just given is still shortest, and is one of four shortest solutions.<ref>[http://portal.acm.org/citation.cfm?id=144045.144106 Cannibals and missionaries], Ruby Lim, pp. 135&ndash;142, ''Conference proceedings: APL '92, the International Conference on APL, 6–10 July 1992, St. Petersburg, Russia'', edited by Lynne C. Shaw, et al., New York: Association for Computing Machinery, 1992, ISBN 0-89791-477-5.</ref>
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:


If a woman in the boat at the shore (but not ''on'' the shore) counts as being by herself (i.e. not in the presence of any men on the shore), then this puzzle can be solved in 9 one-way trips:


{| class="wikitable"
* accessibility:
! Trip number
** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]]
! Starting bank
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)]
! Travel
** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)]
! Ending bank
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)]
|-
** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]].
| (start)
** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]].
|<math>\alpha</math>a <math>\beta</math>b <math>\gamma</math>c
** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode.
|
|
|-
|1
|<math>\beta</math>b <math>\gamma</math>c
|<math>\alpha</math>a →
|
|-
|2
|<math>\beta</math>b <math>\gamma</math>c
|← a
|<math>\alpha</math>
|-
|3
|<math>\beta</math> <math>\gamma</math>c
|ab →
|<math>\alpha</math>
|-
|4
|<math>\beta</math> <math>\gamma</math>c
| ← b
|<math>\alpha</math>a
|-
|5
|<math>\gamma</math>c
| <math>\beta</math>b →
|<math>\alpha</math>a
|-
|6
|<math>\gamma</math>c
|← b
|<math>\alpha</math>a <math>\beta</math>
|-
|7
|<math>\gamma</math>
|bc →
|<math>\alpha</math>a <math>\beta</math>
|-
|8
|<math>\gamma</math>
|← c
|<math>\alpha</math>a <math>\beta</math>b
|-©
|9
|  
|<math>\gamma</math>c →
|<math>\alpha</math>a <math>\beta</math>b
|-
|(finish)
|
|
|<math>\alpha</math>a <math>\beta</math>b <math>\gamma</math>c
|}


==Variations==
==Test pages ==
An obvious generalization is to vary the number of jealous couples (or missionaries and cannibals), the capacity of the boat, or both.  If the boat holds 2 people, then 2 couples require 5 trips; with 4 or more couples, the problem has no solution.<ref>[http://www.sciencenews.org/view/generic/id/4512/title/Math_Trek__Tricky_Crossings Tricky Crossings], Ivars Peterson, ''Science News'', '''164''', #24 (December 13, 2003); accessed on line February 7, 2008, URL update March 12, 2011</ref>  If the boat can hold 3 people, then up to 5 couples can cross; if the boat can hold 4 people, any number of couples can cross.<ref name=b /><sup>,&nbsp;p.&nbsp;300.</sup> 


If an island is added in the middle of the river, then any number of couples can cross using a two-person boat.  If crossings from bank to bank are not allowed, then 8''n''&minus;6 one-way trips are required to ferry ''n'' couples across the river;<ref name=a /><sup>,&nbsp;p.&nbsp;76</sup> if they are allowed, then 4''n''+1 trips are required if ''n'' exceeds 4, although a minimal solution requires only 16 trips if ''n'' equals 4.<ref name=a /><sup>,&nbsp;p.&nbsp;79.</sup>  If the jealous couples are replaced by missionaries and cannibals, the number of trips required does not change if crossings from bank to bank are not allowed; if they are however the number of trips decreases to 4''n''&minus;1, assuming that ''n'' is at least 3.<ref name=a /><sup>,&nbsp;p.&nbsp;81.</sup>
To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages:
*[[Displaystyle]]
*[[MathAxisAlignment]]
*[[Styling]]
*[[Linebreaking]]
*[[Unique Ids]]
*[[Help:Formula]]


==History==
*[[Inputtypes|Inputtypes (private Wikis only)]]
The first known appearance of the jealous husbands problem is in the medieval text ''[[Propositiones ad Acuendos Juvenes]]'', usually attributed to [[Alcuin]] (died 804.)  In Alcuin's formulation the couples are brothers and sisters, but the constraint is still the same&mdash;no woman can be in the company of another man unless her brother is present.<ref name=a /><sup>,&nbsp;p.&nbsp;74.</sup>  From the 13th to the 15th century, the problem became known throughout Northern Europe, with the couples now being husbands and wives.<ref name=b /><sup>,&nbsp;pp.&nbsp;291&ndash;293.</sup>  The problem was later put in the form of masters and valets; the formulation with missionaries and cannibals did not appear until the end of the 19th century.<ref name=a /><sup>,&nbsp;p.&nbsp;81</sup>  Varying the number of couples and the size of the boat was considered at the beginning of the 16th century.<ref name=b /><sup>,&nbsp;p.&nbsp;296.</sup>  Cadet de Fontenay considered placing an island in the middle of the river in 1879; this variant of the problem, with a two-person boat, was completely solved by Ian Pressman and [[David Singmaster]] in 1989.<ref name=a />
*[[Url2Image|Url2Image (private Wikis only)]]
 
==Bug reporting==
==See also==
If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de .
*[[Fox, goose and bag of beans puzzle]]
*[[Transport puzzle]]
*[[Circumscription (logic)]]
 
==References==
{{reflist}}
 
[[Category:Logic puzzles]]
 
[[pt:Problema dos canibais e missionários]]
[[uk:Задача про місіонерів та канібалів]]
[[zh:传教士和吃人恶魔问题]]

Latest revision as of 22:52, 15 September 2019

This is a preview for the new MathML rendering mode (with SVG fallback), which is availble in production for registered users.

If you would like use the MathML rendering mode, you need a wikipedia user account that can be registered here [[1]]

  • Only registered users will be able to execute this rendering mode.
  • Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.

Registered users will be able to choose between the following three rendering modes:

MathML

E=mc2


Follow this link to change your Math rendering settings. You can also add a Custom CSS to force the MathML/SVG rendering or select different font families. See these examples.

Demos

Here are some demos:


Test pages

To test the MathML, PNG, and source rendering modes, please go to one of the following test pages:

Bug reporting

If you find any bugs, please report them at Bugzilla, or write an email to math_bugs (at) ckurs (dot) de .

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=329754"