challenges « The Math Less Traveled

Archive for the ‘challenges’ Category

More cookies

Tuesday, July 27th, 2010

I recently received the following interesting problem from Shadowcat, which is a generalization of the cookie problem I’ve written about previously. We again want to count the ways to distribute identical cookies to non-identical students, with the twist that we impose an upper bound on the number of cookies received by each student (quite reasonable if we want to be mindful of the students’ nutrition):

Imagine that instead of ten cookies and five students, you have fifty cookies and ten students. (It’s easier to quantify this situation using larger numbers.) How many ways can you distribute these cookies among the students so that no student has any more than ten cookies?

Students may be given any number of cookies less than or equal to ten, including zero. The cookies are identical, just as in the original problem, so, as with the original problem, it doesn’t matter which cookie the student gets, just how many. But the students, again, are *not* identical, so which student gets a specific number of cookies is important.

I unfortunately haven’t had much time to think about it yet. Feel free to leave comments, thoughts, partial solutions, and solutions in the comments!

Tags: cookies, counting, students
Posted in arithmetic, challenges, counting | 9 Comments »

Optimal change-carrying

Thursday, June 24th, 2010

Recently Michael left the following challenge in a comment:

I’ve been trying to optimize my change-carrying habits. What is the smallest amount of quarters, dimes, nickels and pennies one can carry while still being able to give perfect change (two decimals)?

It’s not 100% clear what Michael meant by “give perfect change”, but let’s assume the goal is to be able to make any amount between 1 and 99 cents. For non-US readers, US coins are worth 1, 5, 10, and 25 cents.

Some questions for exploration:

What’s the smallest number of coins you can come up with that works? What are they?
Are there multiple solutions, or is the solution unique?
How can you prove that a proposed solution is optimal? Unique?
Can you answer the question for a different system of coins? For example, I am currently spending the summer in Cambridge, England, where coins are worth 1, 2, 5, 10, 20, and 50 pence. What if you also include the 1- and 2-pound (100 and 200 pence) coins, and want to be able to make change for every amount up to 5 pounds (the smallest note)?
The US and UK coin systems both have the property that a greedy strategy works for giving the smallest amount of change. That is, to make a certain amount of change with the smallest possible number of coins, you can just keep picking the biggest coin less than or equal to the remaining amount. What about coin systems without this property? Do they make this problem harder? Easier?
If you got to design your own system of coins with whatever denominations you wanted, how would you design it so that the minimum number of coins needed to make all amounts between 1 and 99 cents is as small as possible? As LARGE as possible?
What are some methodologies for attacking this sort of question in general?

Feel free to come up with your own generalizations as well. Post questions, discussion, and solutions in the comments but don’t peek until you’ve tried solving it! I’ve posted another change-making puzzle before as well; the discussion there might also give you ideas.

Tags: change, minimum
Posted in arithmetic, challenges, counting | 11 Comments »

The broken weight problem: solutions and further exploration

Tuesday, May 11th, 2010

First of all, let me say to all my readers how fantastic it felt to post a puzzle, after not posting anything for two months, and get eighteen thoughtful, insightful comments in just three days; it’s every blogger’s dream. You all are fantastic and make this a lot of fun — thanks for reading!

I thought I’d take a post just to summarize some of the responses and solutions to the broken weight problem. As many commenters realized, the solution is that the weights are of sizes 1, 3, 9, and 27. Hmm, powers of three… coincidence? Of course not!

As several commenters noted, something involving base three readily presents itself if we realize that there are three possibilities for each weight: it can be on the left of the balance scale, on the right, or not on the scale at all. Since one side of the scale corresponds to adding the weight and the other side to subtracting, we are essentially writing numbers in base three, but using the digits -1, 0, and 1 instead of the usual 0, 1, 2. For example, 25 can be written as 10(-1)1, that is, $1 \cdot 27 + 0 \cdot 9 - 1 \cdot 3 + 1 \cdot 1$ (if we were really going to use this system we’d want to come up with a better symbol for -1). In fact, this is known as balanced ternary, and it is a fact (as proved by a few commenters) that n digits of balanced ternary allow us to uniquely represent every integer between $\pm \frac{3^n - 1}{2}$ . With four digits (as in the problem) we can uniquely represent every integer between -40 and 40. There was a bit of confusion in the comments about being able to represent some integers in more than one way, but I think if you try it out you will find that this is not the case.

From this problem (generalizing it to arbitrary numbers of weights), we can see that

