Friday, February 17, 2006

A few problem-solving exercises just for fun. . .

As an aside: I feel like I'm on a blog post marathon. I don't intend to keep posting things so close together, but I keep finding something new I want to post! Thankfully, my recent posts have been quick and easy to write - with a huge exception to my Under Grace, Part III post - so it hasn't eaten away my time. I'm not intending to keep up this rapid posting schedule indefinitely, in case anyone is wondering :). This weekend should be slow while I'm out of town.

~~~~~~~~~~~~~~~~~~~~~~

As one of my math education electives in college, I took a problem-solving course. It would have proved to be my favorite course in college had it been structured differently, but regardless, I loved working through different problem types and tweaking my thoughts until I reached a solution. It was pure fun. I kept my course folder for memories and to occasionally pull from for the classes I teach.

We had some extra time in geometry yesterday so we did some problem-solving exercises from the back of the book that were similar to the ones I did in my problem-solving course. They loved them! Of course, who wouldn't? It's like working a puzzle :). As part of the homework assignment, I told my students I would e-mail them a few problems from my folder. They're just so much fun, I thought I'd share them here, along with a bonus problem just for all of you. For a treasure trove of such problems, try my former professor's website. That should keep you busy for about a decade :).

Feel free to comment with answers. If you want to work the problems out on your own, don't look at the comments first! I'm especially interested to see if anyone can get the last one. The first ones are quite doable, but the last requires a bit more.

~~~~~~~~~~~~~~~~~

What Color is my Hat?

Three people are sitting in a row, one behind the other, facing forward. The third person can see the two people in front of him, the second person can see the person in front of him, and the first person can see no one.

There are 5 hats: 3 red hats and 2 black hats. A 4th person places one hat on each of the three people's heads without each person knowing his own hat color.

The 3rd person says, "I cannot tell what color hat I have."
The 2nd person says, "I cannot tell what color hat I have."
The 1st person says, "I know for sure what color hat I have."

Is he telling the truth, and if so, what color hat does he have?

~~~~~~~~~~~~~~~~~

Crime and Logic

Four suspects of a crime made the following statements to the police:

Andy: Carl did it.
Bob: I did not do it.
Carl: Dave did it.
Dave: Carl lied when he said I did it.

Given that one of them "did it" and that exactly one of them told the truth, who did it?


~~~~~~~~~~~~~~~~~

Secret Whole Number

By using the answers to the following questions, Patrick determines Sam's secret whole number.

(1) Is it a factor of 30? --> yes
(2) Is it a prime number? --> no
(3) Is it a multiple of 3? --> no
(4) Is it less than 3? --> no

What is Sam's secret number?


~~~~~~~~~~~~~~~~~

And just for my blog readers, here's a bonus problem! This was my favorite problem that I did in college, I think.

I'll bake chocolate chip cookies for anyone who figures this problem out correctly. (A coconut dessert would be more appropriate, but I don't cook with coconut.) The cookies are available for pickup at our home in Metro Atlanta :). And no doing a search on the internet for this problem; your solution has to be your own work. Happy problem solving!

The Coconut Problem

On a desert island, 5 men and a monkey gather coconuts all day. At nighfall the men go to sleep, leaving the monkey to guard the stash.

The first man wakes up during the night. He divides the stash into 5 equal shares and gives the remaining coconut to the monkey. He takes his share and puts the remaining 4 shares back together in a pile.

The 2nd, 3rd, 4th, and 5th men each wake up separately in succession throughout the night and do the same as the 1st man, each unbeknownst to the others; they each divide the (remaining) pile of coconuts into 5 shares, giving the extra coconut to the monkey, take their share and return the rest of the coconuts to a big pile.

When they all awaken in the morning, the pile is a multiple of 5 coconuts. What is the minimum number of coconuts originally present?

21 comments:

Adrian C. Keister said...

Warning! Solutions ahead.

Hat Problem:

Because the first person doesn't know his color, it cannot be that both the second person and the first person both have black hats. If they did, the third person would know he had red. So because of that, the second person knows that he and the first person cannot both have black hats. If the first person had a black hat, he would know he had a red hat. But he says he doesn't know what color hat he has, therefore the first person cannot have a black hat. The first person, knowing all this, claims he has a red, and he would be correct.

