wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Whimsical Teacher
        
(Message started by: spanchap on Mar 23^rd, 2007, 3:56pm)

Title: Whimsical Teacher
Post by spanchap on Mar 23^rd, 2007, 3:56pm

I am a whimsical high school teacher with 20 very bright (high IQ) students in my class. I assign each student a unique number (from 1 thru 20) but do not tell them which student is assigned which number.

I offer the following proposition to the students:

I will ask each one of you (in alphabetical order) to come visit me in the teacher's room. When you come and meet me, you have to utter a number from 1 thru 20. If your number satisfies certain conditions, I will ensure you get an "A" grade in my class else you will get a "C" grade.

The conditions for getting an "A" grade are:

1. You uttered the number secretly assigned to you
2. You uttered the number which was uttered by the previous student provided the previous student did not qualify for an "A" grade

You can talk among yourselves before the first student visits me. Also you will have no knowledge of the grade any other student will get.

What is the strategy that the students should follow to maximise the number of students getting "A" grade.

Contributor's note: Sorry if this puzzle sounds "clunky" - I just made this up 5 minutes ago. It is trivial to ensure at least 50% of the students get "A" grade - for example if everybody uttters "1" at least 50% will get "A" grade

Title: Re: Whimsical Teacher
Post by Whiskey Tango Foxtrot on Mar 23^rd, 2007, 4:15pm

If everyone says 1, don't 90% get an A?

Title: Re: Whimsical Teacher
Post by spanchap on Mar 23^rd, 2007, 4:28pm

" If everyone says 1, don't 90% get an A?

No. You will not get credit for saying 1 if the previous student said 1 and qualified for "A" grade.

Title: Re: Whimsical Teacher
Post by tiber13 on Mar 23^rd, 2007, 7:04pm

why no 1,1 then 2,2... to 10,10 and 50% will pass

Title: Re: Whimsical Teacher
Post by Whiskey Tango Foxtrot on Mar 23^rd, 2007, 7:16pm

on 03/23/07 at 15:56:43, spanchap wrote:

provided the previous student did not qualify for an "A" grade

Of course, of course. Silly me, I missed this part. 50% it is. And I believe tiber has the optimal solution, as any more than two of the same guesses in a row cannot increase your chances.

Title: Re: Whimsical Teacher
Post by Icarus on Mar 23^rd, 2007, 7:46pm

If these really are bright kids, then 10 are going to realize that this strategy guarantees the other half of the class gets an A, while they have only a 5% chance of getting one themselves. And this distinction is based on their names, and not in any way on their performance.

On the other hand, other strategies may give a lower total percentage, but increase their own chances. In particular, if the students were to decide in group to follow the strategy tiber13 suggests, I would expect the resulting sequence to be 1,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10, as all but the first of the odd ranked students realizes it is to their own advantage to cheat.

Of course, the even ranked students will in turn realize that surely this is going to happen, and adjust their own responses accordingly. Which will be realized by the odd students, which will be realized by the even students, etc. And of course Allen Aaron is going to be quite P.O.ed about the whole thing!