$\displaystyle 1 + 3 + \dots + 3^{n-1} = \frac{3^n - 1}{2}.$

JM noted that this generalizes to

$\displaystyle 1 + b + b^2 + \dots + b^{n-1} = \frac{b^n - 1}{b - 1}$

and wondered whether this has anything to do with solving the problem, or with problems like it. Indeed it does; here’s one for you: suppose you are tasked with designing a set of weights. The weights should make it possible to weigh as many different integer weights as possible, without leaving any out, just like the weights 1, 3, 9, 27 make it possible to weigh every integer weight up to 40 without leaving any out. The one difference is that you want to have two identical copies of each weight. What is the best you can do?

I’ve left the problem slightly vague on purpose, but I hope you will have fun solving it and figuring out what it has to do with JM’s observation! Can you come up with other interesting generalizations of the problem?

Finally, Sam Shah posted a link to a description of his experience using the problem in a real-life problem-solving session.

Tags: balanced, broken, puzzle, ternary, weight
Posted in arithmetic, challenges, number theory, solutions | 6 Comments »

The broken weight problem

Saturday, May 1st, 2010

Here’s a fantastic problem I recently heard. Apparently it was first posed by Claude Gaspard Bachet de Méziriac in a book of arithmetic problems published in 1612, and can also be found in Heinrich Dorrie’s 100 Great Problems of Elementary Mathematics.

A merchant had a forty pound measuring weight that broke into four pieces as the result of a fall. When the pieces were subsequently weighed, it was found that the weight of each piece was a whole number of pounds and that the four pieces could be used to weigh every integral weight between 1 and 40 pounds. What were the weights of the pieces?

Note that since this was a 17th-century merchant, he of course used a balance scale to weigh things. So, for example, he could use a 1-pound weight and a 4-pound weight to weigh a 3-pound object, by placing the 3-pound object and 1-pound weight on one side of the scale, and the 4-pound weight on the other side.

The solution to this puzzle is really fascinating and leads into all sorts of fun generalizations and other topics; I’ll write more later. For now, as always, feel free to leave questions, observations, and solutions in the comments (so don’t look at the comments before you’ve solved it if you don’t want to see the answer!).

Tags: puzzle, weights
Posted in arithmetic, challenges, number theory, puzzles | 22 Comments »

The haybaler

Wednesday, December 16th, 2009

At Penn Alexander’s math club yesterday, the students worked on a fun puzzle that I’d never seen before. It goes like this:

You have five bales of hay.

For some reason, instead of being weighed individually, they were weighed in all possible combinations of two. The weights of each of these combinations were written down and arranged in numerical order, without keeping track of which weight matched which pair of bales. The weights, in kilograms, were 80, 82, 83, 84, 85, 86, 87, 88, 90, and 91.

How much does each bale weigh? Is there a solution? Are there multiple possible solutions?

Unfortunately, the problem seemed a little beyond them (or at least, they thought it was beyond them, so they quickly lost interest) but this seems like a great problem to use in middle school or high school math classes. In middle school, keep them talking and focus on the methods they employ to try to solve it. In high school, perhaps once they solve it you could get them to try generalizing the problem (to other sets of weights, more than five bales, etc.).

Tags: bales, hay, weights
Posted in arithmetic, challenges, logic, puzzles, teaching | 10 Comments »

Who Am I?

Sunday, November 29th, 2009

An excellent puzzle from JD2718:

There are five true and five false statements about the secret number. Each pair of statements contains one true and one false statement. Find the trues, find the falses, and find the number.

1a. I have 2 digits
1b. I am even

2a. I contain a “7”
2b. I am prime

3a. I am the product of two consecutive odd integers
3b. I am one more than a perfect square

4a. I am divisible by 11
4b. I am one more than a perfect cube

5a. I am a perfect square
5b. I have 3 digits

Please don’t post the solution in a comment, so as not to spoil it for others. But feel free to leave a comment if you need a hint, or to email me if you think you have solved it and want to check if you are correct. (Actually, it’s easy to check yourself: just make sure that each of each pair of statements, exactly one is true and one is false!)

Tags: number, puzzle, secret
Posted in challenges, logic, number theory, puzzles, teaching | 13 Comments »

Hyperbinary conjecture seeking proof for a good time, long walks on the beach

Monday, October 12th, 2009

Recounting the Rationals