Crime and Logic:

Bob did it. My solution was to suppose each person in turn had done it, and evaluate how many people lied. It is only when Bob did it that exactly one person tells the truth (Dave).

Secret Whole Number

The factors of 30 are 1, 2, 3, 5, 6, 10, 15, 30. Of those, only 6, 10, 15, and 30 are composite (not prime). Of those, only 10 is not a multiple of 3. Therefore, the answer is 10, and actually, condition (4) is superfluous because of condition (2).

The Coconut Problem

The solution is to work forwards, from conditions we know must be the case before and after each man divides the pile. On my honor, I did all this by hand.

Let N be the starting number of coconuts. If we divide N by 5, there must be 1 left over. That means that, for some integer n1, we have that N=5n1+1. Similarly, n1=5n2+1, for some n2. Construct n3, n4, and n5 the same way. What is left after the last man goes is n5, which we are told is a multiple of 5. That means that, for some integer n6, we must have n5=5n6. There are no conditions on n6, except that it be minimized. This is a system of six equations in seven unknowns, plus the minimization condition. We can use substitution to solve:

N=5(5n2+1)+1
=5(5(5n3+1)+1)+1)+1
=5(5(5(5n4+1)+1)+1)+1
=5(5(5(5(5n5+1)+1)+1)+1)+1
=5(5(5(5(5(5n6)+1)+1)+1)+1)+1
=5(5(5(5(25n6+1)+1)+1)+1)+1
=5(5(5(125n6+5+1)+1)+1)+1
=5(5(5(125n6+6)+1)+1)+1
=5(5(625n6+30+1)+1)+1
=5(5(625n6+31)+1)+1
=5(3125n6+155+1)+1
=5(3125n6+156)+1
=15625n6+780+1
=15625n6+781.

The minimum here is n6=1, which means

N=15625+781
=16406.

Final answer: N=16406. Is that right? If it is, I hate to tell you, but I'm not keen on driving all the way over to Atlanta from Blacksburg just to pick up some cookies.

Incidentally, one little trick I used to avoid and catch mistakes with all those parentheses is a computer science trick: start from the left with zero. Every time you encounter a "(", increment your count by one. Every time you encounter a ")", decrement by one. You should end up with zero. If not, you have mismatched parentheses.

In Christ.

Adrian C. Keister said...

Just for revenge, I'll post a few problems of my own on my blog.

In Christ.

Susan said...

I'll give you credit for 2.5/4, so you got a 63%, or I guess since #4 was a bonus, I'll give you 2.5/3, which is an 83%. No extra for the bonus; I don't give partial credit for bonuses. . .

Your answers were correct for 1-3, though your reasoning was not quite right for #3, the secret whole number. Double-check your knowledge of subsets. . .

And nope, #4 is not right. You got the same answer that my Abstract Algebra professor first got, so don't feel too bad. Try, try again :). . .

Susan said...

Oh, and please post your problems to your blog today so I can work them before I leave tomorrow afternoon :).

Adrian C. Keister said...

Reply to Susan.

3. Oh, 1 is not prime. Those dang little exceptions to the rules! Fine: the condition n>3 is not superfluous. That's what comes of being an applied mathematician, and not a pure one. ;-)

4. I see what I did wrong. I needed to take 4/5, not 1/5. I still am not getting any answer that makes sense. I'll wrestle with it a bit longer.

In Christ.

Adrian C. Keister said...

4. Ok, let's try this again.

Let x be the starting number of coconuts. The first guy divides up the pile into five equal portions, but there's one left over, which he gives to the monkey. That means he took (x-1)/5 coconuts. x-1 is divisible by 5; the pile that's left is 4/5 of x-1. So we have 4(x-1)/5 coconuts left after the first guy is done. We can already see the pattern here: subtract one, the multiply by 4/5. We'll get:

