Prev: mini-challenge from UH contest
Next: Analogon to 28S' FORM on the HP 50g
From: Scott Hemphill on 30 Nov 2009 14:08
I don't know how many of you followed the thread regarding the
University of Houston high school calculator contest, but it seems
clear that it wasn't really expected that anyone would be able to
solve the last problem on a pocket calculator, especially in the
1-hour timeframe. I don't know about the capabilities of the TI
calculators that all the students used, but it seems as if this
problem might very well be feasible on the HP48 series.

The problem:

Thirteen men and nineteen women are placed in line so that 3 women are
at the front of the line, 4 women are at the end of the line, and men
and women alternate in the line from the fourth position to the 29th
position, with a man standing in the 4th position. Each of the first
31 people choose a random number in the set {2, 3, … , 100}. You don't
know their choices, but you know that the 32nd person knows their
choices, and you hear her say that all of the men have chosen prime
numbers in increasing order, and all of the women have chosen
composite numbers in increasing order. What is the probability that
she can choose a composite number in the set {2, 3, … , 100} that is
larger than any of the numbers chosen by the women and forces the sum
of all chosen numbers to be an integer multiple of 103?

Of course, the first part of the problem is to come up with an
algorithm that doesn't take forever. In a followup post, I will give
an example of a reasonably simple algorithm in the form of C code and
program notes. On my PC, the program completes in about 0.04 seconds.
The question is: can this be made to run in a reasonable time frame on
an HP calculator? The challenge, I think, is to avoid too many array
copies during stack manipulations. (There are times that I really
wished that RPL arrays had PostScript semantics, i.e. that when you
DUP an array, you DUP the reference, not the memory.)

So, time is of the essence, but your program actually has to calculate
the answer, not just push it on the stack and exit. In the spirit of
the contest, the probability need only be calculated as a real number.
But for extra credit (and to show off the capabilities of the later
models of the HP48 series), can the exact fraction be calculated?

Scott
--
Scott Hemphill hemphill(a)alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
From: Scott Hemphill on 30 Nov 2009 14:11
Scott Hemphill <hemphill(a)hemphills.net> writes:

[snip]

> In a followup post, I will give
> Of course, the first part of the problem is to come up with an
> algorithm that doesn't take forever.

Here's the promised followup.

The problem:

Thirteen men and nineteen women are placed in line so that 3 women are
at the front of the line, 4 women are at the end of the line, and men
and women alternate in the line from the fourth position to the 29th
position, with a man standing in the 4th position. Each of the first
31 people choose a random number in the set {2, 3, … , 100}. You don't
know their choices, but you know that the 32nd person knows their
choices, and you hear her say that all of the men have chosen prime
numbers in increasing order, and all of the women have chosen
composite numbers in increasing order. What is the probability that
she can choose a composite number in the set {2, 3, … , 100} that is
larger than any of the numbers chosen by the women and forces the sum
of all chosen numbers to be an integer multiple of 103?

The program:
========================================================================
#include <stdio.h>

#define NM 13 // number of men
#define NW 19 // number of women
#define NP 25 // number of choices for men
#define NC 74 // number of choices for women
#define MOD 103 // sum of choices must be a multiple of MOD

#define max(x,y) ((x) > (y) ? (x) : (y))

int primes[NP+1] = { // choices for men
0, 2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97
};

int composites[NC+1] = { // choices for women
0, 4, 6, 8, 9, 10, 12, 14, 15, 16,
18, 20, 21, 22, 24, 25, 26, 27, 28, 30,
32, 33, 34, 35, 36, 38, 39, 40, 42, 44,
45, 46, 48, 49, 50, 51, 52, 54, 55, 56,
57, 58, 60, 62, 63, 64, 65, 66, 68, 69,
70, 72, 74, 75, 76, 77, 78, 80, 81, 82,
84, 85, 86, 87, 88, 90, 91, 92, 93, 94,
95, 96, 98, 99, 100
};

double table[max(NP,NC)+1][MOD]; // number of ways choices can be made
// (see program notes)

// update table for a new person
// nums is primes for men, composites for women
// lastrow is number of choices in nums (see program notes)