Recounting the Rationals, part I
Recounting the Rationals, part II (fractions grow on trees!)
Recounting the Rationals, part III
Recounting the Rationals, part IV
Recounting the Rationals, part IVb: the Euclidean Algorithm
Challenge #12: sums of powers of two
Challenge #12 solution, part II
More hyperbinary fun
Hyperbinary conjecture seeking proof for a good time, long walks on the beach
The hyperbinary sequence and the Calkin-Wilf tree

Here’s the latest progress on the hyperbinary sequence. We’re trying to figure out the inverse relation of the function : given a particular number , where does it occur in the hyperbinary sequence? That is, what are the values of for which h(k) = n ?

There are infinitely many, but in a previous post I argued why we only need to find occurrences at even positions of the sequence, which we call primary occurrences. I have no idea how easy or hard it is to give a general method for finding all primary occurrences. But some progress has been made:

Brendan proved by induction that and . These correspond to the numbers that occur right next to 1 in the sequence (we saw earlier that ).
Brendan also proved that $h(2^{p+q} - 2^q) = 1 + pq$ . This is impressive, since this pattern certainly isn’t obvious (at least, it wasn’t to me!).
Fergal Daly conjectured that the number of primary occurrences of is $\phi(n)$ . $\phi$ denotes the so-called Euler totient function; $\phi(n)$ is defined to be the number of positive integers smaller than which are relatively prime to . An explanation of this fact, if it is true (and it really looks like it might be!) would probably go a long way towards finding a general method for computing $h^{-1}$ !

Can anyone find a proof of Fergal’s conjecture?

« Previous in series | Next in series »

Tags: Euler, hyperbinary, inverse relation, totient
Posted in challenges, pattern, people, proof, sequences | 3 Comments »

More hyperbinary fun

Monday, September 28th, 2009

Recounting the Rationals

When I originally posed Challenge #12, a certain Dave posted a series of comments with some explorations and partial solutions to part II (the hyperbinary sequence). Although I gave the “solution” in my last post, no solution to any problem is ever the last word—there’s always more to explore, more connections to see! It’s worth taking another post to explore some of Dave’s discoveries and conjectures, and how they connect to my last post. I’ve used different notations, made up some terms, tried to simplify things where possible, and so on, but all the ideas in this post are fundamentally Dave’s.

First things first

Dave first noticed that

h(2^k - 1) = 1

for all $k \geq 0$ . I noted this in my previous post as well, but said only that this is “apparent” from thinking about the recursive construction I described. However, it’s worth going through a proof of this more formally; it’s a good example of a proof by induction. First, let’s recall the recurrence relation that defines the hyperbinary sequence:

$\begin{align*}h(0) &= 1 \\ h(2n+1) &= h(n) && \text{(O)}\\ h(2n+2) &= h(n+1) + h(n) && \text{(E)}\end{align*}$

Now we can show that h(2^k - 1) = 1 for $k \geq 0$ . First, the base case: when k=0 , h(2^0 - 1) = h(0) = 1 ; check!

Now, let’s suppose that h(2^k - 1) = 1 for some particular $k \geq 0$ ; this is called the inductive hypothesis, which I will abbreviate as IH. we want to show that $h(2^{k+1} - 1) = 1$ as well. $2^{k+1} - 1$ is obviously odd, so we want to apply rule (O). The only trick is to get it into the right form first:

$\begin{align*}h(2^{k+1} - 1) &= h(2^{k+1} - 2 + 1) && \text{\{ arithmetic \}}\\ &= h(2(2^k - 1) + 1) && \text{\{ factor \}}\\ &= h(2^k - 1) && \text{\{ rule (O) \}} \\ &= 1 && \text{\{ IH \}}\end{align*}$

Presto! Since the thing we wanted to show is true when k=0 and is true for k+1 whenever it is true for , by induction it must be true for all $k \geq 0$ .

Second things, third things…

But Dave then went on to notice that this sort of pattern isn’t unique to 1. For example,

$h(3 \cdot 2^k - 1) = 2$

for $k \geq 0$ , and

$h(5 \cdot 2^k - 1) = h(7 \cdot 2^k - 1) = 3$

also for $k \geq 0$ . Dave conjectured that this generalizes, and indeed it does: most generally, we can say that

$h(p \cdot 2^k - 1) = h(p - 1)$

for $k \geq 0$ . That is, once a certain number occurs at position p - 1 , it will keep occurring in a regular pattern after that, at every position of the form $p \cdot 2^k - 1$ . Note that h(2^k - 1) = 1 is a special case with p = 1 .