1. 4(x-1)/5
2. 4(4(x-1)/5-1)/5
3. 4(4(4(x-1)/5-1)/5-1)/5
4. 4(4(4(4(x-1)/5-1)/5-1)/5-1)/5
5. 4(4(4(4(4(x-1)/5-1)/5-1)/5-1)/5-1)/5

This last one is equal to some multiple of 5, so we'll say it's 5y. If this is so, then simplification yields that

x = (8404+15625y)/1024, or
- 15625 y + 1024 x = 8404. This is a Diophantine equation (x and y have to be integers), which I haven't solved since super-senior year in college, thank you. We reduce the problem down two steps as follows:

Solve

- 15625 y_0 + 1024 x_0 = 1. We can just multiply y_0 and x_0 by 8404 to get the final solution.

In order to solve
- 15625 y_0 + 1024 x_0 = 1
we solve
15625 y_1 + 1024 x_1 = 1, and substitute y_1 = - y_0 as our answer.

Solving
15625 y_1 + 1024 x_1 = 1 is a matter of Euclid's algorithm:

15625 = 1024 * 15 + 265
1024 = 265 * 3 + 229
265 = 1 * 229 + 36
229 = 6 * 36 + 13
36 = 2 * 13 +10
13 = 1 * 10 + 3
10 = 3 * 3 + 1.

Going backwards yields:

1 = 1 * 10 - 3 * 3
1 = -3 * 13 + 4 * 10
1 = 4 * 36 - 11 * 13
1 = -11 * 229 + 70 * 36
1 = 70 * 265 - 81 * 229
1 = - 81 * 1024 + 313 * 265
1 = 313 * 15625 - 4776 * 1024

Thus, the solution to
15625 y_1 + 1024 x_1 = 1
is y_1 = 313, x_1 = -4776. Therefore,
y_0 = -313, x_0 = -4776. These make
- 15625 y_0 + 1024 x_0 = 1. Multiplying by 8404 gives a starting number of x = -40137504 coconuts, a manifest absurdity.

All is not lost, however. Suppose we add to x and y two numbers v and w, respectively, such that the new numbers y+w and x+v still satisfy the equation, but y+w and x+v are both positive. If we plug this into the equation above, we get
-15625(y+w)+1024(x+v)=8404. Note that x and y are the number found before: x = -40137504 and
y = -2630452.
Thus we obtain
-15625 w + 1024 v = 0. Thus,
v = 15625 w / 1024. We would need to pick w's that render v an integer, obviously. Any multiple of 1024 will do. Let's pick the smallest w such that y+w is positive. That means w > 2630452. But remember that 1024|w. This means w = 2630656. Note that 2630656 = 1024 * 2569. With this w, we have v = 40140625. Check: is
x+v>0? Recall that x = -40137504. The answer is yes. So, we have that y + w = 204, and x + v = 3121.

My answer is that the starting amount is 3121. The ending amount will be 1020.

After all that work, I think to myself, there's got to be an easier way. If you know of one, please let me know.

This was kind of fun, in a perverted sort of way. I had to do some math I haven't done in five years. *nyah*

In Christ.

Adrian C. Keister said...

Incidentally, I had to look up how to solve the Diophantine, but the idea of the v's and w's was something I did not look up. I may have been taught it a long time ago; certainly the idea of an affine equation having infinitely many solutions suggested there might be others besides the absurd one.

In Christ.

ashley said...

The answer to all of them is 42.

(This will not make sense to you if you have never read Hitchhiker's Guide to the Galaxy)

Ashley said...

BTW I was just teasing with a sarcastic answer. Puzzles are fun! I'm just way too tired to think right now. ;-)

Susan said...

Ashley,

Are you proud? I did get your comment even without the link. Ben had previously informed me that 42 is "the answer to life, the universe, and everything else."

Adrian,

Hehe, I can't believe you solved it that way! Yes, the answer is 3121, and there were 1020 at daybreak. Your way took considerable more skill than my way, though mine was much quicker ;).

I'm rather impressed with your method, though I don't understand it. You lost me right about the time you mentioned "Diophantine equation." That is Greek to me :). It all looks impressive, though.

