Probability question (1 Viewer)

[enak]

I don't have the answer to this, so maybe 0o0 could answer this

Players 1, 2, 3, , n are seated around a table and each has a single penny. Player 1 passes a penny to Player 2, who then passes two pennies to Player 3. Player 3 then passes one penny to Player 4, who passes two pennies to Player 5, and so on, players alternately passing one penny or two to the next player who still has some pennies. A player who runs out of pennies drops out of the game and leaves the table. Find an infinite set of numbers n for which some player ends up with all n pennies.

Maybe turtle or dr buchanan has seen it?

 

[freaking_out]

Originally posted by enak

Maybe turtle or dr buchanan has seen it?

y?....has this got to do with the "riemens hypothesis".

 

[Affinity]

no, this is a combinatorics question,

so the first person doesn't get out automatically,

and a person only gets out if he/she has only 1 penny and have to pass 2? so he/she passes the penny to the next person and gets out? and in this case does the person who received 1 penny pass 1 or 2 to the next person?

 

[enak]

Originally posted by freaking_out
y?....has this got to do with the "riemens hypothesis".

no

Originally posted by Affinity
no, this is a combinatorics question,

so the first person doesn't get out automatically,

and a person only gets out if he/she has only 1 penny and have to pass 2? so he/she passes the penny to the next person and gets out?

I'm assuming the first person would get out automatically, since passes his/her only penny to person 2, and person 2 is also out because s/he has to pass their two pennies to person 3 and so forth.

 

[Archman]

haven't worked this out yet, but it seems that a stalemate will only occur when there are an odd number of people left, each with at least 3 pennies. Now have to work out, for which n, this situation will occur.

 

[Affinity]

{x: x= 2^n + 1 }
I will write up the proof tomorrow.

outline:

basically after 1 round (last person gets his 2 coins) the configuration would be something like:

3,2,2,2,2,2,2,2,2,....2 in a circle and 2^(n-1) persons altogether.

and the guy with 3 coins is to pass 1 to the next guy so on..

when we get back to this person it would be

4,1,3,1,3,1,3,.....,1 in a circle,

again it would be

5,4,4,4,4..... with 2^(n-2) persons remaining , the person with 5 starts passing 1 again..


continuing this, it will reach

h,k,k,k in a circle, where the person with h is to pass 1 coin

will get down to the 2 persons, and 1 eventually.

turtle probably seen it.. I vaguely remember seeing something like this. somewhere sometime in some question on some page of some book.

 

[Affinity]

Proof:

RESULT 1:

consider the situation where

1.) there are 2^n persons still in the game (n is integer)
2.) the first person(who is about to pass) has 2 or more coins
3.) the person about to pass is to pass 1 coin to the next person
4.) everyone except the person who is about to pass the coin each has equal number of coins.

going around the circle back to the person who started, the 1st, 3rd, 5th etc person after the person passing will have 1 penny deducted from their hand because they each receive 1 from the person before them and give 2 to the next.

the 2nd, 4th, 6th etc person would have 1 coin added to their hand because they receive 2 and give 1 away.

the person who started passing would receive 2 coins from the 'last' person in the circle because the circle has a even number of people. and now it's that person's turn to pass 1 coin again

the net effect of this round is equivalent to every second person after the passer giving one coin to the person next to them
such as:

5,3,3,3,3,3,3,3 (in a circle) becomes 6,2,4,2,4,2,4,2 (in a circle)

continuing this will eventually eliminate half of the people in the circle in some round. (every second guy will eventually drop down to 1, then the next round they will be gone)

now we're back to a situation again satisfying the 4 points listed above, but now we only have 2^(n-1) persons in the game.

eventually there will be 2^1 = 2 left in the game.

and with 2, the coins will always go to one person.

BACK TO THE ORIGINAL QUESTION:

if we start with 2^m + 1 in the circle,

and we start passing ...
the first 2 will be out
the 4th,6th, ... will be out
3rd,5th,... will end up with 2 coins
and the 'last' person in the circle will have 3 by receiving 2 from the previous person before he passes.

this is a configuration which satisfies the conditions for RESULT 1, so applying that

{x:x=2^n + 1 } is a set of infinite solutions

 

[Affinity]

enak, where did you see the question?

 

[enak]

It was a sample problem from the Putnam maths comp for uni students in america, so good job

 

[Harimau]

Originally posted by enak
It was a sample problem from the Putnam maths comp for uni students in america, so good job

Mmm now i remember where i saw this one. Did you see the question about the basketball hoops and how many times the person can get in exactly 50 times?

 

[Affinity]

by the way {x:x=2^n + 2} are also solutions

 

[underthesun]

Giving us questions from a math comp that have a mean mark of 1? sheesh you silly you

Seems like some 4unit student from this forum should really go there, can probably win a nobel prize!

 

[Affinity]

it's a median mark of 1.. mean would be higher

 

[enak]

Hmm, I wonder what the mean mark is.

Let me find another one for you affinity

1.
Given any five points on a sphere, show that some four of them must lie on a closed hemisphere.

2.
In Determinant Tic-Tac-Toe, Player 1 enters a 1 in an empty 3 3 matrix. Player 0 counters with a 0 in a vacant position, and play continues in turn until the 3 3 matrix is completed with five 1s and four 0s. Player 0 wins if the determinant is 0 and player 1 wins otherwise. Assuming both players pursue optimal strategies,
who will win and how?

Should keep you busy for the moment

Harimau, this one?
Shanille OKeal shoots free throws on a basketball court. She hits the first and misses the second, and thereafter the probability that she hits the next shot is equal to the proportion of shots she has hit so far. What is the probability she hits exactly 50 of her first 100 shots?

 

[Affinity]

question 1:

pick 2 points
draw the big circle through it.

you have 3 points remaining to place in the 2 hemispheres, so.. one of the hemispheres must have 2..
these 2 points + teh 2 on the big circle will give 4.

done

 

[Affinity]

question 2
player 0 wins

strategy:

basically you want 3 0s in a row/column or 4 0s each occupying a corner of a rectangle:

by '4 at corners of rectangle' it could be:

0 1 0------0 0 1------1 0 0------0 1 0
0 1 0------0 0 1------1 1 1------1 1 1
1 1 1------1 1 1------1 0 0------0 1 0

the '-' are just spaces

etc.


3 0s in a row/column is obviously gives a determinant of 0

for the second case, expanding the determinant about a column containing 2 0s

you will get
[1 0] * (+/- 1) = 0 * (+/- 1) = 0
[1 0]

(or:
[0 1]
[0 1]
)

anyway, to show that this can be forced:

MOVE 1:

place 0 so that it's not on the same row/column as the 1.

MOVE 2:

If you can, place the 0 on the same row/column as your first 0, and if possible, avoid placing it in a row / column with 1s
This would force player 1 to fill in the place to stop player 0 from completing 3 in a row.

MOVE 3:

now, there are 2 empty spaces on the board which will form a rectangle with the 2 with 0s. one of them will also be in a line with one of the 0s and another empty square

place a 0 there forking player 1.

MOVE 4

complete the row of 3 0s or the rectangle

win.