Math and Logic Puzzles

[implosion]

@Espeonage:
Well, what about something like this?

Code: Select all

+--+--+
|12|34|
|34|21|
+--+--+
|41|X2|
|23|1X|
+--+--+

That's not a legal sudoku...

The fact that this doesn't produce a legal sudoku, yet it falls in line with the specifications you gave in your solution, means that your solution must have missed something . The first three boxes were produced in the method that you gave, but the last box isn't already determined - in fact, there's no possible number for either of the boxes marked X.

[implosion]

Okay. I'm going to answer the sudoku question now, but in a slightly different way.

Lets start with the upper-left 2x2 grid. There are 24 distinct possibilities for it (4!). Now, the lower-right grid also has 24 distinct possibilities. HOWEVER, some of these possibilities will make the remaining two grids impossible to fill in. Lets consider a sample upper-left 2x2 grid filling in of:

1 2 X X
3 4 X X
X X A B
X X C D

Now, if A and B are either 1 and 3 or 2 and 4, there will be a square in the lower-left grid which can't be filled in. So A and B are either 1 and 2 or 3 and 4 or 1 and 4 or 2 and 3. The same is true of C and D.
Similarly, {A, C} and {B, D} can't be {1, 2} or {3, 4}. So from this, we get only a few possible combinations for ABCD from the original 4!:

if A=1, B = 2 or 4 and C = 3 or 4. So this allows:
1 2
3 4,
1 4
3 2,
1 2
4 3. So 3 possibilities. Similarly, there are 3 possibilities if A is 2, 3, or 4. Therefore, there are 3*4=12 possibilities for the lower-right grid. Whatever the lower-right grid is, as it winds up, the upper-right and lower-left grids will have already been determined.

So I get 12*24 = 288, which agrees with personalidiot.

[implosion]

lol (i'm chair).

Three men, Mr. White, Mr. Gray and Mr. Black, have always hated each other. So one day, they decide to settle it like gentlemen: with guns. They stand in an equilateral triangle and take turns shooting at each other.

Mr. White hits his target a third of the time. Mr. Gray hits his target two thirds of the time. Mr. Black hits his target 100% of the time, a sure-shot. The three of them, being gentlemen, decide that they'll take turns shooting at each other with the least skilled going first. Mr. White goes first, then Mr. Gray, then Mr. Black. This cycle continues (skipping dead people of course) until only one of the three is alive. You can assume that Mr. Brown and Mr. Black will shoot at each other because they don't see Mr. White as as much of a threat.

At whom should Mr. White aim his first shot in order to maximize his odds of being the last one alive? Bonus: calculate his odds of winning when he follows your strategy.

[implosion]

He should shoot into the air. If he kills Black, to win grey must miss him, and then other stuff must happen - so his odds are worse than 1/3. If he kills noone, he wins if he hits with his next shot, or if other stuff happens - so his odds are better than 1/3.

Assuming he never accidentally kills someone, his odds are

Grey hits black:
2/3*(1/3+2/3*1/3*1/3+...)=2/3*(1/3/(1-2/3*1/3))=2/7
Grey misses black:
1/3*1/3=1/9
Total chance of winning 25/63.

Yep. And I got the same number when I did it on pencil and paper at 4 AM with a much more convoluted method, so it's probably right .

"whom" was a bit of a misnomer because "where" makes it obvious that "neither of them" is a choice.

[implosion]

Assuming a totally solid earth, infinite. You can be at the north pole, or three miles north of a spot where the radius of the circle that you'll walk in is 3/n miles, where n is a whole number (so 3 miles, 1.5 miles, 1 mile, .75 miles, .6 miles, .5 miles, etc). At 3 miles, you'll make a full revolution. At 1.5 miles, you'll make two. at 1 mile, you'll make three. At 1/n miles, you'll make n revolutions.

In fact, each n has infinitely many starting points. There are just specific longitudes (or latitudes, i get them mixed up) that you have to start from. You can be anywhere on that latitudinal/longitudinal circle, and there are infinitely many circles.

[implosion]

What is the square root of four?

What is the area of a regular n-gon (an equilateral, equiangular, n-sided polygon) with side length x in terms of x and n?
I derived this in chemistry once when i was really, really bored.

[implosion]

digi's solution to mine appears to work, although it's different from the one i used before (of course, mine was some weird thing involving the law of sines, SO )

[implosion]

well, i got the hint from the maze.
The hint:

GO BLINKING ACTOR IN LABYRINTH

How to get it:

The maze is a 26x26 grid. Every column is a different letter in the clue. Look at where the paths intersect. The first column is in the 7th row, so G. the next one is the 15th row, so O... etc.

[implosion]

I get 100(pi/3 + 1 - sqrt(3)), or approximately 31.5. Which looks about right.

Consider one of the circles (i used the lower-left one). It's a LOT easier with a figure, which i made with a graphing program. Using the lower-left circle, calculate the upper-right quadrant's area (and multiply by four in the end). To do that, first you have to find the angle between the lines that go from (-5, -5) to the two relevant points of intersection of the circles. That angle winds up being 30 degrees. Then you have to find the area of the kite that's part of the sector of the circle but isn't part of what you want (again, easier with a figure). That kite's area winds up being 25(sqrt(3) - 1). Subtract that from the area of the sector, and multiply by four.

[implosion]

Suppose that we want to make a 3x3 grid of numbers so that the first two numbers in each row add to the third, and the first two numbers in each column multiply to the third.

Suppose further that the following three numbers are fixed in the grid:

X | 3 | X
----------
2 | Y | X
----------
X | X | 5

The 2, 3, and 5 are fixed. List all possible values of Y such that the grid can exist as written. The X's can be anything as long as the criterion in the first sentence of the puzzle is met (they can be different, obviously).

More generally, if we replace 3, 2, and 5 with a, b, and c, then what must Y equal in terms of a, b and c?

[implosion]

yes.

[implosion]

Well, there are 13 possible rotations of the table. Each of the 13 people has to be in their correct seat in exactly one of those rotations. Therefore, across all 13 rotations, there must be exactly 13 people seated correctly. There are none in the current rotation, which leaves 12 rotations and 13 correctly seated people. By the pigeonhole principle, at least one of those rotations has to have at least 2 correctly seated people.

Also, y=-a+c as a formula doesn't work. Inspir's values were correct - note that there were two of them, so the formula for y has to produce 2 possible values (it winds up being a quadratic).

[implosion]

Here's another.

Quadrilateral ABCD has side lengths AB = 5, BC = 7, CD = 23, and DA = 13. Segments AC and BD both have integral length. How long are AC and BD?

[implosion]

You don't need a drawing, although it could be useful.

[implosion]

Yep.

[implosion]

I stared at this for a minute going "wth, there's no way that you can know" and then i realized that their queens are gone...
Then i still thought it was impossible, then i realized green was in check...

Two things are important above all else:
1) green is in check
2) the only moves that have been made are knight moves and king moves, because no other piece would ever have had open space to move to and no pawns ever moved.
Now, eventually, the knights captured both queens. Because of this, the kings only have two spaces that they can move between. Because of THIS, combined with observation 2, we know that:
3) every single move that has been made must have moved a piece from a black square to a white square, or vice versa.