Why is this? Intuitively, it’s because of the “copying”—the blue numbers in my previous post. Once a number occurs, it will keep getting copied, but with the distance between the copies doubling each time. But again, this is worth proving formally. I’ll let you do this one—the proof by induction is similar to the proof above!

But why do occurrences of 1 correspond to p = 1 , and occurrences of 2 to p = 3 , and occurrences of 3 to p = 5 and p = 7 , and so on? Are there any patterns to be found here? This is what Dave explored next; let’s follow.

Primary occurrences and the inverse of h

Let’s think a little more about this equation $h(p \cdot 2^k - 1) = h(p - 1)$ . Let’s suppose that is odd (if it isn’t, we can always take another factor of two out of it to combine with the 2^k ). Notice that $p \cdot 2^k - 1$ is always odd, except when k = 0 (in which case $p \cdot 2^k - 1 = p - 1$ , which is even). Moreover, we can always write any odd number in the form $p \cdot 2^k - 1$ , where is odd: just add one, and factor out as many copies of 2 as possible. For example, $11 = 12 - 1 = 3 \cdot 2^2 - 1$ .

This means that if is any odd number, we can write it in the form $q = p \cdot 2^k - 1$ , and so h(q) = h(p-1) : that is, every odd position in the hyperbinary sequence is just copied from an earlier even position. Of course, this can also be seen from the recursive construction in my previous post; but now we have really proved it! And what about the even positions? The values of the hyperbinary sequence at even positions are obtained by adding, rather than copying. If occurs at an even position, we will call it a primary occurrence of .

The nice thing about primary occurrences is that (a) there are only finitely many primary occurrences of any particular (challenge: prove this!), and (b) once we know the positions of the primary occurrences of , we know the positions of all the occurrences of : they are at positions of the form $p \cdot 2^k - 1$ , where p - 1 is a primary occurrence.

So, given , can we find all its primary occurrences? Essentially we are asking if we can compute $h^{-1}$ (by which I mean the inverse relation of ; since is not injective its inverse is obviously not a function), but leaving out non-primary occurrences since we can easily find those from primary ones. Let’s start by making a table with some small values of :

n	Primary occurrences
1	0
2	2
3	4, 6
4	8, 14
5	10, 12, 16, 30
6	32, 62
7	18, 22, 24, 28, 64, 126
8	20, 26, 128, 254
9	34, 46, 48, 60, 256, 510
10	38, 56, 512, 1022
11	36, 40, 54, 58, 66, 94, 96, 124, 1024, 2046
12	44, 50, 2048, 4094
13	42, 52, 70, 78, 112, 120, 130, 190, 192, 252, 4096, 8190
14	68, 80, 110, 122, 8192, 16382
15	72, 118, 258, 382, 384, 508, 16384, 32766
16	92, 98, 134, 158, 224, 248, 32768, 65534

Do you see any patterns? If so, can you prove them by induction? I’ll talk about a few in my next post. But I still don’t know whether there’s an effective way to compute $h^{-1}(n)$ !

« Previous in series | Next in series »

Tags: hyperbinary, induction
Posted in challenges, induction, pattern, proof, recursion, sequences, solutions | 11 Comments »

Challenge #12 solution, part II

Saturday, September 19th, 2009

Recounting the Rationals

Yes, that’s right, that Challenge #12, posted one year, five months, and a day ago. You see, I have this nasty habit of starting things and not finishing them… well, better late than never!

Question two of the aforementioned challenge asked this:

Given a positive integer n, in how many ways can n be written as a sum of powers of two, when each power is allowed to occur at most twice? Say denotes the number of different ways to write n as a sum of powers of two with at most two copies of each power allowed. What can you say about the function h?

These representations using at most two copies of each power of two are sometimes called hyperbinary representations. For example, 11 can be written as 2^3 + 2^1 + 2^0 or as 2^2 + 2^2 + 2^1 + 2^0 . It turns out these are the only hyperbinary representations of 11, so h(11) = 2 .

How to analyze this? We can use a similar approach to that outlined in the solution to part III (which asked a similar question, but allowing any number of copies of each power of two). First let’s think about odd numbers, that is, numbers of the form 2n + 1 . Any representation of an odd number must include an odd number of copies of 2^0 (otherwise the sum won’t be odd!), but since at most two copies are allowed, there must be exactly one copy of 2^0 . If we take away the 2^0 and divide everything else by two, we get a valid representation of . The reverse works as well: if we start with any valid representation of , multiply everything by two, and add a copy of 2^0 , we get a valid representation of 2n + 1 . This means that

h(2n+1) = h(n) .