void update(int *nums, int lastrow)
{
int i, j, k;
for (i = lastrow; i >= 0; i--) {
for (j = 0; j < MOD; j++) {
if (table[i][j]) {
for (k = i+1; k <= lastrow; k++) {
table[k][(j+nums[k])%MOD] += table[i][j];
}
table[i][j] = 0;
}
}
}
}

// main algorithm
// total is the number of ways that all of the men and all but one of
// the women can choose numbers in the proper order
// count is the number of those ways where the last woman can choose
// a number in order such that the total is a multiple of MOD. (see
// program notes)

int main(int argc, char *argv[])
{
double count, total;
int i, j, k;
table[0][0] = 1; // step 1
for (i = 0; i < NM; i++) update(primes, NP); // step 2
for (i = 1; i <= NP; i++) { // step 3
for (j = 0; j < MOD; j++) {
table[0][j] += table[i][j];
table[i][j] = 0;
}
}
for (i = 0; i < NW-1; i++) update(composites, NC); // step 4
for (i = 0, total = 0; i <= NC; i++) { // step 5
for (j = 0; j < MOD; j++) total += table[i][j];
}
for (i = 0, count = 0; i <= NC; i++) { // step 6
for (j = 0; j < MOD; j++) {
if (table[i][j]) {
for (k = i+1; k <= NC; k++) {
if ((j+composites[k])%MOD == 0) {
count += table[i][j];
break;
}
}
}
}
}
printf("total = %.17g, count = %.17g\n", total, count); // step 7
printf("probability = %.17g\n", count/total);
return 0;
}
========================================================================
Program notes:

I originally wrote this program with no comments at all. I then wrote
a file with explanatory notes. I then started commenting the program,
but couldn't bring myself to expand the terse code with all of this
text:

"NM" is the number of men and "NW" is the number of women. "NP" is
the number of choices that the men have and "NC" is the number of
choices that the women have. The total of all the choices has to be a
multiple of "MOD".

"primes" contains a list of the men's choices, sorted in the order in
which choices must be made. It corresponds with the rows of "table",
so the first location is a placeholder. "composites" contains a list
of the women's choices, sorted in the order in which choices must be
made. It also corresponds with the rows of "table", so the first
location is a placeholder.

"table" is used to tabulate the number of ways men's or women's
choices may be made. It is used first to tabulate the men's choices
and then to tabulate the women's choices. The row corresponds to the
index of the last choice made by a member of the group being
tabulated. The column corresponds to the remainder of the total of
all the choices when divided by MOD. If no choices have yet been
made, then the entries of "table" will be zero except for row zero,
which will contain the number of ways that the total can have the
various remainders modulo MOD.

"update" uses the contents of "table" to construct a new table with
the number of ways that the previous people and a new person can make
valid choices. "nums" is either "primes" for the men, or "composites"
for the women. "lastrow" is the number of entries in this person's
table of choices, and is also the number of the last row that we look
at and/or update in "table". Since the new person must choose a
number later in the list than the previous person, each row in the
table will affect only later rows in the new table. Therefore, we can
update "table" in place, as long as we process each row in reverse
order.

The algorithm in "main" proceeds as follows:

1. Initialize table to say that there is only one way to start, with a
total which is zero modulo MOD.

2. Call "update" once for each of the men.

3. All the entries in "table" now represent valid choices for the men
(no matter which row they are in), so move the totals to row zero and
zero the rest of the table in preparation for the women.

4. Call "update" once for each of the women except the last.

5. All the entries in "table" now represent the total number of events
we wish to count. Add them together into "total". If the program
executes correctly, this number should be C(NC,NW-1)*C(NP,NM). For
the problem values this should be a floating point approximation of
377893220518123106330800.

6. For each of the non-zero entries in "table", if there is now a way
for the last woman to choose a later number in "composites" that makes
the total equal to zero modulo MOD, then accumulate that entry into
"count". For the problem parameters, the "break" in the inner loop is
not necessary, but if MOD were less than the maximum value in
composites, there might be more than one way to make the total equal
to zero modulo MOD, and we would overcount unless we broke out of the
loop. In fact, in the original version of this program, instead of
the nested loop, I just called "update" again for the last woman, and
summed the entries in column zero of "table". This works as long as
you can't possibly overcount.

7. Print the results.

Scott
--
Scott Hemphill hemphill(a)alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
From: Bastian Erdnuess on 1 Dec 2009 01:46
Scott Hemphill <hemphill(a)hemphills.net> wrote:

> Thirteen men and nineteen women are placed in line so that 3 women are
> at the front of the line, 4 women are at the end of the line, and men
> and women alternate in the line from the fourth position to the 29th
> position, with a man standing in the 4th position. Each of the first
> 31 people choose a random number in the set {2, 3, … , 100}. You don't
> know their choices, but you know that the 32nd person knows their
> choices, and you hear her say that all of the men have chosen prime
> numbers in increasing order, and all of the women have chosen
> composite numbers in increasing order. What is the probability that
> she can choose a composite number in the set {2, 3, … , 100} that is
> larger than any of the numbers chosen by the women and forces the sum
> of all chosen numbers to be an integer multiple of 103?

Is 'increasing' the same as 'strictly increasing'? I.e. is it possible
that two did choose the same number or not? I'll assume not.

How exact does it need to be? Without a calculator I would have said
that after the first 31 picked their numbers there are 74 - 18 = 56
possible composite numbers for Ms. 32 left, each with a chance of 1/103
to fill up the sum to the next multiple of 103. Furthermore, the
chances are 1/19 that this is the biggest composite number chosen.

Thus, the chances are about 56/103/19 ~ 2.71% that Ms. 32 can make her
choice.

Bastian
From: Scott Hemphill on 1 Dec 2009 08:50
earthnut(a)web.de (Bastian Erdnuess) writes:

> Scott Hemphill <hemphill(a)hemphills.net> wrote:
>
>> Thirteen men and nineteen women are placed in line so that 3 women are
>> at the front of the line, 4 women are at the end of the line, and men
>> and women alternate in the line from the fourth position to the 29th
>> position, with a man standing in the 4th position. Each of the first
>> 31 people choose a random number in the set {2, 3, … , 100}. You don't
>> know their choices, but you know that the 32nd person knows their
>> choices, and you hear her say that all of the men have chosen prime
>> numbers in increasing order, and all of the women have chosen
>> composite numbers in increasing order. What is the probability that
>> she can choose a composite number in the set {2, 3, … , 100} that is
>> larger than any of the numbers chosen by the women and forces the sum
>> of all chosen numbers to be an integer multiple of 103?
>
> Is 'increasing' the same as 'strictly increasing'? I.e. is it possible
> that two did choose the same number or not? I'll assume not.

Yes, I also assumed that increasing meant "strictly increasing".

> How exact does it need to be? Without a calculator I would have said
> that after the first 31 picked their numbers there are 74 - 18 = 56
> possible composite numbers for Ms. 32 left, each with a chance of 1/103
> to fill up the sum to the next multiple of 103. Furthermore, the
> chances are 1/19 that this is the biggest composite number chosen.
>
> Thus, the chances are about 56/103/19 ~ 2.71% that Ms. 32 can make her
> choice.

You have arrived at answer that is approximately correct. It's easy
to show that this can't be the exact answer, however. To get the
exact answer (I think!) I enumerated all the ways the choices could be
made. I did this with a C program on my PC, but I believe that it
could be done on in RPL on an HP48 series calculator.

Scott
--
Scott Hemphill hemphill(a)alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
From: Bastian Erdnuess on 1 Dec 2009 10:27
Scott Hemphill <hemphill(a)hemphills.net> wrote:

> earthnut(a)web.de (Bastian Erdnuess) writes:
>
> > Thus, the chances are about 56/103/19 ~ 2.71% that Ms. 32 can make her
> > choice.
>
> You have arrived at answer that is approximately correct. It's easy
> to show that this can't be the exact answer, however. To get the
> exact answer (I think!) I enumerated all the ways the choices could be
> made. I did this with a C program on my PC, but I believe that it
> could be done on in RPL on an HP48 series calculator.

I didn't took my time to read your code, yet, but I almost cannot
beleave that you really enumerated all possibilities. The men are no
problem, they can choose their numbers in (25 over 13) ~ 5 million
different ways. But the first 18 women can choose their numbers already
in (74 over 18) ~ 73 * 10^15 different ways and it would take months to
enumerate them all, even on a modern cpu.

Can you explain how your program works in some more human readable way?

Bastian
 |  Next  |  Last
Pages: 1 2 3 4 5
Prev: mini-challenge from UH contest
Next: Analogon to 28S' FORM on the HP 50g