So we consider the number of total pieces among all six kings and knights that are on black squares. At the beginning of the game, three of them are (one knight of each color and the white king). By observation 3, after white's move, an even number will be on black squares. After black's next move, an odd number will be on black squares, and so on. In this position, an even number are on black squares, and green is in check, meaning blue just moved. There are an even number of them on black squares after white's move, and blue just moved, so blue is white and green is black.

[implosion]

oh yeah rooks move like that don't they.

[implosion]

Find the area of the shape S, which is defined as the union of all points closer to the origin then to a square with vertices (1,1), (1,-1), (-1,-1), and (-1,1).

[implosion]

(in two-dimensional space, obviously)

[implosion]

nope, and nope.

[implosion]

Basically, what magua said is right, but it's a little bit more complicated because you have to figure out the right bounds of integration. Plus there's at least one other probable stumbling block which pops up. But yeah, it isn't a circle. The answer doesn't involve pi.

[implosion]

Okay, so I did it and got an answer that's numerically REALLY close to what llamarble got (4 - sqrt(2)/3)
But i just redid it and got the same thing. I think i got the intersection point wrong.

But yeah. It's a bunch of parabolas, and llamarble's answer is (i think) right.

[implosion]

By the way, i adapted this from a problem on a math contest - the original problem was a multiple choice that just asked what the shape looked like. The correct choice was "none of the above."

[implosion]

x^13/13

Wrong.

No constant of integration.

/hides

Twice my answer is more than 1, which seems unlikely.

Impossible, actually - the entire area under consideration fits within a 1x1 square with corners at (+/- .5, +/- .5)

And llamarble is right - the eighth part that you're taking isn't the entire area under the parabola. It's the area in between the parabola and the line y=x. So you have to subtract x from the integrand.

[implosion]

Bleeeeeeeegh

My first instinct was that the probability that the shortest had the first alphabetical name was 1/3, but that's probably wrong given that they're both boys...

I feel like the only easy way to do this is to list out every possibility.

