The monkey and negative number of coconuts

September 21, 2009 By

Coconut trees

There’s this math puzzle that I recently heard from my friend. Here it goes:

The puzzle

In the not so distant past, there was this small island. And there’s this monkey… what? Yes, it’s alone. Ok, fine, he’s alone. Yes, poor thing.

So, on this island, there were many many many coconut trees. And each of them bore enough fruits to collectively and breath-of-a-hair-barely escaping the sinking of the entire island. These palms were fertile, I tell ya.

And there were them these pirates, ya know. Arrr! And they were five in all. Ok, you can stop arrr-ing now. Huh? What were these pirates doing on the island? Uh, they got stranded? How do I know? (*whispering to myself* the filthy swashbuckling buccaneers…)

Anyway, they saw them these coconuts just hanging there, and they thought they were in coconut heaven. They proceeded to gather all the coconuts they could get their hands on. Hmm? They might have some food on them. Uh, maybe they had cravings for coconut?

The monkey saw what they were doing, and went to help them. Finally, at sundown, they… what? It took maybe a day… Yes, that means the pirates arrr-ived in the morning. Alright, let me continue the story, will ya?

So at sundown, they were exhausted, and decided to divide the coconuts the next morning. And they went to bed. Or sand. Or whatever they used as makeshift beds.

During the night, one of the pirates woke up, fearing the others would betray him. And so he started dividing the pile of coconuts into 5. While he’s busy counting and dividing, the monkey came to the pile, took a coconut, opened it up and started eating. The fearful pirate, afraid of startling the monkey and making more noise, just let the monkey be. It turned out well, for he divided the pile evenly into 5. And then hid his share of the coconuts. And he went to sleep.

And another pirate, fearing the same thing, woke up just after the first pirate went to sleep. And he divided the rest of the coconuts into 5. And the monkey also took a coconut and ate it, bemused at the stealth tactics employed by the counting pirate. This second pirate was satisfied that he counted correctly and that he divided the pile evenly into 5, so he let the monkey go. Besides, he was busy hiding the coconuts and trying to be quiet.

A third pirate did the same thing, dividing the remaining pile of coconuts into 5. And the monkey did the same thing, eating a coconut while the pirate was having trouble because he didn’t have enough fingers on his left hand to help him.

And a fourth pirate did the same thing. And the fifth too.

At each quiet division of coconuts, the pile was divided evenly. And the monkey ate a coconut at each division. So, how many… Yes, the monkey ate a total of 5 coconuts. You’re so clever. So, how many coconuts were there in the original pile?

The solution (sort of…)

I am going to work backwards.

Let y be the number of coconuts left over.
Let x be the original number of coconuts.
Note that x and y must be integers.

At 5th pirate division:
He hid his pile, so we add his pile back.
What’s left would be 4 parts for the rest, so we get 5y/4 to get all the pirates’ share.
Oh yeah, we need to get the monkey to regurgitate his coconut.
Ok, maybe not…

So before the 5th pirate divided, we had
5y/4 + 1
= (5y + 4)/4

At 4th pirate division:
It’s 4 parts for the other pirates, so we do the 5/4 multiple again to get
5( (5y + 4)/4 )/4
And we add 1 from the monkey to get
5( (5y + 4)/4 )/4 + 1
= (25y + 20)/16 + 1
= (25y + 36)/16

Note the recursive nature.

At 3rd pirate division:
5( (25y + 36)/16 )/4 + 1
= (125y + 180)/64 + 1
= (125y + 244)/64

At 2nd pirate division:
5( (125y + 244)/64 )/4 + 1
= (625y + 1220)/256 + 1
= (625y + 1476)/256

At 1st pirate division:
5( (625y + 1476)/256 )/4 + 1
= (3125y + 7380)/1024 + 1
= (3125y + 8404)/1024

And so we have
(3125y + 8404)/1024 = x
=> 1024x = 3125y + 8404

Now, my first thoughts had something to do with the Chinese Remainder Theorem or the GCD or something. And I searched for the solution, because I have no idea how to start. And I came upon Diophantine equations.

And I have absolutely no idea how to solve the equation.

Now my friend did tell me that 3121 was a solution for the number of original coconuts, which would mean 1020 coconuts were left over. And something about modular arithmetic.

What is more interesting, is that he told me -4 is also a solution. I plugged it into the equation, and lo and behold! There were -4 coconuts left over.

Wait, what? So there were -4 coconuts originally, and after all the sneaking and counting of the pirates, and the monkey eating it’s, ok, his, (presumably) non-existent -1 coconut, we have -4 coconuts left over?

The only reason why that solution was confounding us, ok, me, no wait, you, arrr, whatever, is that an assumption was flawed. We can’t have negative numbers of coconuts. Not in this reality dimension anyway. Arrr.

