Happy New Year! Today is the first day of the Year of the Rooster, celebrated by billions of people around the world. One tradition in Chinese and Vietnamese culture is giving money in small red envelopes, usually to children. Both the money and the red color of the envelope are said to bring good luck to the child for the new year.
This year, Anh is stuffing envelopes with cash in preparation for the new year celebration; each envelope can have any amount of whole dollars ($1, $2, $3, ...) in it. She is going to give some envelopes (one or more) to her niece Mai but she's not sure how much money she wants to give yet. She wants to be prepared to give her any whole dollar amount from $1 to $14 without putting more money in or taking money out of the envelopes she has already prepared.
What is the smallest number of envelopes she has to prepare to be able to give Mai any amount in that range?
Ready for the answer?
This year, Anh is stuffing envelopes with cash in preparation for the new year celebration; each envelope can have any amount of whole dollars ($1, $2, $3, ...) in it. She is going to give some envelopes (one or more) to her niece Mai but she's not sure how much money she wants to give yet. She wants to be prepared to give her any whole dollar amount from $1 to $14 without putting more money in or taking money out of the envelopes she has already prepared.
What is the smallest number of envelopes she has to prepare to be able to give Mai any amount in that range?
Ready for the answer?
This is a very easy question if you know a little bit about binary numbers: those 1s and 0s that fly by in sci fi movies about hackers. Those 1s and 0s represent values that are the powers of 2, and can be used to represent any whole number up to 2n - 1 where n is the number of 1s and 0s you have.
In this case, each envelope represents a 1 or a 0. 1 represents an envelope Anh gives to Mai, and 0 represents an envelope she doesn't give to Mai.
To give Mai any whole dollar amount from $1 to $14, Anh needs to prepare 4 envelopes with the powers of 2 in them: $1, $2, $4, and $8. With those, she can actually make any amount from $1 to $(24 - 1), or $15.
Astute solvers will note that because we're only trying to cover up to $14, the last envelope can have $7 in it.
Comments