OKAY. Let's call the kids a/b/c. There are 3! = 6 different possible ways to arrange them from short to tall and alphabetically. There are also 8 possible permutations of gender. Actually we only care about the shortest/first, so there's 3 possibilities for each of those. Obviously some of the possibilities will be eliminated by the problem's constraints. And i think we can assume without loss of generality that a is the shortest since we haven't distinguished the 3 at all.

So we know that a is a boy. Note that, for instance, BGB would mean "a is a boy, b is a girl, c is a boy". So all possibilities follow:

a is first alphabetically: BBB/BBG/BGB/BGG
b is first: BBB/BBG
c is first: BBB/BGB

So there are 8 possible permutations of everything, and 5 have girls.

5/8.

[implosion]

i THINK that i'm right here. But god, xdaamno, you accidentally opened a pandora's box here...

Tazaro, the problem (i think) with that reasoning is that those two events aren't actually completely independent. Given that the shortest is a boy, the probabilities are skewed towards there being more boys than girls. This alone makes it more likely that the first alphabetically is a boy.

[implosion]

Those 36 permutations aren't equally likely >_>. I think. Let's just take two examples: 1A-2B-3C and 1B-2A-3C.

Let's add in the possible genders to these. The possibilities for the first are:

1AM-2BM-3CM, 1AM-2BM-3CF, 1AM-2BF-3CM, 1AM-2BF-3CF.

The second:

1BM-2AM-3CM, 1BM-2AM-3CF,

Since anything with a 1 or an A must be male. So there are twice as many possibilities within the first permutation, so it's twice as likely to occur. I think.

[implosion]

oh junpei...

that puzzle was BASED on the gameshow. The key difference is that the audience voted on it instead of the gameshow host revealing it - so the car could have been revealed. In this case, no additional information was generated about door 3 when door 2 was opened, because it was opened randomly - ergo, doors 1 and 3 are equivalent.

[implosion]

So let's say that anton always tells the truth. Then he did, in fact, claim that he didn't steal the watch, and when he claimed that, he was telling the truth, and therefore, he is innocent. In this case, he'll answer no to the second question, obviously, because he can't have claimed a lie.

If he always lies, then the first question doesn't tell us anything...

[implosion]

Here's a fun one i just remembered. Knowledge of poker hands is necessary.

Consider the following 2-player variant of 5-card draw. Rather than having the cards dealt out randomly, the entire deck is spread out

face-up

so that both players can see the entire deck. Player one now chooses 5 cards for his initial hand, in plain view of player two. After this, player two chooses 5 cards for his initial hand, in plain view of player one. So both players know each others' hands. After this, player one is allowed to discard any number of cards (none, all five, or anything in between) from his hand into a discard pile (which player two can see), and choose that many new cards from the deck. Player two can then do the same, putting cards in the discard pile and drawing from the deck. After this, whoever has the better poker hand wins, or if they're the same, then they tie. Can either player guarantee a win? If not, how can either player guarantee a tie?

[implosion]

Correct.

[implosion]

Spoiler:

I'm assuming that "the oldest daughter has blue eyes" gives away that there is an oldest daughter. since it isn't enough information, there have to be two ways to factor 36 so that the factors add up to the same thing... also, one of those ways has to have a tie for oldest. So the different ways to factor 36 with a repeated product:
1*1*36
2*2*9
3*3*4
6*6*1
and the second and fourth of these both add up to 13.

So they're 2, 2, and 9.

This doesn't preclude other solutions to the puzzle, but the fact that she knows their ages from that info implies that the solution is unique.

[implosion]

Two players, John and Jane, are each given a slip of paper with a positive integer on it by a third person. The third person tells them that the difference between their numbers is exactly one. He then asks the following questions in the following order, and they receive these answers:

He asks John, "do you know what Jane's number is?" John answers, "no."
Then he asks Jane, "do you know what John's number is?" Jane answers, "no."
Then he asks John, "do you know what Jane's number is?" John answers, "no."
Then he asks Jane, "do you know what John's number is?" Jane answers, "no."
Then he asks John, "do you know what Jane's number is?" John answers, "Yes."

What numbers were they both given if we assume that John's number is odd?
What numbers were they both given if we assume that John's number is even?

[implosion]

Kagelord is correct.

Junpei: 0 isn't considered positive or negative.

[implosion]

Got it by inspection.

x = 6, y = 2, z = 9

[implosion]

Yeah, my line of thought was more:

first, try triples that come to mind that will solve the first and third equations (not counting the inequalities) and see if they solve the second. I was also assuming they were integers.

