Problems of the Week
(Courtesy of Alex Belyi.)
100 prisoners in separate secluded cells and a prison warden agree to perform the following experiment over a period of time: Each day the warden will select a prisoner purely at random (it is thus possible that a prisoner may be selected multiple times as the days go by) and lead her to a room that contains nothing but a light bulb hanging from a cord from the centre of the ceiling. The prisoner led to the room that day has the option of doing one of the following three things:
- Remain silent and switch the light off if it was on.
- Remain silent and switch the light on if it was off.
- Make the statement: "All 100 prisoners have now been led to this room."
The prisoners performing this experiment cannot communicate in any way (except through on/off state of the light bulb) and they do not see who is being led to the room on any day. What strategy can the prisoners all agree on before they play the game to ensure that they will all go free? They know the game will start with the light bulb initially on.
Arrange the numbers 1 through 15, in some order, so that:
a) adjacent numbers in the sequence sum to an odd number.
b) adjacent numbers in the sequence sum to an even number.
c) three consecutive numbers in the sequence sum to an odd number.
d) three consecutive numbers in the sequence sum to an even number.
e) adjacent numbers in the sequence sum to a multiple of three.
f) three consecutive numbers in the sequence sum to a multiple of three.
g) adjacent numbers in the sequence sum to a perfect square.
a) Colour the cells of the following grid black and red so that each row contains precisely three black cells and three red cells, as does each column. [For example, the standard checkerboard pattern is one such colouring scheme. Other schemes are possible too.]
Prove that no matter your choice of colouring scheme the numbers in the red cells add to 333.
b) (Easier) Place six pennies on the grid so that each row and each column of the grid contains only one penny (that is, the pennies are like rooks in mutual "non-attack.") What can you say about the sum of the numbers covered by pennies?
a) On a 6 x 6 grid of squares, arrange six pennies and 15 dominoes so that:
i) Each row and each column of the grid contains only one penny (that is, the pennies are like rooks in mutual "non-attack.")
ii) The fifteen dominoes tile the remaining 30 squares.
b) Do the same with 5 pennies and 10 dominoes on a 5x5 grid; and four pennies and 6 dominones on a 4x4 grid.
c) Classify those numbers N for which this puzzle can be solved with N pennies and N*(N-1)/2 dominoes.
Here are two arrangements of the numbers 1 through 10:
5 2 7 9 10 1 6 3 4 8
6 5 4 2 1 9 10 8 7 3
Are these lists close to being the same? What do I mean by this? Read on:
a) Johnny decided to measure "closeness" by taking the difference of the first numbers in each list: 5 - 6 = -1; the difference of the second numbers: 2 - 5 = -3; and so on. He then decided to add up all these deviations to get the total deviation:
Total deviation = (5 -6) + (2 - 5) + (7 - 4) + ... + (8 - 3) = ???.
He reasoned that if the lists were identical, the total deviation would be zero. Any non-zero answer would be a measure of how non-identical they are.
What do you think of this approach?
b) Lashana decided that she should measure POSITIVE deviations. She could take absolute values but decided to square the numbers instead. (She decided if she ever wanted to calculus when analysing lists like these, differentiating quantities squared is easier than differentiating absolute values.)
She gets total squared deviations: (5-6)^2 + (2-5)^2 + ... + (8-3)^2 = 272.
She reasoned that a total squared deviation of zero really does mean that the lists were identical, and that a non-zero answer really is a measure of how non-identical they are.
Here's my real question: What is the biggest possible total squared deviation value two different arrangements of the numbers 1 through 10 could produce? When does that biggest value happen? (That is, what is it saying about the two lists?)
c) Find a formula for the maximal total squared deviation value that could possibly occur for lists from 1 to N.
1. The following diagram, called a "net," folds to make a cube:
whereas the following two diagrams do not:
How many essentially different nets are there that make a cube? [Each net consists of six squares connected by whole edges. "Essentially different" means to count rotations and reflections of a diagram as the same diagram.]
2. In one dimension, a line segment has 2 0-dimensional end-points.
In two dimensions, a square has 4 1-deimensional edges.
In three dimensions, a cube has 6 2-dimensional square faces.
In four dimensions, a hypercube has how many 3-dimensional cubical "faces" ?
3. Give an example of a net for a hypercube. It will consist of eight cubes connected together by faces arrange in a way that, in four-dimensional space, it folds to make a hypercube.
4. Show that there are 261 essentially different answers to question 3.
Some Lewis Carroll problems:
- No birds, except ostriches, are nine feet high.
- There are no birds in this aviary that belong to anyone but me.
- No ostrich lives on mince pies.
- I have no birds less than nine feet high.
- A plum-pudding, that is not really solid, is mere porridge.
- Every plum-pudding, served at my table, has been boiled in a cloth.
- A plum-pudding that is mere porridge is indistinguishable from soup.
- No plum-puddings are really solid, except what are served at my table.
- No interesting poems are unpopular among people of real taste.
- No modern poetry is free from affectation.
- All your poems are on the subject of soap-bubbles.
- No affected poetry is popular among people of real taste.
- No ancient poem is on the subject of soap-bubbles.
1. In how many ways can I arrange the letters H and T to form a string of ten letters with no two consecutive H's?
2. What is the probability of tossing a coin ten times and never seeing two heads in a row?
3. What is the sum: 1/4 + 1/8 + 2/16 + 3/32 + 5/64 + 8/128 + 13/256 + 21/512 + ... ?
- How many different subsets of the 26 letters of the alphabet are there?
- How many of these subsets do not contain a pair of consecutive letters? (Do not regard Z and A as consecutive.)
- Here's a honeycomb. In how many different ways can you walk from
"start" to "end" only ever moving one cell to the right, one cell
diagonally down, or one cell diagonally up?
- Let P_2(n) be the number of ordered partitions of n if the number
“1” can be
coloured one of two colours, red or blue say. (All other digits can be
written only in black.) For example, P_2(3)=13
“3” = 3, 1(red) + 2, 1(blue) + 2, 2 + 1(red), 2 + 1(blue),
1(red) + 1(red) + 1(red), 1(red) + 1(red) + 1(blue), etc.
- The language "ABEEBA" has just three letters: A, B and E. Every
combination of letters is word except those that have an A followed by
an E. How many n letter words are there in this language?
- A circle of radius 1 rolls inside a circle of radius 2. Describe the path traced by a piece of gum stuck to the rim of the inner wheel.
- The Statue of Liberty is 46 feet tall, and stands on a platform 47 feet tall. How far from the statue along the ground should I stand to get the largest viewing angle possible? (The "viewing angle" is the angle between the line connecting my eyes to the statue's feet, and the line connecting my eyes to the statue's crown.)
A farmer grows bananas in a desert oasis. He has 3000 bananas and market is 1000 miles away. He has only a camel to transport bananas, but there are two problems:
i) The camel can only carry at most 1000 bananas at a time
ii) The camel will only walk if munching on a banana. He eats one banana for every mile he walks.
What is the maximum number of bananas the farmer can get to market using ONLY the camel to transport them?
Hint: The farmer may carry bananas part-way, drop off a supply of bananas, walk back to start (make sure the camel still has enough bananas to do this!), re-boost his supply, and so on. Following a method of this ilk it is possible to get OVER 500 bananas to market. Can you see how?
Acknowledgment: My thanks to Dr. Terry Gaffney of Northeastern University for introducing me to this great problem.
Consider the magic square:
5 22 18
28 15 2
12 8 25
Spell out each number and count how many letters it uses (e.g. "12" is written "twelve" which uses six letters) and replace each entry by its letter count. This gives a new square:
4 9 8
11 7 3
6 5 10
Check - it too is magic!!
- Prove that there are infinitely many (non-trivial) alpha-numeric magic squares.
- Create your own interesting alpha-numeric magic square.
- Can you create a bilingual alpha-numeric magic square, that is,
one that works for both French and English say?
True or False?
1) There exist two distinct powers of two whose sum is a power of two.
2) There exists a power of two (different from 1) that equals a power of six.
3) There exist two distinct powers of two that differ by a multiple of 11.
4) There exist two distinct powers of 10 that differ by a multiple of 17.
5) The product of any five consecutive integers is divisible by 60.
6) There exist three non-zero consecutive integers whose product is a square number.
7) 403 is the sum of two square numbers.
8) There exist to distinct square numbers that differ by a multiple of 403.
9) There exist two non-zero consecutive integers that have the same product as three consecutive integers.