I tried very hard to follow your solution, but I'll just trust that there was real math going on between "let x be the starting number of coconuts" and "my answer is the starting amount is 3121." The highest math classes I took were Abstract Algebra and Non-Euclidean Geometry, so there are no Diophantine equations in my past ;).

I used modular arithmetic to solve the problem, and I worked backwards. I also will admit that, were I to re-solve it cold turkey without my solution in front of me, I almost certainly could not do it, at least not my original way; I solved this problem while taking Abstract, which helped immmensely. The solution is my own original, with no extra help, though. Here is my method:

Let xi = # of coconuts when the ith man awoke, for i = 1, 2, 3, 4, 5

x1 = (5/4)x2 + 1
x2 = (5/4)x3 + 1
x3 = (5/4)x4 + 1
x4 = (5/4)x5 + 1
x5 = (5/4)xf + 1
xf = 5l for some l in Z

Thus x1 = (5/4){(5/4){(5/4){(5/4)[(25/4)l + 1]+1}+1}+1}+1, if you can make sense of all those fractions and brackets. Essentially I just nested all the equations, as you did.

Thus x1 = 15,625l/1024 + 2102/256
So x1 = (15,625l + 8404)/1024

This implies that 1024x1 is equivalent to 8404 (mod 15,625). The gcd(1024, 15,625) = 1 and 1 = -4776x1024 + 313x15,625 (using the division algorithm)

This gives -4776*1024x1 is equivalent to -4776*8404 (mod 15,625)

Thus x1 is equivalent to 3121 (mod 15,625)

Now, if you followed that (especially with all the awkward notation), I'm very impressed, since I'm retyping up my 2-year-old solution thinking, "wow, at one time I could do this" ;). Solving modular arithmetic equations via the division algorithm would require a little brushing up. . . Heh. Unfortunately, what I don't use eventually eeks out of my brain, and I just haven't found a regular use for my Abstract Algebra. T'was a fascinating course, though.

Modular arithmetic is so interesting to me. Every adult in America uses it on a daily basis without even realizing it :). I like saying to people, "Okay, say it's 10:00 in the morning. What time will it be in 5 hours?" After they reply "3:00" I counter with "Why isn't it 15:00?" This, of course, is assuming a chat with non-military personnel :).

I must admit to doubling over with laughter as I read your answer.

Multiplying by 8404 gives a starting number of x = -40137504 coconuts, a manifest absurdity. All is not lost, however.

After all that work, I think to myself, there's got to be an easier way. If you know of one, please let me know. This was kind of fun, in a perverted sort of way.

Hehe. Now you're reminding me of my Brother Dear :). That sounds like something he would say for some reason.

Your cookies are claimable next time you're passing through Atlanta :).

Ashley said...

I want cookies too. Or peanut butter and chocolate cake. After all, I did have the answer for everything. :-) And yes I am proud of you! I thought Ben might have informed you, but I wasn't sure.

Adrian C. Keister said...

Reply to Susan,

Why so surprised I solved it? I mean, this is what I would call a senior-level undergraduate problem, and I have had that level of education, as have you.

Hey, guess what? Our solutions are pretty much the same thing! We even have the same intermediate equation. I think your division algorithm is pretty much all Euclid's algorithm is. The name "Diophantine" has been around for literally millenia. Diophantus, a Greek (good guess!) studied equations that had only integer solutions. So any equations which require integer solutions are today called Diophantine, and there are many different kinds. I would recommend looking up Diophantine equations on MathWorld. Yes, the more I think about it, the more am I convinced our two methods are completely equivalent. I just wrote up the division algorithm, whereas your write-up just writes the result. *ahem* ;-)

So you must have seen the division algorithm in Abstract, right? I got it in Number Theory. Did you ever take Real Analysis at UGA? How about complex analysis? Vector analysis?

So, yes, the next time I pass through Atlanta (I have no idea when that will be. Last time was for my Lane's wedding in 2001, I think it was.) My favorites are oatmeal raisin, and chewy, not crunchy. :-)

In Christ.

Susan said...

Ashley,

How many different ways are you going to sign your name ;). And yes, I suppose you did get them all right, even the coconut one. Impressive since you've only gone through calculus ;). I think I'll have to reward you with a peanut butter chocolate cake. . .