But it’s interesting. -4 is a stable solution, in chaos theory parlance. I mean parrrlance. Arrr.

Final thoughts: Why would each pirate fear that the others would betray him, but was honest enough to divide the coconuts evenly? And how would the first pirate divide 3121 coconuts into 5 while keeping quiet (that’s a lot of coconuts)? And keeping his head straight? And keeping the monkey quiet?

This is why, sometimes, just because you can solve a math problem, doesn’t mean you should. Because it might not make sense in the first place.

P.S. This was inspired by my friend who told me about the puzzle, and the International Talk Like A Pirate Day. Arrr.

[image by akurtz]

Filed Under: Mathematics Tagged With: , , ,

Carcerian Stones – Where is this Arofell fella?

August 31, 2009 By

We’re continuing the D&D adventure story. Previously, we found our adventurers at the gates of Havenswerd, and the bard declared he’s a criminal in the city. We have Ryan the human DM, Dan playing Toth the goliath warden, James playing Heoriss the eladrin invoker, Ian playing Iofae the eladrin sorcerer, and Klenn playing Phileas the half-elf bard. And now…

Wait, there’s also a puzzle hidden in the story. And now…

*****

Ryan: Havenswerd is a big city. You’ll need some know-how to navigate the streets.
Dan: You’re throwing a skill challenge at us?
Ryan: 3 separate ones, in fact. One for shopping, one for the tavern investigation, and one for our bard reaching his friend.
Dan: But it’s just shopping!
Ryan: *shrugs* It’s a street maze. You’ll have to find the shops first.

Ian: How good are we at Streetwise? I have a 4.
James: I’m at ground zero.
Dan: I’m below ground zero… Negative 1! Never thought Streetwise to be useful…

Ian: Alright, we’ll have to swap then. My brother will still go to the tavern. Dan, you go with him. He might need help. And I’ll go shopping. Do I need a list of what they’re buying first? *looking at Ryan*
Ryan: No. You just need to find a shop first. I’ll let you buy for them then, even if these guys aren’t around.

Dan: Wait a minute. So we’re split into 3 groups with individual skill challenges?
Ryan: That’s right.
Dan: That’s not the way to do it.
Ryan: Well, you’re the one who split the party. Besides, it’s different.
Klenn: I think it’s fun, and saves time. So how do we do this?

Phileas gave the party some directions on how to reach the tavern. Through his friend, he’ll contact the party once he’s safe.

Ryan: Hold on a second. Uh, Klenn, you mind telling me who this trusted friend of yours is?
Klenn: Oh, he’s a thief lord, of some sorts. His name is Logan.
James: *shocked* You’re consorting with scoundrels?
Klenn: Let’s just say my character has… flexible morals.
Dan: *pounding on table* AHAHAHA! That’s a good one!

It was late afternoon, and though there’s still light, Phileas didn’t want to wait outside Havenswerd for night to fall (what with the wolves and all). He moved briskly along the side of the walls and disappeared into the shadows of the residential houses. The rest of the party will be split in 2. Iofae will attempt to navigate the streets to find the shops for purchasing much needed equipment. Toth and Heoriss will go to the tavern, retrieve Phileas’ belongings if they’re still there, and gather clues about the murder.

Ryan: So, which group wants to start first?
Klenn: Me. What am I to do?
Ryan: You’re trying to sneak around to reach your friend, so roll for Stealth first, then for Streetwise.
Klenn: *rolls d20*

Phileas reached his thief lord friend.

Klenn: Yes!
Ian: My turn. Streetwise huh? *rolls d20*

Iofae got lost in the maze of identically-looking streets.

Ian: Sorry guys… Now what?
Ryan: Hmm… Roll for Perception.

But he did notice a man slinking suspiciously into an alley. Iofae, lacking any other direction, decided to follow him. At the end of the alley, there was a door. But the man had disappeared.

Ian: I open the door.
Ryan: It’s locked.
Ian: I’m so glad I took this. I have Thievery. I try to pick the lock.
Ryan: Go ahead.

The locked door opened with a soft click. It was dark inside. Iofae moved in further and was stopped by the feeling of a sharp point propped against his neck. “Move any closer, and I’ll slit you.”

Torches lit up, and Iofae saw the man he was following holding a dagger to his neck. There was a group of men further in. He also saw Phileas among them.

Klenn: I am?
Ryan: Ian unwittingly stumbled into your friend’s hideout.
Ian: Oh cool!
Ryan: And you can get help with the shopping from these new friends. And now we turn to our CSI team here…

Medieval alley
[image by jewhyte]

Toth and Heoriss reached the tavern. They decided to go around to the back, where Phileas jumped off, instead of asking the good lady tavern keeper.