What about even numbers? A valid representation of 2n + 2 has either two copies of 2^0 , or none. If it has none, we can simply divide by two to get a valid representation of n + 1 (and vice versa); if two, we can take away the copies of 2^0 and then divide by two to get a representation of , and vice versa. Therefore,

h(2n+2) = h(n+1) + h(n) .

These two equations, h(2n+1) = h(n) and h(2n+2) = h(n+1) + h(n) , along with the fact that h(0) = 1 , are enough to completely characterize h(n) . We can easily compute h(n) for the first few values of :

1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,1…

It’s immediately striking, of course, that h(n) isn’t strictly increasing: that is, just because m > n doesn’t mean h(m) > h(n) . In fact, even as the values of h(n) continue to get bigger on average, there are still some values of 1 hiding in there. In fact, h(0) = h(1) = h(3) = h(7) = h(15) = 1 , and the obvious conjecture is that h(2^k - 1) = 1 for every $k \geq 0$ .

The next thing we notice, after staring a bit, is that the h(n) sequence contains a lot of palindromes! Every section sandwiched in between two 1’s seems to read the same forwards and backwards. Let’s make some graphs so we can see these patterns more easily: below I’ve made graphs showing h(n) as goes from 1 to 100, 1000, and 10000, respectively.

The hyperbinary sequence through n=100

The hyperbinary sequence through n=1000

The hyperbinary sequence through n=10000

Pretty! We can clearly see the symmetric structure here, and the way that it occasionally (every 2^k - 1 ) jumps back down to 1.

Here’s another way to think about building the sequence. We start with the first two elements:

$1,\rrr{1}$

Now we copy the red part onto the end of the sequence (the copy will be blue), leaving a blank space in front of each blue number:

$1,\rrr{1},\blnk,\bbb{1}$

Now we fill in each blank (in green) by adding the two numbers on either side of it:

$1,\rrr{1},\gggr{2},\bbb{1}$

Now the blue and green part becomes the new red part:

$1,1,\rrr{2},\rrr{1}$

Now we repeat! Copy the red part to the end, leaving a blank in front of each copied number:

$1,1,\rrr{2},\rrr{1},\blnk,\bbb{2},\blnk,\bbb{1}$

Fill in each blank by adding the two numbers on either side:

$1,1,\rrr{2},\rrr{1},\gggr{3},\bbb{2},\gggr{3},\bbb{1}$

And again: blue and green become the new reds, copy the red numbers to the end with a blank in front of each:

$1,1,2,1,\rrr{3},\rrr{2},\rrr{3},\rrr{1},\blnk,\bbb{3},\blnk,\bbb{2},\blnk,\bbb{3},\blnk,\bbb{1}$

And fill in the blanks by adding:

$1,1,2,1,\rrr{3},\rrr{2},\rrr{3},\rrr{1},\gggr{4},\bbb{3},\gggr{5},\bbb{2},\gggr{5},\bbb{3},\gggr{4},\bbb{1}$

And so on. It takes a little bit of thought, but it can be seen that the method I’ve described here is really just a different way of expressing the equations h(2n+1) = h(n) and h(2n+2) = h(n+1) + h(n) ! But thinking about it this way makes it apparent why a 1 always shows up at h(2^k - 1) , and also why we end up with palindromes.

I’ll stop there for now; in an upcoming post I’ll bring things full circle by showing how these numbers relate to the Calkin-Wilf tree of rationals.

« Previous in series | Next in series »

Tags: binary, hyperbinary
Posted in challenges, counting, induction, pattern, sequences, solutions | 14 Comments »

MMM #33: Super divisible

Monday, May 25th, 2009

This week’s Monday Math Madness is up at Wild About Math!. Looks like a fairly accessible problem this week:

What’s the prime factorization of the smallest whole number that is divisible by all integers from 1 up to and including 50?

Submit an answer (see the post for instructions), and maybe win a prize!

Tags: divisible, factorization, smallest
Posted in challenges, links, number theory, primes | No Comments »

The Math Less Traveled

Archive for the ‘challenges’ Category

More cookies

Optimal change-carrying

The broken weight problem: solutions and further exploration

The broken weight problem

The haybaler

Who Am I?

Hyperbinary conjecture seeking proof for a good time, long walks on the beach

Recounting the Rationals

More hyperbinary fun

Recounting the Rationals

First things first

Second things, third things…

Primary occurrences and the inverse of h

Challenge #12 solution, part II

Recounting the Rationals

MMM #33: Super divisible

Pages

Archives

Categories