Hi all,
This took me hours but i still cant do it... I have to make a program for t
his question... It took too long for me. Does anyone have any idea?
THanx
Logic City
The king, to test a candidate for the position of wise man, offers him a
chance to marry the young lady in
the court with the largest dowry. The amounts of the dowries are written on
slips of paper and mixed. A slip
is drawn at random and the wise man must decide whether that is the largest
dowry or not. If he decided it
is, he gets the lady and her dowry if he is correct; otherwise he gets
nothing. If he decides against the
amount written on the first slip, he must choose or refuse the next slip,
and so on until he chooses one or
else the slips are exhausted. In all, 100 attractive young ladies
participate, each with a different dowry. How
should the wise man make his decision?
>>>>> "Esen" == Esen Alici <·····@worldnet.att.net> writes:
Esen> Hi all, This took me hours but i still cant do it... I have
Esen> to make a program for t his question... It took too long for
Esen> me. Does anyone have any idea? THanx
Esen> Logic City The king, to test a candidate for the position of
Esen> wise man, offers him a chance to marry the young lady in the
Esen> court with the largest dowry. The amounts of the dowries are
Esen> written on slips of paper and mixed. A slip is drawn at
Esen> random and the wise man must decide whether that is the
Esen> largest dowry or not. If he decided it is, he gets the lady
Esen> and her dowry if he is correct; otherwise he gets
Esen> nothing. If he decides against the amount written on the
Esen> first slip, he must choose or refuse the next slip, and so
Esen> on until he chooses one or else the slips are exhausted. In
Esen> all, 100 attractive young ladies participate, each with a
Esen> different dowry. How should the wise man make his decision?
I could get my chances up to 25% by refusing the first 50 offers,
remembering the maximum dowry and then choosing the first one that
tops that from the next 50 draws.
Has anyone got a better strategy, preferably one that requires lisp?
Immanuel
Please pardon me being thick, but how do you derive the 25%? I can
follow splitting your chances to 50% by eliminating the first half of
the pool of nubile women, but I don't follow the next step. Also, if
the first 49 of the other half don't match or exceed the max of the
first set, you are forced to select the last, possibly much lower
entry.
Would it improve things to use the first set to identify a
distribution of dowries, then using the distribution as a basis for
evaluating the "quality" of the selections from the second set?
But all things considered, shouldn't information about the
Mother-In-Laws be included in the selection criteria?
;)
Gregm
>
>
> I could get my chances up to 25% by refusing the first 50 offers,
> remembering the maximum dowry and then choosing the first one that
> tops that from the next 50 draws.
> Has anyone got a better strategy, preferably one that requires lisp?
> Immanuel
>>>>> "Greg" == Greg Menke <······@erols.com> writes:
Greg> Please pardon me being thick, but how do you derive the 25%?
Greg> I can follow splitting your chances to 50% by eliminating
Greg> the first half of the pool of nubile women, but I don't
Greg> follow the next step. Also, if the first 49 of the other
Greg> half don't match or exceed the max of the first set, you are
Greg> forced to select the last, possibly much lower entry.
50% chance that second highest is in first group and 50% chance that
highest is in the second group.
Actually I guess the chance is a little higher because of the slightly
lower chance to have them both in the same group.
Greg> Would it improve things to use the first set to identify a
Greg> distribution of dowries, then using the distribution as a
Greg> basis for evaluating the "quality" of the selections from
Greg> the second set?
I don't think so, but this would at least require xlisp-stat :-)
Immanuel
Greg Menke <······@erols.com> writes:
> Please pardon me being thick, but how do you derive the 25%? I can
> follow splitting your chances to 50% by eliminating the first half of
> the pool of nubile women, but I don't follow the next step.
The next step happens because there may be more than one dowry larger
than the largest in the first half. If the first dowry larger than the
largest of the first half isn't the true largest one, it will be
accepted and you won't get to the largest.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
>>>>> "TAR" == Thomas A Russ <···@sevak.isi.edu> writes:
>>>>> "Greg" == Greg Menke <······@erols.com> writes:
Greg> Please pardon me being thick, but how do you derive the 25%? I
Greg> can follow splitting your chances to 50% by eliminating the
Greg> first half of the pool of nubile women, but I don't follow the
Greg> next step.
TAR> The next step happens because there may be more than one dowry
TAR> larger than the largest in the first half. If the first dowry
TAR> larger than the largest of the first half isn't the true largest
TAR> one, it will be accepted and you won't get to the largest.
Hmm. Interesting. Using this procedure, I am seeing empirical
averages in the 33% to 35% range, not 25% (e.g., 34,959 successes of
100,000 tries).
--
Russell Senior
·······@teleport.com
"Esen Alici" <·····@worldnet.att.net> writes:
> Logic City
> The king, to test a candidate for the position of wise man, offers him a
> chance to marry the young lady in
> the court with the largest dowry. The amounts of the dowries are written on
> slips of paper and mixed. A slip
> is drawn at random and the wise man must decide whether that is the largest
> dowry or not. If he decided it
> is, he gets the lady and her dowry if he is correct; otherwise he gets
> nothing. If he decides against the
> amount written on the first slip, he must choose or refuse the next slip,
> and so on until he chooses one or
> else the slips are exhausted. In all, 100 attractive young ladies
> participate, each with a different dowry. How
> should the wise man make his decision?
A classic in probability theory. You refuse the first 1/e candidates and
you take the next one that is larger than or equal to the largest dowry
seen in the first 1/e candidates.
ObLisp: (/ (exp 1)) evaluates to 0.36787945 so you let the first 37 slips
pass.
Lieven Marchand
···@bewoner.dma.be
>>>>> "Lieven Marchand" == Lieven Marchand <···@bewoner.dma.be> writes:
Lieven Marchand> A classic in probability theory. You refuse the
Lieven Marchand> first 1/e candidates and you take the next one
Lieven Marchand> that is larger than or equal to the largest dowry
Lieven Marchand> seen in the first 1/e candidates.
Lieven Marchand> ObLisp: (/ (exp 1)) evaluates to 0.36787945 so
Lieven Marchand> you let the first 37 slips pass.
I think my strategy is better. Maybe you would care to give a
reference to the name of the "classic in probability" as my
experience draws almost exclusively from sitting at a bridgetable
:-).
I strongly suspect that the fact that all dowries are of different
amounts gives me an edge in this case but wouldn't mind being
explained why I am wrong.
Immanuel
(I note that no one is answering the original question: namely,
"how do I write a program to explore this question". Since it
appears to be someone's homework, perhaps this is just as well.)
Immanuel Litzroth wrote:
> I think my strategy is better. Maybe you would care to give a
> reference to the name of the "classic in probability" as my
> experience draws almost exclusively from sitting at a bridgetable
> :-).
> I strongly suspect that the fact that all dowries are of different
> amounts gives me an edge in this case but wouldn't mind being
> explained why I am wrong.
The fact that the dowries are different can't possibly make any
difference, I think. (Since they could be different by arbitrarily
tiny amounts.)
Against your belief that your strategy is better I offer the following
evidence:
;; Shuffle an array.
(defun permute-randomly (array)
(let ((n (length array)))
(dotimes (i (1- n))
;; swap element i with a random element from [i,n)
(let ((j (+ i (random (- n i)))))
(when (/= i j) (rotatef (aref array i) (aref array j)))))))
;; Make an array containing 0...n-1 in that order.
(defun sorted-array (n)
(let ((array (make-array (list n))))
(dotimes (i n) (setf (aref array i) i))
array))
;; Make an array containing only zeroes.
(defun zeroed-array (n)
(make-array (list n) :initial-element 0))
;; Try the above-mentioned strategy and return the resulting dowry.
;; N-DISCARDED is the number of ladies rejected without a thought.
(defun try-once (array n-discarded)
(let ((n (length array))
(threshold (reduce #'max array :end n-discarded)))
(loop for i from n-discarded to (1- n) doing
(let ((value (aref array i)))
(when (> value threshold) (return-from try-once value))))
(aref array (1- n))))
;; Try the above-mentioned strategy N-TRIALS times and return
;; an array saying how many times each dowry resulted.
(defun histogram (n n-discarded &optional (n-trials (* n 10)))
(let ((array (sorted-array n))
(counts (zeroed-array n)))
(dotimes (i n-trials)
(permute-randomly array)
(incf (aref counts (try-once array n-discarded))))
counts))
;; Turn #(a b c) into #(a+b+c b+c c).
(defun partial-sum (counts)
(let* ((n (length counts))
(total (loop for count across counts summing count)))
(let ((result (make-array (list n))))
(loop for i from 0 to (1- n) doing
(setf (aref result i) total)
(decf total (aref counts i)))
result)))
;; Try the strategy N-TRIALS times and return an array whose
;; i'th element is the number of trials giving a dowry >= i.
(defun ps-hist (n n-discarded &optional (n-trials (* n 10)))
(partial-sum (histogram n n-discarded n-trials)))
;; Compare the N/e strategy to the N/2 strategy empirically.
(map 'list #'> (ps-hist 100 37 10000) (ps-hist 100 50 10000))
==> (NIL T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T
T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T
T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T T)
(The first NIL is because the first element of each array is 10000.)
I think N/e wins handsomely here.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
Immanuel Litzroth <········@plateau.rug.ac.be> writes:
> >>>>> "Lieven Marchand" == Lieven Marchand <···@bewoner.dma.be> writes:
>
> Lieven Marchand> A classic in probability theory. You refuse the
> Lieven Marchand> first 1/e candidates and you take the next one
> Lieven Marchand> that is larger than or equal to the largest dowry
> Lieven Marchand> seen in the first 1/e candidates.
>
> I think my strategy is better. Maybe you would care to give a
> reference to the name of the "classic in probability" as my
> experience draws almost exclusively from sitting at a bridgetable
> :-).
You can find it in the rec.puzzles archives under decision problems or
you can consult
<http://www.thewizardofodds.com/math/group2.html>
where it is problem 26. Alternatively, you can come and borrow my old
course on probability and statistics ;-)
--
Lieven Marchand
···@bewoner.dma.be
Check out this month's issue of the American Mathemetics Monthly. It gives
and overview of this type of problem.
faa
Esen Alici wrote in message <··········@bgtnsc03.worldnet.att.net>...
>Hi all,
>This took me hours but i still cant do it... I have to make a program for t
>his question... It took too long for me. Does anyone have any idea?
>THanx
>
>Logic City
>The king, to test a candidate for the position of wise man, offers him a
>chance to marry the young lady in
>the court with the largest dowry. The amounts of the dowries are written on
>slips of paper and mixed. A slip
>is drawn at random and the wise man must decide whether that is the largest
>dowry or not. If he decided it
>is, he gets the lady and her dowry if he is correct; otherwise he gets
>nothing. If he decides against the
>amount written on the first slip, he must choose or refuse the next slip,
>and so on until he chooses one or
>else the slips are exhausted. In all, 100 attractive young ladies
>participate, each with a different dowry. How
>should the wise man make his decision?
>
>