Adrian,

Note I said, "I can't believe you solved it that way." I figured you would be able to solve it. I was merely expressing my disbelief in the way you solved it. It was just too amusing when you found x to be a negative number in excessive of several million. I was thinking, "What did he do?" But then it actually worked out. Hehe.

Yes, I was introduced to Euclid's algorithm in Abstract. I never got to take an Analysis course. It wouldn't fit into my class schedule because of my education classes :-P. I spent my time drawing pictures of mathematicians (no kidding) instead of learning from mathematicians. . .

Adrian C. Keister said...

Not even Advanced Calculus?

I have to say, no offense (though it sure sounds like you weren't impressed, either) but education classes are somewhat lacking in content. Do we really need to send people to school to learn how to pass out paper? Or to learn that "one must have adequate lighting," as my mother would say. They're mostly a waste of time. Better to master the subject you want to teach.

O, and did you see the Yahoo news item on unschooling? That's homeschooling with a twist: the children set the entire curriculum. I'm not sure if I've ever heard anything so dashed absurd in all my life. What about the fallenness of human nature?

In Christ.

Susan said...

Yes, I didn't learn a whole lot in my education classes. We seriously spent two days drawing pictures of our conception of a mathematician and then presenting our drawings to the class. Then we spent 3 days talking about one dot pattern. My fellow "prisoners" and I decided that education programs have beating a dead horse down to an art.

The worst was how much relativism permeated even math education. Almost direct quote from a class (I heard the same thing so many times, that it's hard not to remember): Now think about what I did a minute ago. I praised Brian for his correct answer, but did not praise Nikki for her incorrect answer. We need to be careful. That's an issue of equity. I think it's an ethical issue too.

BTW, did you know that students shouldn't be told their answers are wrong? We should just encourage them to "think about it another way" or "continue to explore the problem." Now I'm all for encouraging kids, but they also need to know that math does have a right or wrong answer.

The highest calculus I took was third semester, multi-variable calculus. Not sure if that's considered advanced, probably not :).

Heh, so you're not a fan of unschooling either? I think it's a wrong solution to an obvious problem. Of course there are varying degrees of unschooling, so I can't say it would always fail - kind of like declaring all "dating" to be a sin" - but it certainly doesn't seem like a good idea in its general form. No kidding about sinful nature. Unschooling, as a general rule, doesn't seem to jive with total depravity. . .

Nope, didn't see the Yahoo news item on unschooling, but two weeks ago a friend sent me a CNN link to an article on unschooling, asking me what I thought about the concept. This is what I responded:

I like parts of it[unschooling], such as the stress on learning being a life task, not something compartmentalized into certain hours [or years]of the day, but I think usually "unschooling" is not a good idea. I know if I had been given freedom to determine my study habits when I was in 4th grade, I would be a rather uneducated person today :). Children need structure and regular discipline to form good life habits, and "unschooling" doesn't always provide that. I think it can work, but I think as a general rule it is not a good idea.

I favor the classical approach to education - through homeschooling, through a good, Christ-centered classical Christian school, or through a combination of the two (like the one-a-week program for which I teach). The classical approach is very disciplined, stressing the need for structure and form and stressing reasoning in all aspects of education. God is a God of order, and discipline is very stressed in scripture, including the discipline of our mind, which is why I like the classical approach.

I guess I just feel that "unschooling" in general fails to stress discipline and excellence to a proper level. "Unschooling" is a negative reaction (rightly so) of general, purposeless-driven education today. Most educational methods today focus on teaching to the test, meeting state requirements, etc., to the detriment of the love of learning, learning for pleasure and for purpose, etc. I agree with "unschoolers" in their recognition of this problem. I do feel that other educational methods, such as the classical method, have managed to incorporate purpose and reason to learning without the sacrifice of discipline.

Ashley said...

Especially impressive since my Calculus was in high school - not even college. ;-) And the reason why I sign my name different ways is because "twentysixacts" is my blogger account, but I've been trying to remember to manually sign my name so the link goes to my real blog, instead of my profile. It's so all the thousands of people who visit your site can come read my blog because I sound so interesting. :-) And wise, too, since I obviously know the answer to everything. Now I want to prove to you that I *can* do math so maybe I'll work through the puzzles.

