Interesting Puzzles, Problems, and Conundra

[goodmathproblems]

I’m thinking of an integer between 1 and 100, inclusive. You have 10 guesses to guess my number. However, I am permitted to lie on at most one of the questions (I can also just tell the truth all the time if I so choose). Your questions can only be of the form “is the number in this set” - you can’t ask self-referential things to force a lie or ask about future plans. 

Is it possible to determine my number with certainty?

(Harder: if 100 is replaced with some other number of possible answers, where is the boundary between when this can and cannot be done?)

Heard from a coworker, who told me he saw it in a problem book. 

[goodmathproblems]

There are 5 houses of different prices and heights. The house that's taller than the house that's more expensive than the house that's shorter than the house that's cheaper than the house that's blue is red. Deduce everything you can.

Originally from /u/jacoblance, found via this comment on reddit. The solution relies on a fairly reasonable assumption about the language used in the problem, which I think doesn’t give too much away.

[goodmathproblems]

Designing a teleporter system

You are building your new nation in the Euclidean plane, and need to create n cities. From every city, there are two kinds of transport: a teleporter which takes you to the nearest city, and a teleporter which takes you to the farthest city. (The cities are assumed to have pairwise distinct distances.)

For large n, how can you position your cities to bound the length of the worst-case number of teleportations required to get from one city to another?

In particular, try to get o(n), or (for a slightly harder variant) O(√n). Can you do even better? (I don't know if improving on √n is possible.)

A friend of mine came up with this puzzle, the above is as far as we’ve gotten.

[goodmathproblems]

A one-question multiple choice test:

Which of the following answers is the correct answer to this question?

None of the below

All of the below

All of the above

One of the above

None of the above

None of the above

From this post at possiblywrong.wordpress.com.

[goodmathproblems]

A 6-sided die is thrown until a 1 appears. What is the expected number of throws (including the throw giving 1) conditioned on the event that all throws gave odd numbers?

The answer is not what almost everyone who first hears this problem thinks.

From Stan Wagon’s Problem of The Week #1249.

[goodmathproblems]

Selector functions

Let A = {1,2,3,4,5} and let P be the set of all nonempty subsets of A. A function f from P to A is a “selector” function if f(B) is in B, and f(B union C) is either equal to f(B) or f(C‌). How many selector functions are there?

From the Puzzle Column at the MSRI newsletter Emissary’s Fall 2018 issue, originally from a Turkish national competition.  

[goodmathproblems]

Four suspects, one of whom was known to have committed a murder, made the following statements when questioned by police. If only one of them is telling the truth, who did it?

Arby: Becky did it. Becky: Ducky did it. Cindy: I didn’t do it. Ducky: Becky is lying.

From the 2000 Indiana College Mathematics Competition, found via Futility Closet here.

[goodmathproblems]

Forefathers

Twenty children attend a rural elementary school. Every two children have a grandfather in common. Prove that some grandfather has not less than 14 grandchildren in this school.

From the 1996 mathematical olympiad of the Republic of Moldova, found via Futility Closet here.

[goodmathproblems]

Detective Radstein is investigating a robbery. He apprehends three suspects: Anne, Bill, and Caroline. The detective knows that no one else could have participated in the robbery. During the interrogation the suspects make the following statements:

Anne: I didn’t do it. Bill did it alone.

Bill: I didn’t do it. Caroline did it.

Caroline: I didn’t do it. Bill did it.

Detective Radstein also discovered that all three suspects are members of a club called The Halfsies. Every time they speak, they make two statements, one of which is a lie and the other one is true. Who committed the robbery?

From this post on Tanya Khovanova’s math blog.

[goodmathproblems]

Suppose we have a nonempty finite planar graph G. We color the edges red and blue. Prove that there is some vertex V of G around which the red and blue edges form two contiguous blocks; that is, there is an edge from which, proceeding clockwise around the edges emanating from V, the colors are red, red, red, red, blue, blue, blue (or something of that form, with either the list of reds or blues potentially empty).

Heard from some math-oriented friends of mine; I don’t know the origin.

[goodmathproblems]

Rearranging powers of 2

Do there exist two powers of 2 whose base-10 digits are anagrams of each other?

Found here on /r/mathriddles.

[goodmathproblems]

Coffee and doughnuts

In a certain mathematics class, if each boy purchases a coffee and each girl purchases a doughnut (all items costing an integer number of dollars), the class would spend a total of one dollar more than if each boy purchased a doughnut and each girl purchased a coffee. If there are more girls than boys in the class, what can one determine about the number of girls and the number of boys?

From the Australian Mathematical Gazette’s second Puzzle Corner.

[goodmathproblems]

A long investigation

While questioning a witness, a judge is only allowed to ask questions which are to be answered ‘yes’ or ‘no’. The judge has carefully calculated that, as long as the witness answers every question truthfully, then she can solve the case in no more than 91 questions. One or more of these questions may depend on the answers to previous questions. Show that the judge can solve the case in no more than 105 questions if it is known that the witness may answer at most one question falsely.

Your questions may encompass any past events you wish, but cannot introduce paradoxes or similar sorts of logical trickery (e.g. you can't make question 1 "Will your answer to this question be 'no'?", count it as a lie no matter what they answer, and proceed with the regular questions).

This question is from Issue 4 of the Australian Mathematical Gazette's Puzzle Corner.

[goodmathproblems]

Cutting up a cuboid (pt 2)

Same problem as yesterday, but this time with a cuboid of dimensions k × l × m. How many straight cuts does it take in general to turn it into klm 1×1×1 cubes? 

There is a nice solution and proof, but it may take some exploration to discover it. 

[goodmathproblems]

Cutting up a cube

You have a 3cm x 3cm x 3cm block of cheese, and you have a recipe that calls for 27 1cm cubes to be used instead. To accomplish this task, you have a knife which makes straight (planar) cuts, but you’re very worried about it getting too dull, so you’d like to use as few cuts as possible.

How many cuts will it take to accomplish your task? (You are allowed to rearrange the pieces after each cut, if you choose.)

This problem is fairly well-known; I’m not sure what the original source is.

[goodmathproblems]

Finding a common language

In a certain room, everyone is fluent in some subset of four languages. For any two people in the room, there exists a language they are both fluent in.

Prove that there exists a language which at least 3/5 of people in the room are fluent in.

From this post by /u/impartial_james on /r/mathriddles.

[goodmathproblems]

Rose colors every point of the real line either blue or red. Violet will perceive a point as purple if however small a neighborhood of the point is considered, there exist both a red point and a blue point in it. Is it possible that the numbers Violet sees as purple

a) are the reals,

b) are exactly the integers,

c) are exactly the rational numbers?

Source