What is the solution to the hat problem?

[Jamin2112]

Homework Statement

2.10. Express each of the following statements as a conditional statement in "if-then" form or as a universally quantified statement. Also write the negation (without phrases like "it is false that").

a) Every off number is a prime
b) The sum of the angles of a triangle is 180 degrees
c) Passing the test requires solving all the problems
d) Being first in line guarantees getting a good seat
e) Lockers must be turned in by the last day of class
f) Haste makes waste
g) I get mad whenever you do that
h) I won't say that unless I mean it

2.41. A clerk returns n hats to n people who have checked them, but not necessarily in the right order. For which k is it possible that exactly k people get a wrong hat? Phrase your conclusion as a biconditional statement.

Homework Equations

?

The Attempt at a Solution

The only part of the first problem that I'm stuck on is b.

The sum of the angles of a triangle is 180 degrees

What does "a" triangle mean? Does that mean "any" triangle or "one" triangle? I don't know how to interpret that.

And the second problem is just plain confusing.

So, suppose n=4.

You could have k=1,2,3 or 4.

You could have

right, wrong, wrong, wrong
right, right, wrong, wrong
right, right, right, right
.
.
.

... Is that the right idea? I'm not sure if I'm doing this right.

 

[LCKurtz]

Homework Statement

2.10. Express each of the following statements as a conditional statement in "if-then" form or as a universally quantified statement. Also write the negation (without phrases like "it is false that").

a) Every off number is a prime
b) The sum of the angles of a triangle is 180 degrees
c) Passing the test requires solving all the problems
d) Being first in line guarantees getting a good seat
e) Lockers must be turned in by the last day of class
f) Haste makes waste
g) I get mad whenever you do that
h) I won't say that unless I mean it

2.41. A clerk returns n hats to n people who have checked them, but not necessarily in the right order. For which k is it possible that exactly k people get a wrong hat? Phrase your conclusion as a biconditional statement.

Homework Equations

?

The Attempt at a Solution

The only part of the first problem that I'm stuck on is b.

The sum of the angles of a triangle is 180 degrees

What does "a" triangle mean? Does that mean "any" triangle or "one" triangle? I don't know how to interpret that.

It means "any".

And the second problem is just plain confusing.

So, suppose n=4.

You could have k=1,2,3 or 4.

You could have

right, wrong, wrong, wrong
right, right, wrong, wrong
right, right, right, right
.
.
.

... Is that the right idea? I'm not sure if I'm doing this right.

Could exactly 1 person have the wrong hat? Is there something special about 1?

 

[Mark44]

Homework Statement

2.10. Express each of the following statements as a conditional statement in "if-then" form or as a universally quantified statement. Also write the negation (without phrases like "it is false that").

a) Every off number is a prime

What's an "off" number? Do you mean odd?

b) The sum of the angles of a triangle is 180 degrees
c) Passing the test requires solving all the problems
d) Being first in line guarantees getting a good seat
e) Lockers must be turned in by the last day of class
f) Haste makes waste
g) I get mad whenever you do that
h) I won't say that unless I mean it

2.41. A clerk returns n hats to n people who have checked them, but not necessarily in the right order. For which k is it possible that exactly k people get a wrong hat? Phrase your conclusion as a biconditional statement.

Homework Equations

?

The Attempt at a Solution

The only part of the first problem that I'm stuck on is b.

The sum of the angles of a triangle is 180 degrees

What does "a" triangle mean? Does that mean "any" triangle or "one" triangle? I don't know how to interpret that.

"A" triangle means any old triangle. All you can assume is that it has three sides.

And the second problem is just plain confusing.

So, suppose n=4.

You could have k=1,2,3 or 4.

You could have

right, wrong, wrong, wrong
right, right, wrong, wrong
right, right, right, right
.
.
.

... Is that the right idea? I'm not sure if I'm doing this right.

If n = 4, is it possible for exactly one person to get the wrong hat? It's certainly possible for two people to get the wrong hat.

You won't be able to assume any specific value for n, but I think it's useful to look at different cases - n = 1, n = 2, n = 3, n = 4, etc., to see if you can detect a pattern.

Also, don't forget k = 0.

 

[Jamin2112]

Could exactly 1 person have the wrong hat? Is there something special about 1?

No. 3 persons have the right hat ----> 4 persons have the right hat. I don't think it's the same way for 3 persons having the wrong hat ...

Anyways, why does this matter?

 

[Mark44]

Because the problem asks you "For which k is it possible that exactly k people get a wrong hat? "

 

[LCKurtz]

No. 3 persons have the right hat ----> 4 persons have the right hat. I don't think it's the same way for 3 persons having the wrong hat ...

Anyways, why does this matter?

Why it matters is you are trying to decide for what values of k, exactly that many people can have the wrong hat. And you have apparently decided it can't be k = 1. What about k = 2, or 3, or...?

 

[Jamin2112]

n=1

You can only have one person get a wrong a hat or one person get the right hat. k=1.

n=2

You can have two persons get the wrong hat or you can have two person get the right hat. k=2.

