Author |
Topic: Painted Balls (Read 765 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Painted Balls
« on: Apr 11th, 2007, 10:22am » |
 Quote  Modify
|
A box contains n balls, each of a different colour. From the box you randomly choose a ball with your left hand and another ball with your right hand. You now paint the left-hand ball the same colour as the right-hand ball and replace both balls in the box. How many such turns would you expect to need before all of the balls in the box are the same colour?
|
|
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Painted Balls
« Reply #1 on: Apr 11th, 2007, 11:54am » |
Quote Modify
|
(n-1)2 ?
It sounds too good to be true, so probably is..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Painted Balls
« Reply #2 on: Apr 12th, 2007, 7:45am » |
Quote Modify
|
on Apr 11th, 2007, 11:54am, towr wrote:
Has it been posted before?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Painted Balls
« Reply #3 on: Apr 12th, 2007, 7:54am » |
Quote Modify
|
I don't think so. Although I recall a somewhat similar riddle with a different, but equally astonishing results In that problem you got multiplication of two numbers.
I'm still thinking how to prove this result in general though -- I just generalized from the first few examples (even though at first one of the results didn't correspond, but I found I made a mistake)
|
| « Last Edit: Apr 12th, 2007, 7:55am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Painted Balls
« Reply #4 on: Apr 13th, 2007, 9:22am » |
Quote Modify
|
on Apr 11th, 2007, 11:54am, towr wrote:(n-1)2 ?
It sounds too good to be true, so probably is.. |
|
It does sound too good to be true, but I've run tens of thousands of simulations for up to 20 or so balls, and your guess is looking right. All we need now is a proof... (just constructing a Markov chain for the 4 ball problem gives me a headache).
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Painted Balls
« Reply #5 on: Apr 13th, 2007, 12:25pm » |
Quote Modify
|
Maybe I am complicating matters (and I am definitely not helping  by the following):
isn't this: Given a complete graph of white edges. We pick an edge at random and colour it black. We are looking for the subgraph induced by the black edges to span all the nodes.
I would expect this to be standard by now.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Painted Balls
« Reply #6 on: Apr 13th, 2007, 3:22pm » |
Quote Modify
|
on Apr 11th, 2007, 11:54am, towr wrote:
What if n is even, with n/2 colours and 2 balls of each colour? 
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Painted Balls
« Reply #7 on: Apr 13th, 2007, 4:01pm » |
Quote Modify
|
on Apr 13th, 2007, 12:25pm, Aryabhatta wrote:Maybe I am complicating matters (and I am definitely not helping by the following):
isn't this: Given a complete graph of white edges. We pick an edge at random and colour it black. We are looking for the subgraph induced by the black edges to span all the nodes.
I would expect this to be standard by now.
|
|
Isn't the problem at hand a little bit more complicated? I'm not sure whether you are referring to a directed or an undirected graph.
Anyway, here the order in which the directed edges get colored and, moreover, the number of times they get colored play a crucial role.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Painted Balls
« Reply #8 on: Apr 13th, 2007, 5:23pm » |
Quote Modify
|
You are right Johan... the problem is more complicated than I stated.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Painted Balls
« Reply #9 on: Apr 14th, 2007, 7:14am » |
Quote Modify
|
on Apr 13th, 2007, 9:22am, Miles wrote:| (just constructing a Markov chain for the 4 ball problem gives me a headache). |
|
4 balls is still manageable.
There are only 5 states (1111, 211, 31, 22, 4) and only 31 and 22 can form a cycle.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Painted Balls
« Reply #10 on: Apr 14th, 2007, 11:51am » |
Quote Modify
|
4 I succeded early on. It is indeed 9.
I think even few more can be done relatively easily, but I don't think that help in the general solution.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Painted Balls
« Reply #11 on: May 4th, 2007, 12:29pm » |
Quote Modify
|
on Apr 11th, 2007, 11:54am, towr wrote:
Consider running the experiment backwards.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print