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 1hour 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 < NW1; 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,NW1)*C(NP,NM). For the problem values this should be a floating point approximation of 377893220518123106330800. 6. For each of the nonzero 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: minichallenge from UH contest Next: Analogon to 28S' FORM on the HP 50g 