Eventually I realized the second equation implied z > z^(1/y), which in turn implied y > 1, like Who said. At that point I assumed y was 2 and tried various possible square numbers for z, and voila~

[implosion]

New one.

Find, with proof, the smallest positive integer k such that any set containing exactly k (not necessarily distinct) positive integers must contain some subset of 9 (also not necessarily distinct) integers which sums to a value divisible by 9.

[implosion]

I don't quite follow that line of reasoning, in particular what you mean by "now with the combinations possible."

It isn't the line of reasoning that I know works, although, if it does work, then absolutely (the answer does wind up being 17).

As a hint for the line of reasoning that I know does work,

solve a smaller version of the problem then use it as a lemma. Sudo is also on the right track in that the pidgeonhole principle (or something similar) is rather useful.

[implosion]

More specific hint:

You don't need to consider the general case. Only the specific case of n=3 instead of 9. Once you've solved the case for n=3, think about how you can apply that to the n=9 case.

[implosion]

Spoiler: for 1:

(1/3) * (1/4 + 1/4 + 1/5). too lazy to work out fraction.

Counterpuzzle: suppose the marble you pulled out is white. What's the probability that the bag you took was the one with 5 marbles?

Spoiler: for 2:

horrible python code says 972. Can't be assed to do it in an elegant way~

Spoiler: for 3:

if the number is even, at least two people are lying (serra/stranger), so it's odd. Also its digits have to be different, because otherwise 11 divides it and 11 is congruent to 3 mod 4 (so sudo would be lying) and either SC or SK would be lying.

If the first digit is even, then the second digit must be 7 or otherwise sci and SK are lying. 27 implies SC lying, 47 implies serra lying, 67 implies sudo lying, 87 implies SK lying, and all of them imply SK lying, so both digits are odd and different.

If neither digit is 7 (i.e. if sci lied) then it has to be a twin prime based on serra/SC; the only 2-digit twin primes are (copied from wikipedia) (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73). 11's digits are the same, 13 means SK lied, 17 we don't care about, 19 means SK lied, 29 has an even digit, 31 means SK lied, 41/43 have even digits, 59 means sudo lied, 61 has an even digit, 71 we don't care about, 73 we don't care about. So Scigatt told the truth.

If sudo lied then it still has to be a twin prime, and one with 7 in it. only possibilities are 17 and 71, both of which imply that SK lied. So sudo told the truth.

If SK lied it's also a twin prime, and also one with 7 in it, so 17 or 71. 17 would let everyone but SK be telling the truth; one of the digits is 7, it differs from 19 by 2, it's prime and it's 1 + 16. So SK can be lying iff the number is 17 (71 implies sudo lied)

too lazy to check if serra/stranger could be lying but phrasing implies only one can be.

Aaaand too lazy for 4 and 5. Which is also shorthand for saying "i might be able to figure them out but nothing is immediately apparent"

[implosion]

Also answer to the puzzle that I had:

Spoiler:

The answer is 17.

First, to show that 16 doesn't work, the set containing 8 zeroes and 8 ones clearly fails.

As a smaller case, suppose you want to choose 3 numbers whose sum is divisible by 3. Process of elimination/some mild logic will show you need 5 numbers. Now, suppose you have a set of 17 numbers. Arbitrarily choose 5 of them; from those 5, choose 3 whose sum is divisible by 3. This leaves you with 14 more numbers. Do it again, leaving you with 11. Do it again, leaving you with 8. Do it again, leaving you with 5. Do it one more time, leaving you with 5 sets of 3 numbers whose sums are each divisible by 3 and two leftover numbers that you can discard. Now, each of these subsets are congruent to either 0, 3 or 6 mod 9. The same exact logic that you use for the n=3 case can be applied to see that, since you have 5 of these subsets, you can guarantee that 3 of them will sum to be congruent to 0 mod 9; and lo and behold, that subset will have 9 elements.

[implosion]

apparently when i looked at the list of twin primes that i made, i did not actually see the number 73. ~('.'~)

Here's another one (which I don't think is too hard if you can see where it's going) that I came up with recently. The third part is really the interesting one.

Suppose {a_n} is an infinite sequence of real numbers, {a_n} = a₁, a₂, ...

1) Suppose I told you that every two consecutive elements of {a_n} sum to an integer. Prove that (or just explain why, it doesn't have to be formal) the fractional part (that is, the stuff after the decimal point) of any two terms whose indices differ by an even number are the same (that is, the fractional part of all of the even terms is the same and the fractional part of all the odd terms is the same).

2) Suppose, in addition to telling you that every two consecutive elements sum to an integer, that I told you that every three consecutive elements sum to an integer. Prove that (or explain why) every element of {a_n} must be an integer.