Therefore, a workable optimal solution must equalize the probabilities for all students as much as possible (except perhaps for poor Allen, who'll probably be in the back of the line for the hat-execution party too).

Title: Re: Whimsical Teacher
Post by JiNbOtAk on Mar 23^rd, 2007, 7:47pm

I think the probability is a shade better than 50%, since there is the chance of the students fulfilling the first condition as well..

Or is that nullified as well ? :-/

Title: Re: Whimsical Teacher
Post by spanchap on Mar 23^rd, 2007, 8:52pm

on 03/23/07 at 19:47:51, JiNbOtAk wrote:

I think the probability is a shade better than 50%, since there is the chance of the students fulfilling the first condition as well..

Or is that nullified as well ? :-/

I do not think so.

If a student fulfils the first condition and is odd numbered, then the even student gets a "C". In this case the "A" and "C" gets flipped between the two, but still it is one "A" for two students.

If a student fulfils the first condition and is even numbered, then the even student gets a "A" which he/she would any way have got as the previous student would have got a "C" with that answer.

Title: Re: Whimsical Teacher
Post by Icarus on Mar 23^rd, 2007, 9:08pm

By tiber13's strategy, the odd ranked students do not get a chance to satisfy condition 2 at all. Their only hope is to satisfy condition 1. Since there are 20 numbers and no information to choose any one over the others, the odds that the number they say will match their own is 1/20 = 5%.

P.S. - I didn't say any of this as a criticism of tiber13's strategy, which meets the actual conditions listed in the puzzle (except for possibly not being optimal - that hasn't been shown). Rather, I wanted to point out that the puzzle has a deeper level, if you also assume that the kids are not selfless.

Title: Re: Whimsical Teacher
Post by towr on Mar 25^th, 2007, 7:49am

Running a small simulation for n=6 and n=8, I only ever get 50%
And you might as well all say -http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif.

Title: Re: Whimsical Teacher
Post by rmsgrey on Mar 25^th, 2007, 8:04am

Everyone saying "1" gives even numbered kids the advantage early on, but the probabilities even out over the run.

It looks like N/2 is the best you can do with an even number, N, of students - apart from the unlucky Mr Aaron, each student's chances individually are maximised by picking the same value as the student before, and if each student does better, the final score should come out better...

With an odd number, you can do slightly better than half

Title: Re: Whimsical Teacher
Post by Icarus on Mar 25^th, 2007, 11:36am

on 03/25/07 at 07:49:37, towr wrote:

Running a small simulation for n=6 and n=8, I only ever get 50%.

By either tiber13's strategy or the "everybody says 1" strategy, or any other where even students repeat the value of their predecessors, exactly one of each pair of students is successful. If the first of the pair fails, the second succeeds, and vice versa.

Quote:

And you might as well all say -\pi.

The odd-numbered students strongly beg to differ!

Title: Re: Whimsical Teacher
Post by towr on Mar 25^th, 2007, 11:40am

on 03/25/07 at 11:36:44, Icarus wrote:

The odd-numbered students strongly beg to differ!

As far as maximizing the number of A's is concerned, they can go suck an egg. :P

Title: Re: Whimsical Teacher
Post by Icarus on Mar 25^th, 2007, 1:02pm

on 03/25/07 at 08:04:15, rmsgrey wrote:

Everyone saying "1" gives even numbered kids the advantage early on, but the probabilities even out over the run.

They get closer, but only Yolanda Young and Zephaniah Zweiner have an equal chance of getting an A. For all preceding pairs, the odds are better if your number is even.;)

Still, I think that because of the reasoning that I outlined above that would occur if they decided to use tiber13's strategy, "everybody says 1" is the strategy that will end up being used. It fairs no worse than any other "evens repeat their predecessors" strategy, while giving the odds their best shot. And I do not think it is possible to find a strategy whose expectation exceeds 50%.

On the other hand, "Everybody says 1" could actually be quite profitable for Mr Aaron. No matter what he says, his odds are still only 5%, but suppose that a certain group, feeling that the agreed-upon "everybody says 1" strategy unfairly discriminates against them, should offer a bribe to Allen to say "2"...

--------------------------------------------------

Now, what happens if the students know who before them got As?

Title: Re: Whimsical Teacher
Post by towr on Mar 25^th, 2007, 1:11pm

on 03/25/07 at 13:02:40, Icarus wrote:

Now, what happens if the students know who before them got As?

Well, you can improve your chances a bit by not repeating a number anyone got an A on.

Title: Re: Whimsical Teacher
Post by tiber13 on Mar 25^th, 2007, 2:21pm

Yippee, [/i] Tiber13 looks up optimal in the online dictoinary[i] i have a nice solution,[/b][/i][/u] In the hard forum[b][i][u]

Title: Re: Whimsical Teacher
Post by Icarus on Mar 25^th, 2007, 2:31pm

When you use the formatting tag buttons, they insert both the opening and closing tag. You need to move the cursor back and put your text in between the two tags. If you don't, a lot of extra garbage shows up.

For example, clicking the I button inserts [i][/i] in your post. What you want to do is move back before the [/i] to write:

Code:

[i]Hello![/i]

which then shows as:
Hello!

One other beneficial trick: If you see somebody else do something, and you want to know how it was done, "Quote" their post. You will get the entire post as entered, except for any quotes within it (YaBB doesn't do nested quotes). Once you have found what you needed to know, just use the "back" button on your browser to back out of the reply page without posting.

Title: Re: Whimsical Teacher
Post by Icarus on Mar 25^th, 2007, 8:52pm

Concerning the original problem: For a given strategy, let p_k be the probability that the k^th student got a C, and let N > 1 be the total number of students (20, in our case).

Note that by the rules, p_k+1 = p_ka_k + (1-p_k)(N-1)/N, where a_k = 0 if the k+1^st student gives the same response as the k^th, and equals 1 otherwise. In particular, p_k+1 >= (1-p_k)(N-1)/N.

The expected number P of C's is the just the sum of the p_k. Letting p₀ = 0, we have:
P =http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=1..N p_k >= (N-1)/N http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=1..N (1-p_k-1) = (N-1)/N [ N - (P - p_N)] >= (N-1/N)(N - P).
Solving the inequality gives P >= N(N-1)/(2N-1).

The expected number of A's is just N-P <= N²/(2N-1). For N = 20, the highest expectation for the number of A's is at most 400/39 = 10.2564...

Title: Re: Whimsical Teacher
Post by Eigenray on Mar 25^th, 2007, 10:45pm

on 03/25/07 at 20:52:57, Icarus wrote:

Note that by the rules, p_k+1 = p_ka_k + (1-p_k)(N-1)/N, where a_k = 0 if the k+1^st student gives the same response as the k^th, and equals 1 otherwise.

I read that and went so far as to show that the smallest P could be is

r + r(1-r) + r(1-r(1-r)) + r(1-r(1-r(1-r))) + ...
= Nr - (N-1)r² + (N-2)r³ - ... + (-1)^N-1r^N
= Nr/(1+r) + (1-(-r)^N)(r/(1+r))²,

where r = 1-1/N.

...But then I realized that this is wrong even for N=2 :-/. The problem is that student k+1 guessing wrong (with probability r) is not independent of student k passing (with probability 1-p_k).

Title: Re: Whimsical Teacher
Post by tiber13 on Mar 26^th, 2007, 9:30am

Icurus, thank you, but it came out how ai wante, no offense. I barely use it anyways

Title: Re: Whimsical Teacher
Post by Grimbal on Mar 26^th, 2007, 10:04am

If the students (we?) are so smart, they should complain about the nonsensical scoring of their teacher, get him fired and all get the A they deserve.

That was the "I am completely out of the box" contribution.

Title: Re: Whimsical Teacher
Post by Icarus on Mar 26^th, 2007, 3:36pm

on 03/25/07 at 22:45:22, Eigenray wrote:

The problem is that student k+1 guessing wrong (with probability r) is not independent of student k passing (with probability 1-p_k).

I don't see this. Student k+1 chooses his number from 1-20 without any knowledge of k's success or failure. How does k's success affect the probability that k+1 is correct?

Title: Re: Whimsical Teacher
Post by Eigenray on Mar 26^th, 2007, 5:01pm

on 03/26/07 at 15:36:44, Icarus wrote:

I don't see this. Student k+1 chooses his number from 1-20 without any knowledge of k's success or failure. How does k's success affect the probability that k+1 is correct?

In the simplest case, suppose N=2, and both students guess 1. The probability that the first student passes is 1/2. The probability that the second student guesses inorrectly is also 1/2. But these are the same event, so the probability that the second student fails is 1/2, not 1/2 * 1/2.

Title: Re: Whimsical Teacher
Post by Icarus on Mar 26^th, 2007, 9:04pm

Of course. I overlooked that the pre-decided strategy couples the events. :-[