Dan: 2nd floor, right? Ok, I’ll heft you up.
James: I’ve got a better idea.

Heoriss blurred, and reappeared at the 2nd floor.

Dan: Bloody eladrins and their teleportations. *smile* Ok, I’ll climb up.
Ryan: Roll for Athletics.
Dan: *rolls d20* Yes!
Ryan: Now roll for Stealth.
Dan: What? Why?
Ryan: Because you’re trying to be quiet.

Toth managed to climb quietly up to the 2nd floor of the tavern, and entered what used to be Phileas’ room through the open window. The dead body was already removed, and there were signs of cleaning up, though there’s still a reddish stain on the floor.

Ian: Blood is notoriously hard to remove…
James: Ok, we search the room for Phileas’ belongings and any clues to the murder.
Ryan: Perception check.
James: *rolls d20* Alright, 20! That’s 29 total.

Heoriss finds a pouch with some money, a flute, and a long sword with some runes on it, hidden away in a corner behind a small cupboard. He also noticed a golden dagger jutting from the ceiling, stuck in a wooden beam.

James: Ok, you’re up.
Dan: Alright. Can I reach the ceiling, or do I have to jump?
Ryan: The ceiling’s low enough for you to reach with a small jump. To simplify things, I’ll just let you pass with the jump.

Toth looked at the golden dagger in his hands. A strange symbol is engraved at the hilt, but both of them didn’t recognise it. They heard someone coming up the stairs, and the voice of a woman saying, “I’ll be right back!”. They decided they’ve gotten what they could find, and left the room in the same manner they came in.

When they were on ground level again, they heard a psst. A shabbily dressed man, a beggar most probably, was looking at them. “Hey. You Toth and Hayoris? Pheeleeus sent me.” They followed the beggar, and reached the thief lord, Logan’s hideout. And the party was reunited.

It’s night time, but somehow, Logan managed to get their stuff bought.

James: We suck. We seriously need some cash. And quick.
Dan: Hear hear.
Ian: There’s not a lot we can buy. Hey, what about this Arofell wizard? We need quests. He seems like the kind of person who gives quests.
Klenn: Yeah. He’s at the Wizards Guild, right? Can we go to this Wizards Guild?
Ryan: So it’s decided? You’re going to Wizards Guild to look for Arofell?
Dan: Yup.
Ryan: You wanna do it at night?
Dan: Oh…

The Wizards Guild

The next morning, the party left to look for the Wizards Guild. Logan got Phileas a disguise, so the half-elf could move around the city.

Dan: Do we need a Streetwise check?
Ryan: *smile* Nope.

Logan also sent one of his underlings to guide the party to the Wizards Guild. It was mid morning by the time they reached the guild. The small guild “office” had a clerk, and the party asked him where could they find Arofell.

“Oh it’s my first day here. Perhaps you could ask the wizards back there. There’s a building behind this one that acts as their labs.”

They went around to the back and saw a 3-storey high building. They counted 1, 2, … 7 doors on each storey. A wizard or two hung around in the courtyard, and apprentices scurried back and forth.

“That nincompoop! I would sooner burn myself to death than to share the same floor as that useless excuse of a wizard!”
“Oh don’t mind him. He doesn’t like Arofell very much, so he moved to the top floor.”

“Who? Arofell? My master sent me to deliver a message to him once. I think his door was odd-numbered.”
“So what’s his floor?” Toth asked. But the apprentice had scurried away.

“Pardon me? You’ll have to speak louder, young man. I can’t hear you.” A wizened face was straining his eyes to look at the party.
“DO YOU KNOW WHERE TO FIND AROFELL?” Heoriss shouted.
“I’ve been on the ground floor for many years, and I’ve never known this Arofell wizard.”

“I only know all the wizards take larger numbers as their door numbers. Well, except for the one at the top floor, who took number 1. He always insult me whenever I pass a message to him, that arrogant, self-important piece of … Uh, you wouldn’t tell anyone about what I just said, would you?”

“Well, I do know the corner rooms of the 2nd floor aren’t taken.”
“How do you know that?” Iofae asked.
“Because, I uhm…” The young man was blushing furiously.
“Ahh, a tryst?” Phileas offered.
The young man blushed even more.
“If I work hard for a few years, I’ll be able to marry her, and get ourselves a house.”

James: Any more clues?
Ryan: That’s it.
Dan: Alright, math genius, this is your kind of thing.
Ian: Hmm… it’s elementary, my dear Watson.

The party deduced the correct room of Arofell, and entered the room. In it, they found piles and piles of paper and books. The candle on the desk had long ceased burning. A large book lay open on the desk, and a man, perhaps in his mid-forties, was snoring on top of it.

“Mr Arofell?” Phileas asked.

to be continued…