3) Now, imagine that I replaced the numbers 2 and 3 in the previous parts with arbitrary positive integers; that is, suppose that, for some positive integers c and d, I told you that every c consecutive elements of {a_n} sum to an integer, and every d consecutive elements of {a_n} sum to an integer. Give a condition (with proof of course! Or at least some explanation) on c and d which is both necessary and sufficient to conclude that every element of {a_n} is an integer.

[implosion]

...~_~

actually i just realized an even simpler way that that fails: -.4, .4, .6...

Ignore what I gave as a "definition" and use the actual definition for fractional part

[implosion]

(That is, x - floor(x), so the fractional part of -.4 is actually .6)

[implosion]

Didn't know it was called Bézout's identity, but yes, exactly.

Additionally, generalizing, you can always guarantee that the fractional parts of the elements will be periodic with period gcd(c, d), similar to the generalization of part 1.

[implosion]

I'm bored. Let's make up a combinatorics problem!

Let m and n be positive integers, m ≤ n. For ease of notation, let M = 2m + 1 and N = 2n + 1 (so M and N are odd). You have M distinct buckets and N indistinct marbles. How many ways can you place all the marbles into the buckets so that at least one bucket has an even number of marbles?

To be clear in case of misreading: the buckets are distinct. The marbles are not.

Edit: fixed typo

[implosion]

I think there's a way to do it that shouldn't involve anything quite that complex.

[implosion]

I believe Mitillos is correct (or, at the very least, that's how it was intended to be solved and my lazy phoneread of what he wrote didn't catch any errors). Multichoose notation also would have been fine.

[implosion]

Here's one I just came up with that I *think* I have an answer for.

It's classic to see puzzles or tricks that rely on the construction of modern dice. For example, rolling a set of three dice and being able to predict the sum of the face-down faces just by looking at the faces on the top. This is accomplished through a simple trick: modern six-sided dice nearly always have their opposite faces add up to seven. So, for this puzzle, we'll assume we have a modern cubic six-sided die, with the pips on each face looking like this, for reference:

Spoiler:

Code: Select all

   .

Code: Select all

.
   
      .

Code: Select all

.
   .
      .

Code: Select all

.     .
   
.     .

Code: Select all

.     .
   .
.     .

Code: Select all

.     .
.     .
.     .

And the only other assumption we'll make is that opposite faces add up to 7.

