Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2012-05-19 23:30:00

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,172
Website

The Wrong Hats Problem

It has been many days since I last posted. Feeling cool to post again

Anyway,
            There had been eight men and eight hats. They were so much drunk that they could not recognise their own hats. So they picked them up in a random manner. Now what is the chance that no man will choose his own hat?
            Of Course the first step is to find the factorial of 8 which is equal to the number of ways they can pick up the hats in. But it is such a large number that it would take years to write all of them down?

Can You give me the answer????


I know the answer but I dont know how to derive it. So a help would be nice


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#2 2012-05-19 23:41:21

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

Re: The Wrong Hats Problem

Hi;


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#3 2012-05-19 23:47:48

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,172
Website

Re: The Wrong Hats Problem

How do you get it?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#4 2012-05-19 23:49:32

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: The Wrong Hats Problem

If I am correct,than this is the derangement problem for 8 elements. I think you can find it on Wikipedia.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#5 2012-05-19 23:51:26

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

Re: The Wrong Hats Problem

Yes, this is a derangement problem. You can first use the approximation of

There are many formulas to generate the number of derangements.

http://en.wikipedia.org/wiki/Derangement


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#6 2012-05-19 23:58:22

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,172
Website

Re: The Wrong Hats Problem

Thnks I will read the article but will you explain what is approximation of 1/e?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#7 2012-05-19 23:59:19

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

Re: The Wrong Hats Problem

As n approaches infinity the probability of a derangement approaches 1 / e.

http://en.wikipedia.org/wiki/Derangement


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#8 2012-05-20 00:10:15

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,172
Website

Re: The Wrong Hats Problem

http://upload.wikimedia.org/wikipedia/en/math/3/f/6/3f619a61786028a59a524136391f52f0.png

How do you prove the above?
Please explain step by step
Can't Understand
sad


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#9 2012-05-20 00:17:02

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

Re: The Wrong Hats Problem

Hi;

I am sorry but I can not see that picture clearly.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#10 2012-05-20 00:20:24

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: The Wrong Hats Problem

Hi bobbym

It says !n=(n-1)*(!(n-1)+!(n-2))

Last edited by anonimnystefy (2012-05-20 00:20:43)


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#11 2012-05-20 00:21:22

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,172
Website

Re: The Wrong Hats Problem

The formula is:
!n=(n-1) (!(n-1) + !(n-2))

Last edited by Agnishom (2012-05-20 00:21:58)


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#12 2012-05-20 00:25:28

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

Re: The Wrong Hats Problem

Hi Agnishom;

That is the recurrence relation for the number of derangements. Did you read this:

http://en.wikipedia.org/wiki/Derangement

About half way down the page they will describe the process. It is difficult.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#13 2012-05-20 00:34:12

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,172
Website

Re: The Wrong Hats Problem

They wrote:

Suppose that there are n persons numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as his/her number. Let us assume that first person takes the hat i. There are n − 1 ways for the first person to choose the number i. Now there are 2 options:

1.    Person i does not take the hat 1. This case is equivalent to solving the problem with n − 1 persons n − 1 hats: each of the remaining n − 1 people has precisely 1 forbidden choice from among the remaining n − 1 hats (i's forbidden choice is hat 1).
  2.    Person i takes the hat of 1. Now the problem reduces to n − 2 persons and n − 2 hats.

From this, the following relation is derived:

    !n = (n - 1) (!(n-1) + !(n-2)).\,

Now would you please explain point 1 and 2


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#14 2012-05-20 00:38:55

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

Re: The Wrong Hats Problem

Hi Agnishom;

That is a standard book way of getting a recurrence form. I know it as East-West analysis from a famous book written by the late Herbert S. Wilf. Though I have read it many times I am unable to do it or even explain it. I am sorry about that, wish I could do more here.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#15 2012-05-20 00:46:04

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,172
Website

Re: The Wrong Hats Problem

Dear Bobbym,
Do you own a copy of Amusement in Mathematics by Henry. E. Dudeney?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#16 2012-05-20 00:49:05

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

Re: The Wrong Hats Problem

Hi;

Yes.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#17 2012-06-24 14:32:09

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,172
Website

Re: The Wrong Hats Problem

Actually I don't understand these two lines:
1.    Person i does not take the hat 1. This case is equivalent to solving the problem with n − 1 persons n − 1 hats: each of the remaining n − 1 people has precisely 1 forbidden choice from among the remaining n − 1 hats (i's forbidden choice is hat 1).
2.    Person i takes the hat of 1. Now the problem reduces to n − 2 persons and n − 2 hats.

and why hat 1? Why dont we extend the list with Hat 2 and Hat 3 and forever???


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#18 2012-06-24 14:46:30

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: The Wrong Hats Problem

You could've said that we start from Person 2 for the casework, but that wouldn't change much except a few indexes. The point of that casework is to see what are the values weget for each case that exists.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#19 2012-06-27 16:43:01

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,172
Website

Re: The Wrong Hats Problem

Actually I still don't get it


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#20 2012-07-04 21:20:23

biffboy
Member
Registered: 2012-03-23
Posts: 1

Re: The Wrong Hats Problem

Agnishom wrote:

It has been many days since I last posted. Feeling cool to post again

Anyway,
            There had been eight men and eight hats. They were so much drunk that they could not recognise their own hats. So they picked them up in a random manner. Now what is the chance that no man will choose his own hat?
            Of Course the first step is to find the factorial of 8 which is equal to the number of ways they can pick up the hats in. But it is such a large number that it would take years to write all of them down?

Can You give me the answer????


I know the answer but I dont know how to derive it. So a help would be nice

I would have thought the answer was simply 7/8*6/7*5/6*4/5*.3/4*2/3*1/2*1/1=3/4

Offline

#21 2012-07-04 22:36:48

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

Re: The Wrong Hats Problem

Hi biffboy;

Welcome to the forum! Please check the link in post #12.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#22 2012-07-09 13:48:55

Agnishom
Real Member
From: The Complex Plane
Registered: 2011-01-29
Posts: 17,172
Website

Re: The Wrong Hats Problem

Hi biffboy
Why do you calculate that way?
Pls Explain


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'You have made another human being happy. There is no greater accomplishment.' -bobbym

Offline

#23 2012-07-09 14:07:18

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: The Wrong Hats Problem

Hi Agnishom

biffboy's solution isn't correct.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#24 2012-07-09 20:48:00

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,237

Re: The Wrong Hats Problem

Hi Agnishom;

The calculating part is a derangement problem. biffboy's solution is not correct.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Board footer

Powered by FluxBB