n=3

You can have two persons get the wrong hat and one person get the right hate; or you can have everyone get the wrong hat. k=2,3.

n=4

You can have two persons get the right hat and the other two get the wrong hat; or you can have everyone get the wrong hate; or you can have 3 persons get the wrong hat and one get the right hat.

k=2,3,4.

.
.
.
.
.
.

Is there a pattern I'm supposed to be detecting?

 

[Mark44]

You're skipping a lot of cases, or maybe just not being clear about what you're saying.
n = 1. How can one person with one hat get the "wrong" hat. There is only one hat.
n = 2. What are the circumstances for k = 0, k = 1, k = 2?
And so on.

 

[Jamin2112]

n=1

You can only have one person get a wrong a hat or one person get the right hat. k=1.

n=2

You can have two persons get the wrong hat or you can have two person get the right hat. k=1.

n=3

You can have two persons get the wrong hat and one person get the right hate; or you can have everyone get the right hat. k=1,3.

n=4

You can have two persons get the right hat and the other two get the wrong hat; or you can have everyone get the right hat. k=2,4.

.
.
.
.
.
.

Is there a pattern I'm supposed to be detecting?

 

[Jamin2112]

You're skipping a lot of cases, or maybe just not being clear about what you're saying.
n = 1. How can one person with one hat get the "wrong" hat. There is only one hat.
n = 2. What are the circumstances for k = 0, k = 1, k = 2?
And so on.

n=2

Either one gets the right hat and one gets the wrong hat; or both get the right hat.

k=2.

n=3

Either two get the wrong hat and one gets the right hat; or all get the wrong hat.

k=2,3.

 

[Mark44]

n=1

You can only have one person get a wrong a hat or one person get the right hat. k=1.

Again, how can one person get the wrong hat if there is only one hat?

Here's the situation. A guy walks into a restaurant where there are no other patrons, and checks his hat at the hat-check stand. After he checks it in, there is only one hat. After he finishes eating and pays for his meal, he goes back to the hat-check. How can he possibly get the wrong hat?

n=2

You can have two persons get the wrong hat or you can have two person get the right hat. k=1.

What does k = 1 mean here? The question you are supposed to be answering is "For which k is it possible that exactly k people get a wrong hat?" Is it possible for 1 person to get the wrong hat where there are two people and two hats?

n=3

You can have two persons get the wrong hat and one person get the right hate; or you can have everyone get the right hat. k=1,3.

n=4

You can have two persons get the right hat and the other two get the wrong hat; or you can have everyone get the right hat. k=2,4.

You're not considering all the possibilities. For example, 3 people can get the wrong hat and 1 person the right hat. Here's one possibility:
Person: 1 2 3 4
Hat...: 1 3 4 2

Person 1 gets the right hat, person 2 gets hat 3, person 3 gets hat 4 and person 4 gets hat 2.

.
.
.
.
.
.

Is there a pattern I'm supposed to be detecting?

 

[Jamin2112]

Okay ... Let me try this one last time.

n=1

Person: 1
Hat: 1

n=2

Person: 1 2
Hat: 1 2


Person: 1 2
Hat: 2 1

So either they both get the wrong hat or they both get the right hat.

n=3

Person: 1 2 3
Hat: 1 2 3

All right

Person: 1 2 3
Hat: 1 3 2

1 right, 2 wrong

Person: 1 2 3
Hat: 2 1 3

1 right, two wrong

Person: 1 2 3
Hat: 2 3 1

all wrong

Person: 1 2 3
Hat: 3 1 2

all wrong

Person: 1 2 3
Hat: 3 2 1

1 right, 2 wrong

n=4

Person: 1 2 3 4
Hat: 1 2 3 4

Person: 1 2 3 4
Hat: 1 2 4 3

Person: 1 2 3 4
Hat: 1 ....

.
.
.
.
.
.

etc.

Is brute force the way to do this?

k can be 3 or 2 when n=3 and only 2 when n=2.

I don't understand the phrasing "For which k is it possible that exactly k".

Can someone explain that?

 

[Mark44]

How else other than "brute force" would you analyze this situation? You're only using brute force, as you call it, to get an idea of what is going on for relatively small values of n.

Now that you have looked at the various cases for n = 1, 2, 3, and 4, summarize what you have found, stating the values of k for which exactly k people get the wrong hat.

k is an integer such that 0 <= k <= n.
So, for n = 1, is it possible that 0 persons get the wrong hat? Is it possible for 1 person to get the wrong hat?

For n = 2, is it possible that 0 persons get the wrong hat? Is it possible for 1 person to get the wrong hat? Is it possible for 2 persons to get the wrong hat?

Etc.

A table might be a way to display this information.

 

[Jamin2112]

How else other than "brute force" would you analyze this situation? You're only using brute force, as you call it, to get an idea of what is going on for relatively small values of n.

Now that you have looked at the various cases for n = 1, 2, 3, and 4, summarize what you have found, stating the values of k for which exactly k people get the wrong hat.