Given only these assumptions, how many isometrically (correct me if I'm using that word wrong) distinct dice are possible? When I say isometrically distinct, I mean that two dice are isometrically distinct if one cannot be made into the other by rotating it in 3-dimensional space.

[implosion]

Yep, that's what I get. Also cool, you should be able to figure out which of those 16 classes a die belongs to with a single photograph of the die: just take a picture of the 2-3-6 corner.

Which leads me to the bonus challenge: get a photo of 16 real dice purchased/taken from different games or manufacturers or whatever (not just made by you), all distinct .

[implosion]

It might be 1. Or -1.

I can't remember. Although I solved it on the Putnam last year :p.

[implosion]

I'd remember it if I tried~

but I'd rather let someone who hasn't solved it do it.

[implosion]

Forgive me if this has been posted before but it's a great puzzle.

You might have heard of the classic envelope-swapping puzzle or paradox, where you're given an envelope with money and told that you can swap it for an envelope that contains either twice as much or half as much. This is related to that puzzle, but is a bit more general.

I'm going to choose two distinct real numbers. They could be any real numbers at all. I'm then going to tell you one of them. Your goal is to guess whether the number that I told you is greater than or less than the other number. The catch is this: you have to have

strictly greater

than a 50% chance of being correct, regardless of how I chose the numbers. You should be able to tell me what your strategy is, and no matter what numbers I choose and which one I tell you even with the knowledge of what your strategy is, you should have strictly better than 50/50 odds of being correct.

Come up with a strategy.

[implosion]

mmm... I believe Who is correct and I misstated the problem; the chooser probably just isn't allowed to choose which number they tell you, at which point Militos's solution works.

@DrDolittle the game with that post was lost to one of various crashes (it was in otters vs tigers vs sharks mafia). The creator of the swf (bbmolla) might still have it though.

[implosion]

Here's one that I mused about for a while maybe a year ago. Doesn't really have a single correct answer, just something interesting to think about.

Define a subset S of the real plane to be

acceptable

if there is no set of three colinear points that are all in S and

unacceptable

if it contains three colinear points.

Define a subset S of the real plane to be

maximally acceptable

if S is acceptable, and the addition of any point in the real plane not already in S results in an unacceptable set.

Describe at least 3 different (this is subjective) infinite collections of maximally acceptable sets, and prove that each set in each of them is maximally acceptable.

[implosion]

I believe those do both work; can you prove it?

[implosion]

Like any convex curve that is never linear works by definition, right? Just use the definition of convexity.

This is correct so long as you also specify that the curve is a loop, I believe. In particular its a generalization of bullet's first answer. You still need to explain why adding any additional point breaks it, which is why you need it to be a loop.

[implosion]

Here's a nice one I got from my friend:

Someone was hosting a Mafia game. At one point, he knew that someone had been lynched (i.e. had strictly more than half the votes); however, not who the lynched person was. He could easily find out who each person was voting, but could not look at more than one person at once. His memory is also really bad. Help him find a way which requires as little time and memory as possible to find out who was lynched!

This is a bit ambiguous (which seems intentional?)

As a computer scientist I want to interpret this as "given an array of n integers between 1 and n where the majority of them are the same, determine what the majority of them are." Which raises a couple of questions: is this array read-only or can I write to it (i.e., can I tell the people in the room "you two people put your hands down")? If I can then I have a solution that requires you to remember two names (one for where you start scanning through the room and another for who they're voting) and you tell pairs of people to put their hands down if they're voting differently, but it might require a lot of time. Obviously there are solutions that require only one pass through the array / only one scan through people, if you're allowed to remember who everyone is voting.

So then is the question really asking "can the above be done in constant memory and linear time"? Or do we want to try to do it in a single scan and only remembering two names (or fewer)? Etc.

[implosion]

Spoiler: Solution to BNL's in constant memory and one pass

I think this is probably easiest to explain with pseudocode.

Keep track of a current candidate for having the majority of votes on them, and how many votes we're counting on them that have not been "canceled." Initialize the current number of votes to 0.

Code: Select all

for each person:
    if the current number of votes is zero:
        change the current candidate to be this person's vote, and the number of votes to be one.
    otherwise, if that person is voting for the current candidate:
        increment the current number of votes
    otherwise:
        "cancel" one of the current votes with this vote by decrementing the current number of votes.

Once you're done iterating, whoever the current candidate is must have the majority because every other vote must have been canceled (either by some other random vote or by one of the majority votes). However, this does not actually tell you how much they have the majority by.

You have to keep track of one number and one name, and one additional name if we stipulate that we need to remember where we started iterating.

[implosion]

General solution:

Spoiler:

Every missionary must die exactly once so there are exactly 26 instances of a village going back to paganism.
Every village is visited at least once (by the missionary that starts there).
No village is visited three times. For instance if village X were visited three times, then village W must have been visited twice before this (because only missionary X started at village X). But the second time that village W was visited, it would have killed that missionary, so it would have to have been visited at least three times. So village W must be visited three times before village X can be visited three times. Likewise village V must be visited three times before village W can be. Follow this back around and village X must have been visited three times before it can be visited three times, so it can't have been visited three times.
So since all 26 missionaries died, and no village can have killed more than one, every village must have killed a single missionary, and since none were visited more than twice, they all remain pagan, regardless of the arrival times or order of missionaries.

[implosion]

Here's an open-ended one.

Come up with as many significantly different proofs as you can of the following fact:

If two points are chosen uniformly at random on a unit line segment, the expected value of the distance between them is 1/3.

Spoiler: Some suggested approaches:

calculus;
examining what happens if the points are on the same half of the segment or different halves;
argument from symmetry (probably the most elegant I know of).

[implosion]

Alright. I might as well necro this thread again with an old puzzle that I came up with years ago and never figured out in case it interests anyone else.

Consider the following game between Alice and Bob:

• A positive integer n is chosen.
  
• n piles of stones, labeled 1 through n, are created. Each pile starts with a number of stones equal to its label.
  
• Alice goes first.
  
• On a player's turn, if it is the kth turn of the game (starting from 1), that player must remove exactly k stones from a pile. If they cannot do so or if doing so forces them to remove the last stone in a pile, they lose and the other player wins.

For example, at n=4, it doesn't matter what move Alice makes first; bob can remove two stones from pile 4, which will leave Alice without a legal move for turn 3, so Bob will win.

For what values of n does each player win (assuming optimal play)? Can you find a general pattern? I couldn't.

[implosion]

For the actual question, I'm pretty sure Alice has a simple winning solution when

n is a multiple of 3.

. Bob may have a similar simple winning solution when

n is 1 greater than a multiple of 3

. Haven't yet thought about the remaining cases. I didn't actually write down any of my work and haven't checked to make sure any of it is correct, so my approaches might be very very wrong.

This is the same case breakdown that I think I tried to get working a loooooong time ago. I think I got stuck somewhere in the reasoning or in trying to apply it to small cases but possibly just because I wasn't following the right logic. Back when I was thinking about this problem more this breakdown of it did seem relevant.

As for algorithmic solutions I'm happy to see a correct one; when I tried to get an algorithmic solution to this problem I couldn't get one to run efficiently enough to get past n≈10ish in reasonable time (if you simply brute force to test all possible moves at every juncture then it's going to have something like O(nⁿ) runtime which is rather unfeasible).

[implosion]

I'm not quite sure how interesting I can make this but it seems somewhat interesting so why not!

Let S be some set of nonnegative integers. We'll call a sequence {a_n} of nonnegative integers

S-compliant

if two properties hold:
1) a₀ = 0,
2) The sum of any two consecutive elements of {a_n} is in S.

For a given set S, define S_i to be the set of nonnegative integers that could possibly exist as the i^th element of an S-compliant sequence. For example, if S is the even numbers, then S₀ is {0}. S₁ is the even numbers (and you should be able to see easily that S₁ = S for all sets S). S₂ is the set of all numbers that could be added to an even number to produce an even number, i.e., the set of even numbers again. So in this case every S_i after S₀ would be the even numbers.

Describe the behavior of these S_i sequences as well as you can for these sets. In particular, for which of them if any does S_i eventually equal all of the nonnegative integers?
S = {k² : k ≥ 0}
S = {2^k : k ≥ 0}
S = {k : k is congruent to 4 mod 7}
S = {k : k is congruent to 4 or 5 mod 7}
Anything else where this concept seems interesting.

[implosion]

Yeah - you haven't proven that S_n will ever contain all positive integers, you've just proven that every positive integer is a member of some S_n. Or more strongly but still formally, you've proven that for all integers k there exists an n such that if m > n then k is in S_m (that is, every integer is in every S_n after a certain point). I can see the intuitive idea of a limit here, but I don't know if that formally makes sense; I'm only familiar with limits of sequences of points in a metric space or a topological space or some other analytical structure, not in the space of subsets of S_n.

I think for the powers of 2 case, it might be easier to see what's going on

by looking at things in binary

.

(I also didn't have any other particular cases in mind.)

[implosion]

These are quite clever.

Spoiler:

Qe1

If black moves the knight, Qe8++
If black captures with or pushes the a-pawn, Qa5++ or Qxa5++
If black pushes the b-pawn, Qh1++

[implosion]

Spoiler:

Felissan is right. What I like about that puzzle is that Kd6 is the only square the King can move and still have a mate next turn, so it's a very specific wasting move you need.

Spoiler:

What's wrong with Kc5 or Kd4?

Spoiler:

Kd4 is illegal (although I also didn't realize this at first when trying to figure out why those two moves don't work).
Kc5 allows black to play Bg1, which pins white's queen.

[implosion]

Spoiler: Pardon my inexperience in solving chess problems...

...but are you sure you can't mate in two?

1. Qf3 hxg5
   
2. Rxc8

Why isn't this checkmate?

Oh, I see. Kxh5 gets him out.

No, it doesn't. Stupid me ><

Spoiler:

Kxg5 saves black.

[implosion]

Spoiler: Pardon my inexperience in solving chess problems...

...but are you sure you can't mate in two?

1. Qf3 hxg5
   
2. Rxc8

Why isn't this checkmate?

Oh, I see. Kxh5 gets him out.

No, it doesn't. Stupid me ><

Spoiler:

Kxg5 saves black.

Spoiler:

You can't capture your own pawn the last time I checked.

[

Spoiler:

Kxg5 on the first move, not the second, in lieu of hxg5.

[implosion]

After Qg8, black can play Kh4.

[implosion]

Spoiler:

After some fiddling, is the answer "something something quadratic residues mod 12? Actually scratch that, mod 24?"

The harmonica is worth $4.

We know that they bought an odd number of sheep with leftover money, therefore:
x^2 mod 24 ϵ {13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}. Quadratic residues mod 24 can be broken down into quadratic residues mod 3 (which can be 0 or 1) and residues mod 8 (which can be 0, 1, or 4) which further reduces this list to {16}. So we know that the number of dollars that the number of dollars that they have to spend must be congruent to 16 mod 24, meaning that they will buy some even number of sheep (for some amount of money that is a multiple of $24) and then use the remaining $16 to buy one more $12 sheep and a $4 lamb.

Therefore, after they sold their flocks, the man with the sheep got $8 more, so he owed the other man $4 (because all the money he gives is both lost by him and gained by the other man), which is the value of the harmonica.

[implosion]

Inspired by idle thoughts about a speedrun:

You have ten fair coins in front of you, one with each integer value from 1 to 10. You must flip each coin in increasing order of value. If a coin comes up heads, you can go onto the next coin (if coin 10 comes up heads, you're done). If a coin with value i comes up tails, you must pay i dollars, and you have to flip that coin again instead of moving on. You may instead choose to treat the coin as though it had landed on heads. You may only do this once, however, after which point you have no control and must accept every flip.

Your goal is to minimize the expected amount you have to pay. What's the best strategy and how much do you expect to pay using it?

[implosion]

I believe that's incorrect.

[implosion]

you might have misread the prompt? Pretty sure Who read it correctly.

Saving the freebie for the last coin isn't immediately optimal, because it's possible that the last coin could simply land on heads in which case it would have been better to use it earlier.

Notably if you were flipping the coins from highest-value to lowest-value, the answer would trivially be to just use it on the first coin that lands tails because you know it's the best chance you'll get. The problem here is you don't know if you'll need it for the 10-value coin because you don't know it'll land tails.

[implosion]

Who is correct.

Ircher, your ev is off because you don't pay anything when a coin lands on heads, you just go to the next coin.

[implosion]

Spoiler: 1

#1: regardless of the distribution, every pair of consecutive cars has equal likelihood of the front or rear car going faster. So initially, there will be 100 individual cars, and each of the 99 pairs of consecutive cars has probability .5 of eventually meeting and merging into one, so the expected number of clumps is 100 - .5 * 99 = 50.5.

Spoiler: 2

#2: every vertex necessarily has one incident edge of each color.

So looking at this from a first instinct kind of deal, if n=3 then it's obviously doable and if n=2 then it's obviously not, so odds are it works with odd n and not with even n :p

There are n(n-1)/2 edges and n colors, meaning there must be on average (n-1)/2 edges of each color; if n is even, then by the pigeonhole principle there must be some color that colors n/2 edges. But none of these can be incident on the same vertex by (ii), so they must together be incident on every vertex, which violates (iii). So it's impossible in the even case.

In the odd case, there will be exactly (n-1)/2 edges of each color. One way to construct this is to place the vertices in the shape of a regular n-gon in the cartesian plane.

Then, to place the edges of color c, rotate the n-gon so that there is an edge at the bottom parallel to the x-axis and the vertex at the top is the color c. Then for every pair of vertices that are horizontally aligned, join them with an edge of color c. Doing this for every vertex should result in a completely connected n-gon which corresponds to the desired graph.

[implosion]

Spoiler: 1 again

I see where I messed up.

New logic: since it's a continuous distribution the speeds are all distinct with probability 1. Wherever the slowest car is, it will lead a clump of it and everything behind it. If EV(n) is the expected number of clumps if there were n cars, then EV(n) = ((1 + EV(n-1)) + (1 + EV(n-2)) + ... + (1 + EV(n-n))) / n, which can be seen by considering each possible position of the slowest car. The base case is EV(0) = 0. All of the ones can be factored out to get that EV(n) is 1 plus the average of EV(k) over all integers k with 0 ≤ k < n.

So at this point, this is obviously the harmonic numbers and i definitely didn't look at a spoiler that said that was what it was so we're going to blindly proceed with an induction attempt that might or might not work yep. This is probably some well-known property of the harmonic numbers that I just haven't seen before.

The actual formal logic of the induction is sort of trivial. The interesting part is just showing that the average of the first n harmonic numbers plus one is the next harmonic number. Laying things out visually (the logic works the same in the general case but this is how it would work for one small case of n=5):
0
1
1 + 1/2
1 + 1/2 + 1/3
1 + 1/2 + 1/3 + 1/4
When we take the average of these and add one, we need to end up with 1 + 1/2 + 1/3 + 1/4 + 1/5. The 1 will come from the 1 that we're adding, so we need the average of these five numbers to be 1/2 + 1/3 + 1/4 + 1/5. We group the numbers as follows: put one of the 1s on its own. Put one of the 1s with all of the 1/2s. Put one of the 1s with all of the 1/3s. And so on.

When we do this, we note that there are exactly n-k copies of 1/k for each k, for a total value of (n-k)/k = (n/k) - 1, so when we add a 1 to the sum of all of those we get (n/k). So by grouping the numbers this way, we get a bunch of sums that each sum to n/k, and when we take the average we add them all up and divide by n, which gives us exactly the sum that we need.

Forgive me for going from a specific example to general logic but i'm too lazy to actually go back formalize the argument completely. Pretty neat though.

(also it's 1:30 am and i've been nerd sniped so i take full liberty of having this proof be mostly train-of-thought)