Adrian C. Keister said...

Ja, the ridiculousness of not pouncing on wrong answers. *Because we think it will hurt their self-esteem* (Said in a whiny, liberal sort of voice.) Bosh. Self-esteem is something I rank among those things that needs to be hurt, and often.

Multi-variable calculus is not advanced. That's what I would call the end of the beginning of advanced math. You gotta get into detailed delta-epsilon proofs, and the real number system. Later on, you get Lebesgue integrals which are great fun. (Maybe I'll explain those some time; the basic idea is very intuitive.) I think, and it's only me that thinks, you should pick up a book on classical analysis. The Kirkwood book is good: An Introduction to Analysis. Yup, that's right. The walking book recommendation has struck again. I could be like Spiderman: your friendly neighborhood book-recommender. Only I'm not in your neighborhood. Unless you let delta get very large...

Liked your comments on unschooling. It seems apt.

As regards homsechooling. I don't think it's the best option for most people right now, but the only reason is that I don't think most parents are qualified to teach it. If we get a generation of classically trained parents, then let them homeschool! I think, in fact, this would be one of the best strategies. We get a bunch of classical Christian schools together, train up a generation or two, and then disband and let the parents take over. I really like the sound of that.

In Christ.

Susan said...

Well, we did a lot with epsilon in Sequences and Series, mainly with limits and convergence. Stuff like that. Good times. We also dealt with the reals a lot in Abstract and in S&S, but I'm sure not to the extent you mean :).

Your plan for education sounds like a 2-step recovery program for smoking. Hehe.

Well, I'm not going to deny that there are many parents who are underqualified to teach their children, but many also don't have the monetary ability to send their children to a private school, and I definitely do not see public schools as a step up. Even for those with the assets, a classical school may not be in their area. Now, in Atlanta there are oodles of choices - some full-time, some part-time - but that isn't typical for the rest of the nation.

I really do like the classical method, as I've grown to be more familiar with it over the past few years, but I also think there are other valid forms of education out there. Ultimately it depends on how the education is implemented.

I keep meaning to do a more in-depth look at classical education. I am familiar with the basic concepts (kind of hard not to be since I'm teaching for a classical program. . . ), but I'd like to know more. And, yes, Wilson's book is on my reading list, just to save you some typing. *smirk*

Adrian C. Keister said...

Reply to Susan.

*tsk, tsk* You don't seem to have caught on to my joke or my typo. Homsechooling (sic) indeed. Or my neighborhood joke. A neighborhood in math is like a circle around a point, with radius delta. So a pun on the word neighborhood was what I had in mind...

In Christ.

Turn2 said...

I had saved your blog in my Favorites but hadn't been back until now. You seem to be an exceptional young woman who would make an engaging conversational companion. As for the math/logic problems, I may consider them though they are surely over my head. The Lovely And Gracious Wife and The Ever Precocious Daughter have jumped on the sudoku bandwagon recently so maybe they will take a crack at them. I will revisit your site again soon...maybe after your hiatus.

Susan said...

Reply to Adrian,

You will be the downfall of me yet! Here I am dutifully staying away from blogs for a few weeks, and you have to go and comment on my blog AND refer to more comments you've made to me on your blog (TIOC. . . ). *resumes editing position* Too bad you can't even correctly quote your own acronym on my blog :).

It is only because I am polite that I am not currently ignoring your comment *folds arms in mock anger*.

So I see that now I am to be your junior editor, or maybe chief editor, unless your mother has already claimed that role ;). I didn't know it was my responsibility to correct your spelling mistakes. . .

As for the delta/neighborhood joke, please accept my ignorance in this area as reason for not catching onto that joke. My acquaintance with delta does not go beyond its use in elementary physics as a symbol for change. . .

Okay, I am now going back into hybernation for another week or so. Sewing projects are coming along fine, but require more time before I am officially released back into the blogosphere. Meanwhile I will try to cope.