k is an integer such that 0 <= k <= n.
So, for n = 1, is it possible that 0 persons get the wrong hat? Is it possible for 1 person to get the wrong hat?

For n = 2, is it possible that 0 persons get the wrong hat? Is it possible for 1 person to get the wrong hat? Is it possible for 2 persons to get the wrong hat?

Etc.

A table might be a way to display this information.

n=1

0/1! chance of 1 wrong hat

n=2

1/2! chance of 0 wrong hats
0/1! chance of 1 wrong hat
1/2! chance of 2 wrong hats

n=3

1/3! chance of 0 wrong hats
0/3! chance of 1 wrong hat
3/3! chance of 2 wrong hats
2/3! chance of 3 wrong hats.

n=4

1/4! chance of 0 wrong hats
0/4! chance of 1 wrong hat
5/4! chance of 2 wrong hats
9/4! chance of 3 wrong hats
9/4! chance of 4 wrong hats

.
.
.So, for n persons there is always an 1/n! chance of getting the hats all right and a 0 chance of getting just one hat wrong. Other than that, I don't see a pattern heating up.

And I still don't understand the question.

Maybe the chance of getting 2 hats wrong has a pattern? I see that when n=2, the chance was 1/2!; when n=3, the chance was 3/3!; when n=4, the chance was 5/4!. Maybe if j represents the chance of getting 2 wrong, j=(2n-3)/n!

?

 

[Mark44]

You're carrying this further than I would have, by counting the number of ways something can happen. All that's needed, I believe, is whether something can happen, not how many ways it can happen. This isn't a probability problem.

 

[Jamin2112]

I just don't understand how to construct my answer.

"It is possible that exactly __ people get a wrong hat."

?

And in the blank would be some expression involving n?

Give me an example of an answer but don't use correct values.

 

[Mark44]

I think it's too soon to jump to the answer for this problem. It might be useful to look at a couple more cases, n = 5 and n = 6. That might give more insight to this problem, such as does it matter whether n is even or odd.

 

[Jamin2112]

I think it's too soon to jump to the answer for this problem. It might be useful to look at a couple more cases, n = 5 and n = 6. That might give more insight to this problem, such as does it matter whether n is even or odd.

5! = 120. You kidding? Show me the non-brute force way, or at least lead in the right direction.

Whenever you think in terms of groups of 3, say 7 (3+3+1) or 12 (3+3+3+3), you have groups where either all 3 have wrong hats, 2 have wrong hats, or 0 have wrong hats in those sub-groups.

Whenever you have groups of 2 persons, you have either 2 wrong hats or zero wrong hats.

Do I proceed from there? I know I can think of n in therms of 2 and 3.

 

[LCKurtz]

Here's another hint. Regardless of what n is but greater than 1, if you pick a subset of the people with k at least 2 people, can you see a way each of them could pass their hat along to the next so they all have wrong hats while all the others has their own hat?

 

[PhaseShifter]

I just don't understand how to construct my answer.

"It is possible that exactly __ people get a wrong hat."

?

And in the blank would be some expression involving n?

Give me an example of an answer but don't use correct values.

In the blank would be "k."

Which values of k are allowed for any given value of n?
Which values of k are not allowed?

 

[Mark44]

5! = 120. You kidding?

Again, you don't have to count all of the ways.

Show me the non-brute force way, or at least lead in the right direction.

Whenever you think in terms of groups of 3, say 7 (3+3+1) or 12 (3+3+3+3), you have groups where either all 3 have wrong hats, 2 have wrong hats, or 0 have wrong hats in those sub-groups.

Whenever you have groups of 2 persons, you have either 2 wrong hats or zero wrong hats.

Do I proceed from there? I know I can think of n in therms of 2 and 3.

 

[Jamin2112]

In the blank would be "k."

The "it is possible" seems like a weak statement to me.

What is this problem getting at? I need more hints!

 

[PhaseShifter]

Look carefully at the problem, and consider what you are supposed to be asking.

"Is it possible" is equivalent to "does at least one example exist"--why would you have to enumerate every example for a given value of k, when it is sufficient to find one?

 

[Jamin2112]

Look carefully at the problem, and consider what you are supposed to be asking.

"Is it possible" is equivalent to "does at least one example exist"--why would you have to enumerate every example for a given value of k, when it is sufficient to find one?

The problems was:

A clerk returns n hats to n people who have checked them, but not necessarily in the right order. For which k is it possible that exactly k people get a wrong hat? Phrase your conclusion as a biconditional statement.

I think:

"There exists a number k≤n representing the number of people who get a wrong hat"

Okay, well I know k≠1 because if (n - 1) persons get the right hat, then n persons get the right hat.

That's all I've established.

 

[PhaseShifter]

For which k is it possible that exactly k people get a wrong hat?

I think:

"There exists a number k≤n representing the number of people who get a wrong hat."

There is not a single number k for most values of n. This is one point where you are going wrong.

Plus, you don't need to consider all n! permutations of n people with hats.
Partition the group into people with the incorrect hat, and people wearing the correct hat.

Now consider this: If the hat I have is not my own, is its owner wearing the correct hat?