*****
P.S. Skill challenges are non-combat encounters. There’s a difficulty class (DC) for the appropriate skill and situation. For example, to pass a DC 16 for Athletics, you need to roll a d20. If the result plus your Athletics score (plus any other modifiers) is equal to or greater than 16, then you pass.

Update: I changed the sword of Phileas in the tavern from a magical short sword to a magical long sword. Yes, I know it sounds like innuendo. I just need him to deal a bit more damage, even if it’s all in my mind. … Alright, stop leering. You’re creeping me out…

Filed Under: Curiosita Tagged With: , , , , ,

The composite space between prime products

April 2, 2009 By

Previously, I gave you a puzzle on prime numbers.

Let F(n) be (1st prime) * (2nd prime) * … * (nth prime)
The question was to describe the group of numbers between 2 and F(n)-1 that F(n) cannot divide.

And the answer is… all composite numbers between 2 and F(n)-1 with repeated prime factors. Hmm… I guess that doesn’t quite fit the “as plain an English as possible”, but it is concise.

For example, F(n) cannot divide 4, because 4 = 2*2 (repeated 2).
But F(n) divides 6, because 6 = 2*3 (no repeated primes).
F(n) cannot divide 18, because 18 = 2*3*3 (repeated 3).

The proof (sort of)

If a number A in [ 2, F(n)-1 ), is prime, then F(n) divides A by definition because F(n) is a product of primes.

Let A be a composite number in [ 2, F(n)-1 ) with no repeated prime factors. Then F(n) divides A because F(n) is a product of primes where the prime factors form a superset of the prime factors of A.

Can you complete the proof?

Let A be a composite number in [ 2, F(n)-1 ) with repeated prime factors. Let p be a repeated prime.

...

[Can you complete the proof?]

Filed Under: Mathematics Tagged With: , , ,

Factorials, prime numbers and a puzzle

March 26, 2009 By

There is this interesting math tidbit about composite numbers and factorials by Ned Batchelder. Now prime numbers never appear consecutively (except for 2 and 3). Ned then answered this question: how many composites can appear consecutively?

His explanation involves the use of factorials, and you can read about it using the link above. His explanation also gave me something to think about…

Now the factorial of n, denoted by n! is
1*2*3*4* … *(n-1)*n
which is a product of 1 through n.

Let’s define a function F such that F(n) is the product of
(1st prime)*(2nd prime)* … * (nth prime)

For example, the first few prime numbers are 2, 3, 5, 7, 11, 13. So
F(1)=2,
F(2)=2*3=6, and
F(5)=2*3*5*7*11=2310.
This is different from factorial primes (I was actually going to name this special function “prime factorial”).

Now, n! is divisible by 2, n! is divisible by 3 and n! is divisible by 4.
F(n) is divisible by 2, F(n) is divisible by 3, but F(n) is not divisible by 4!

My question: Describe the group of numbers where F(n) cannot divide, in as plain an English as possible. This group of numbers will necessarily be between 2 and F(n)-1.

Your knee-jerk answer could be “all composite numbers between 2 and F(n)-1!”. Ahh, but F(n) is divisible by 10, and 10 is a composite number (assumption, n is a fairly large number, say greater than 5). This puzzle should be easy to figure out. Articulation of the solution into a couple of sentences might be harder…

[Vincent is currently away on vacation. He asked me, the blog, to take over for a while. Using a proprietary algorithm involving language semantics and neural networks (written by me), I came up with the blog post you've just read. It even seems coherent! I mean, uh, of course it makes sense. Oh, the things I do for my master... He'd better come back with lots of pictures for me to post, or he and I are going to have words...]

Filed Under: Mathematics Tagged With: , , ,

Every user query is a puzzle

February 27, 2009 By

The user didn’t really mean to give you a level 5 puzzle to solve. But that’s what it is. Every time the user asks you to help him solve a software related problem, he’s giving you a puzzle.

Sometimes, it’s a level 1 puzzle, where you don’t even need to fire up your code editor to glance through the code to answer, or give more than a few seconds to think through. Sometimes, you have to really push for lots of hints, like clarifying the user’s query, ask for screenshots (even if sometimes they aren’t enough…), and dig through code archives.

I got a level 1.5-ish puzzle lately… The user said he couldn’t use the delete button. I fired up the application, selected a record, and indeed the delete button was disabled. On a whim, I double-clicked. The details of the selected record came up, and the delete button was enabled.

I have never seen or used that particular section of the application before. The user on the other hand, was supposed to be familiar with the application. Perhaps I’m more willing to try out typing randomly or aimlessly clicking the mouse on an application screen. I certainly typed enough asdf’s…

So, have you encountered any high level puzzles? Share in the comments.

Filed Under: Work Stuff Tagged With: ,
« Older Posts