Author |
Topic: Whimsical Teacher (Read 1320 times) |
|
spanchap
Newbie
Suresh
Gender: 
Posts: 40
|
 |
Whimsical Teacher
« on: Mar 23rd, 2007, 3:56pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
Whiskey Tango Foxtrot
Uberpuzzler
Sorry Goose, it's time to buzz a tower.
Gender:
Posts: 1672
|
|
Re: Whimsical Teacher
« Reply #1 on: Mar 23rd, 2007, 4:15pm » |
Quote Modify
|
If everyone says 1, don't 90% get an A?
|
|
IP Logged |
"I do not feel obliged to believe that the same God who has endowed us with sense, reason, and intellect has intended us to forgo their use." - Galileo Galilei
|
|
|
spanchap
Newbie
Suresh
Gender:
Posts: 40
|
|
Re: Whimsical Teacher
« Reply #2 on: Mar 23rd, 2007, 4:28pm » |
Quote Modify
|
" 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.
|
|
IP Logged |
|
|
|
Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender:
Posts: 460
|
|
Re: Whimsical Teacher
« Reply #3 on: Mar 23rd, 2007, 7:04pm » |
Quote Modify
|
why no 1,1 then 2,2... to 10,10 and 50% will pass
|
|
IP Logged |
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?
|
|
|
Whiskey Tango Foxtrot
Uberpuzzler
Sorry Goose, it's time to buzz a tower.
Gender:
Posts: 1672
|
|
Re: Whimsical Teacher
« Reply #4 on: Mar 23rd, 2007, 7:16pm » |
Quote Modify
|
on Mar 23rd, 2007, 3:56pm, 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.
|
|
IP Logged |
"I do not feel obliged to believe that the same God who has endowed us with sense, reason, and intellect has intended us to forgo their use." - Galileo Galilei
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Whimsical Teacher
« Reply #5 on: Mar 23rd, 2007, 7:46pm » |
Quote Modify
|
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).
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
JiNbOtAk
Uberpuzzler
Hana Hana No Mi
Gender:
Posts: 1187
|
|
Re: Whimsical Teacher
« Reply #6 on: Mar 23rd, 2007, 7:47pm » |
Quote Modify
|
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 ? 
|
|
IP Logged |
Quis custodiet ipsos custodes?
|
|
|
spanchap
Newbie
Suresh
Gender:
Posts: 40
|
|
Re: Whimsical Teacher
« Reply #7 on: Mar 23rd, 2007, 8:52pm » |
Quote Modify
|
on Mar 23rd, 2007, 7:47pm, 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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Whimsical Teacher
« Reply #8 on: Mar 23rd, 2007, 9:08pm » |
Quote Modify
|
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.
|
| « Last Edit: Mar 23rd, 2007, 9:13pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Whimsical Teacher
« Reply #9 on: Mar 25th, 2007, 7:49am » |
Quote Modify
|
Running a small simulation for n=6 and n=8, I only ever get 50%
And you might as well all say - .
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Whimsical Teacher
« Reply #10 on: Mar 25th, 2007, 8:04am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Whimsical Teacher
« Reply #11 on: Mar 25th, 2007, 11:36am » |
Quote Modify
|
on Mar 25th, 2007, 7:49am, 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!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Whimsical Teacher
« Reply #12 on: Mar 25th, 2007, 11:40am » |
Quote Modify
|
on Mar 25th, 2007, 11:36am, 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. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Whimsical Teacher
« Reply #13 on: Mar 25th, 2007, 1:02pm » |
Quote Modify
|
on Mar 25th, 2007, 8:04am, 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?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Whimsical Teacher
« Reply #14 on: Mar 25th, 2007, 1:11pm » |
Quote Modify
|
on Mar 25th, 2007, 1:02pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender:
Posts: 460
|
|
Re: Whimsical Teacher
« Reply #15 on: Mar 25th, 2007, 2:21pm » |
Quote Modify
|
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]
|
|
IP Logged |
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Whimsical Teacher
« Reply #16 on: Mar 25th, 2007, 2:31pm » |
Quote Modify
|
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:
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.
|
| « Last Edit: Mar 25th, 2007, 2:36pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Whimsical Teacher
« Reply #17 on: Mar 25th, 2007, 8:52pm » |
Quote Modify
|
Concerning the original problem: For a given strategy, let pk be the probability that the kth student got a C, and let N > 1 be the total number of students (20, in our case).
Note that by the rules, pk+1 = pkak + (1-pk)(N-1)/N, where ak = 0 if the k+1st student gives the same response as the kth, and equals 1 otherwise. In particular, pk+1 >= (1-pk)(N-1)/N.
The expected number P of C's is the just the sum of the pk. Letting p0 = 0, we have:
P = k=1..N pk >= (N-1)/N k=1..N (1-pk-1) = (N-1)/N [ N - (P - pN)] >= (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 <= N2/(2N-1). For N = 20, the highest expectation for the number of A's is at most 400/39 = 10.2564...
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Whimsical Teacher
« Reply #18 on: Mar 25th, 2007, 10:45pm » |
Quote Modify
|
on Mar 25th, 2007, 8:52pm, Icarus wrote:| Note that by the rules, pk+1 = pkak + (1-pk)(N-1)/N, where ak = 0 if the k+1st student gives the same response as the kth, 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)r2 + (N-2)r3 - ... + (-1)N-1rN
= Nr/(1+r) + (1-(-r)N)(r/(1+r))2,
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-pk).
|
| « Last Edit: Mar 25th, 2007, 10:47pm by Eigenray » |
IP Logged |
|
|
|
Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender:
Posts: 460
|
|
Re: Whimsical Teacher
« Reply #19 on: Mar 26th, 2007, 9:30am » |
Quote Modify
|
Icurus, thank you, but it came out how ai wante, no offense. I barely use it anyways
|
|
IP Logged |
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Whimsical Teacher
« Reply #20 on: Mar 26th, 2007, 10:04am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Whimsical Teacher
« Reply #21 on: Mar 26th, 2007, 3:36pm » |
Quote Modify
|
on Mar 25th, 2007, 10:45pm, Eigenray wrote:| The problem is that student k+1 guessing wrong (with probability r) is not independent of student k passing (with probability 1-pk). |
|
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?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Whimsical Teacher
« Reply #22 on: Mar 26th, 2007, 5:01pm » |
Quote Modify
|
on Mar 26th, 2007, 3:36pm, 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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Whimsical Teacher
« Reply #23 on: Mar 26th, 2007, 9:04pm » |
Quote Modify
|
Of course. I overlooked that the pre-decided strategy couples the events. 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print