Page 11234..1020..»

Viral Puzzle 11×11 = 4. The Correct Answer Explained

This puzzle has been shared with the claim that only geniuses can solve it.

11 × 11 = 4
22 × 22 = 16
33 × 33 = ?

It has gone viral on Facebook and the internet with millions of views as people have debated the correct answer.

Arguably there are many answers, as there are many patterns that fit the given information. However, there are 2 main answers that are most popular. I will go over what many people believe to be the correct answer, and I will explain how the 2 main approaches are flavors of the same idea.

Watch the video for an explanation.

Can You Solve The Viral 11×11 = 4 Puzzle? The Correct Answer Explained

Or keep reading.

.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
.
.
.
Answer To Viral Puzzle 11×11 = 4

Most people believe the correct answer is 36. The method to obtain the answer is to take the product of the sum of digits in each number being multiplied.

That is:

aa × aa → (a + a)(a + a)

This procedure matches the pattern of the puzzle:

11 × 11 → (1 + 1)(1 + 1) = 4
22 × 22 → (2 + 2)(2 + 2) = 16

And it suggests the answer of 36.

33 × 33 → (3 + 3)(3 + 3) = 36

This “product of the sum of digits” is what many people believe to be the correct answer. But there is debate.

Alternate answer: 18

Other people thought about the puzzle in terms of doing the multiplication and then taking the sum of the digits in the answer. In other words, this is finding the “sum of the digits in the product.”

11 × 11 = 121 → 1 + 2 + 1 = 4
22 × 22 = 484 → 4 + 8 + 4 = 16

This procedure suggests an answer of 18.

33 × 33 = 1089 → 1 + 0 + 8 + 9 = 18

The “sum of the digits of the product” gives 18, while the “product of the sum of the digits” gives 36.

It seems like these two methods are completely different. However, there is a way to see they are flavors of the same concept. And in this way, it is possible to get an answer of 36 when doing the “sum of the digits of the product.”

Getting 36 from the sum of the product

Let’s go deeper into the details of how to calculate the product of two numbers and how to sum the digits in the answer.

The number 11 can be written as 10 + 1, so we have:

11 × 11
= (10 + 1)(10 + 1)
= 1(100) + 2(10) + 1(1)
= 121

The digits in the answer are the coefficients of the sums of powers of 10, which is how decimal numbers are written. The sum of the digits in the answer is 1 + 2 + 1 = 4.

Similarly, the number 22 can be written as 20 + 2, so we have:

22 × 22
= (20 + 2)(20 + 2)
= 4(100) + 8(10) + 4(1)
= 484

Again, the sum of the digits is the sum of the coefficients of the terms attached to powers of 10. The sum is 4 + 8 + 4 = 16.

What happens with 33 then? The number 33 can be written as 30 + 3, so we have:

33 × 33
= (30 + 3)(30 + 3)
= 9(100) + 18(10) + 9(1)

What happens if you add up the terms attached to powers of 10? You get 9 + 18 + 9 = 36. You get the answer of 36 from this procedure!

But isn’t the answer supposed to be 18 from this method? Yes, the reason is 18(10) is larger than 100, so it involves carryover. We can simplify the answer as:

9(100) + 18(10) + 9(1)
= 9(100) + 10(10) + 8(10) + 9(1)

Now 10(10) = 100, so that contributes 1 more term to the 100 value.

9(100) + 10(10) + 8(10) + 9(1)
= 10(100) + 8(10) + 9(1)

Now 10(100) is equal to 1000, so we again have carryover.

10(100) + 8(10) + 9(1)
= 1(1000) + 0(100) + 8(10) + 9(1)
= 1089

This gives the familiar answer of 1089, which is what a calculator would show for 33 × 33.

But we can see that 9(100) + 18(10) + 9(1) is a valid representation of the product, and the sum would be 36 if we do not go through the carryover process.

So we have found a connection between the two methods.

aa × aa → (a + a)(a + a) = product of sum of digits = sum of the product (without carryover)

It is possible to justify the answer of 36 from either method.

Other ways to arrive at 36

In the video, I show the same thing visually using diagrams from the “multiply by lines” method. The answer in each case is the number of intersections of the lines or “dots” in the figure, and 33 × 33 has 36 dots.

33x33-multiply-by-lines

Via MindYourDecisions YouTube

The key to the answer of 36 is the multiplicative nature of the procedure. Start with 11 × 11 = 4 as a given. The second line has two terms that are 2 times 11, so the answer should be 2(2) = 4 times as large. The third line has two terms that are 3 times 4, so the answer should be 3(3) = 9 times as large.

11 × 11 = 4
22 × 22 = (2 × 11)(2 × 11) = 4(11 × 11) = 4(4) = 16
33 × 33 = (3 × 11)(3 × 11) = 9(11×11) = 9(4) = 36

There is another method to illustrate the multiplicative property and avoid carryover: express the answer in terms of a specific modulus, such as 39.

11 × 11 = 4 mod 39
22 × 22 = 16 mod 39
33 × 33 = 36 mod 39

All of these methods suggest that 36 is the correct answer to the puzzle.

Quora discussion
https://www.quora.com/Puzzles-and-Trick-Questions-What-is-the-correct-answer-to-11×11-4-22×22-16-33×33

Read more:
Viral Puzzle 11×11 = 4. The Correct Answer Explained

Can You Solve This 1869 MIT Admissions Geometry Question? Sunday Puzzle

The Massachusetts Institute of Technology (MIT) is one of the top ranked universities in the world. This question appeared on its admissions exam nearly 150 years ago.

“The perpendicular dropped from the vertex of the right angle upon the hypotenuse divides it into two segments of 9 and 16 feet respectively. Find the lengths of the perpendicular, and the two legs of the triangle.”

Can you figure it out?

Watch the video for a solution.

Can You Solve This 1869 MIT Admissions Geometry Question?

Or keep reading for a solution.

.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
P
U
Z
Z
L
E
.
.
.
.
Answer To 1869 MIT Admissions Geometry Question

Here is a diagram that illustrates the given information.

mit-geometry-problem-diagram-blog

There are many similar triangles in the figure. The triangle CDA is similar to ADB. This means the ratio of the shorter leg to longer leg of each triangle is constant, so we have:

CD/AD = AD/BD
9/p = p/16
9(16) = p2
144 = p2
p = 12 (exclude the negative root)

We now need to figure out the legs AC and AB.

mit-geometry-problem-perpendicular-blog

We could use the Pythagorean Theorem to solve for the remaining lengths, which are the hypotenuses of the smaller triangles. But we can solve for it even faster by noticing each triangle is similar to the 3-4-5 right triangle.

Notice the triangle ADC has two legs 9 and 12, which are triple the legs of 3 and 4 in a 3-4-5 right triangle. The hypotenuse must also be triple the length, so it is 15.

Similarly the triangle ADB has legs 12 and 16, which are four times the legs of 3 and 4 in a 3-4-5 right triangle. The hypotenuse must also be four times the length, so it is 20.

mit-geometry-problem-solved-blog

Source
Questions (see problem 6)
https://libraries.mit.edu/archives/exhibits/exam/geometry.html
Answers (see problem 6)
https://libraries.mit.edu/archives/exhibits/exam/geometry-answers.html

See the original post:
Can You Solve This 1869 MIT Admissions Geometry Question? Sunday Puzzle

Can You Solve Google’s Car Probability Interview Question? Sunday Puzzle

Here is a problem that Google asked as an interview question.

If the probability of seeing a car on the highway in 30 minutes is 0.95, what is the probability of seeing a car on the highway in 10 minutes? (assume a constant default probability)

Some clarifications that can help are:

“Seeing a car” means “seeing at least 1 car.”

“Constant default probability” means there is a constant probability rate of seeing a car (there’s no rush hour traffic, for example), so the probability of seeing a car during a time interval can be treated like a coin flip.

Watch the video for a solution.

Can You Solve Google’s Car Probability Interview Question?

Or keep reading for the solution.

.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
P
U
Z
Z
L
E
.
.
.
.
Answer To Google’s Car Probability Interview Question

Think about each 10 minute interval like a coin flip. Suppose the probability of not seeing a car in 10 minutes is p.

What is the probability of not seeing a car in 20 minutes? This is the probability of not seeing a car in 10 minutes, followed by the same event.

Pr(no cars in 20) = Pr(no cars in 10) Pr(no cars in 10)
Pr(no cars in 20) = p(p)
Pr(no cars in 20) = p2

The probability of not seeing a car in 30 minutes is the probability of not seeing a car in 20 minutes, followed by the event of not seeing a car in another 10 minutes.

Pr(no cars in 30) = Pr(no cars in 20) Pr(no cars in 10)
Pr(no cars in 30) = p2(p)
Pr(no cars in 30) = p3

We could have also directly calculated:

Pr(no cars in 30) = Pr(no cars in 10) Pr(no cars in 10) Pr(no cars in 10) = p(p)p = p3

Now the probability of seeing at least 1 car in 30 minutes can be calculated as the complement event, equal to 1 minus the probability of seeing no cars in 30 minutes.

Pr(car in 30) = 1 – Pr(no cars in 30)
Pr(car in 30) = 1 – p3

We are given this is equal to 0.95. We can solve for p:

1 – p3 = 0.95
p3 = 0.05
p = (0.05)1/3 ≈ 0.368

This is the probability of seeing no cars in 10 minutes. The probability of seeing at least 1 car is the complement event, equal to 1 minus the probability of seeing no cars in 10 minutes.

Pr(car in 10) = 1 – Pr(no cars in 10)
Pr(car in 10) = 1 – p
Pr(car in 10) ≈ 0.632

The probability of seeing at least 1 car on the highway in 10 minutes is approximately 63 percent.

Sources
http://www.impactinterview.com/2009/10/140-google-interview-questions/

http://www.businessinsider.com/answers-to-15-more-google-interview-questions-that-will-make-you-feel-stupid-2010-11#if-the-probability-of-observing-a-car-in-30-minutes-on-a-highway-is-095-what-is-the-probability-of-observing-a-car-in-10-minutes-assuming-constant-default-probability-2

Visit link:
Can You Solve Google’s Car Probability Interview Question? Sunday Puzzle

Chess Puzzles | Brilliant Math & Science Wiki

Practical exercises generally fall into one of two categories: tactics and analytics.

Tactics Puzzles In tactics puzzles, a position is presented with a forcing line of play available, making the goal to find that variation. Solving such puzzles improves one’s tactical vision, awareness, and pattern recognition.

When faced with such puzzles, the general strategy is to analyze the position as one would a real game, but the solver has an advantage in knowing that a tactical blow is present. It then becomes even more beneficial to organize one’s calculations in the following order:

It is rarely the case that the most accurate move in a tactical puzzle does not fall in one of the above categories.

Analytics Puzzles Analytics puzzles are much more involved, asking the solver to come up with a positional plan for the next few moves. Endgames, in particular, often involve little calculation and more long-term planning. These puzzles are not as commonly seen, however, because they demand a relatively high level of skill to reasonably approach, and because their somewhat subjective nature can make a proposed plan hard to judge, they are not automatable.

The next moves to consider are captures, revealing the solution: 1. Nxd5!

Black cannot recapture the knight with his pawn on c6, as the bishop on b5 would put him in check, and his queen is under attack. When his queen moves, White will also be able to capture the knight on e4, as it will no longer be defended by Black’s queen. If Black tries to avoid this by playing 1… Qe6?, White wins the game by playing 2. Nc7 (check), attacking both the king and the queen simultaneously.

In the position below, which is the strongest move for White?

1. Re7 1. Rxc8 1. Qxc7 1. Qf3

The rest is here:
Chess Puzzles | Brilliant Math & Science Wiki

The Hardest Easy Geometry Problem – Sunday Puzzle

hardest-easy-geometry-problem-langleys-adventitious-angles

The problem is known as Langley’s Adventitious Angles and was posed in 1922. It is also known as the hardest easy geometry problem because it can be solved by elementary methods but it is difficult and laborious.

Can you figure it out? Watch the video for a solution.

Can You Solve The Hardest Easy Geometry Problem?

Or keep reading for an explanation.

.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
P
U
Z
Z
L
E
.
.
.
.
Answer To The Hardest Easy Geometry Problem

There are two main principles to solving the problem. The first is that all the angles in a triangle sum to 180 degrees. The second is that in an isosceles triangle, there are two equal angles opposite two equal sides. Knowing a triangle has two equal angles means the sides opposite are equal, and knowing there are two equal sides means the angles opposite are equal.

hardest-easy-geometry-problem-langleys-adventitious-angles-principles-solving

The proof involves working through a series of isosceles triangles. To get started, draw line segment BG such that CBG is equal to 20 degrees.

hardest-easy-geometry-problem-langleys-adventitious-angles-solution-1

In triangle CBG, we know one angle is 20 degrees and other is 80 degrees, for a total of 100 degrees. So the triangle’s angles sum to 180, we can solve that  ∠CGB = 80 degrees. This means triangle CBG is an isosceles triangle, and BC = BG.

hardest-easy-geometry-problem-langleys-adventitious-angles-solution-2

Angles CBG and BGE form a straight line so they must add up to 180 degrees. This means angle BGE equals 100 degrees.

Then, focusing on triangle BGE, we can solve that ∠BEG = 40 degrees, because it has to be 180 minus the known angles of 40 and 100. Triangle BGE has two angles equal to 40 degrees, so this is another isosceles triangle, so BG = GE.

Then, focusing on triangle BFC, we can solve that ∠BFC = 50 degrees, which means triangle BFC is another isosceles triangle. This means BF = BC.

We have proven BC = BG = GE = BF.

hardest-easy-geometry-problem-langleys-adventitious-angles-solution-4

Now we create another triangle BFG. Since BG = BF, we know the opposite angles must be equal. The third angle in the triangle, ∠GBF, is 60 degrees, so the remaining angles have to be half of 180 – 60. This is (180 – 60)/2 = 60 degrees. In other words, all 3 angles are equal so BFG is an equilateral triangle. All of its sides must be equal, so GF = BF.

hardest-easy-geometry-problem-langleys-adventitious-angles-solution-5

We have figured out a lot of information. There is just one more triangle that is necessary to consider, so below is a diagram focusing on triangle GFE that omits the non-essential information.

We know GF = GE, so we once again have an isosceles triangle, and we know the vertex angle is equal to 40 degrees. This means the remaining angles are one-half of 180 – 40, which is 70 degrees.

hardest-easy-geometry-problem-langleys-adventitious-angles-solution-6

Finally, we know that 40 + has to be equal to 70, so that means x = 30 degrees.

hardest-easy-geometry-problem-langleys-adventitious-angles-solution-7

And that’s the answer! The value of x is 30 degrees.

Wikpedia Langley’s Adventitious Angles
https://en.wikipedia.org/wiki/Langley%E2%80%99s_Adventitious_Angles

Math With Bad Drawings Solution
A Technique is Just a Trick That Went Viral

World’s hardest easy geometry problem
http://thinkzone.wlonk.com/MathFun/Triangle.htm
https://www.duckware.com/tech/worldshardesteasygeometryproblem.html

Thanks to Patrons!

Kyle
Brian M. Mooney

You can support me and this site at Patreon.

Visit link:
The Hardest Easy Geometry Problem – Sunday Puzzle

How Many Liars Are At The Party? Sunday Puzzle

At a party there are 100 people who are either liars or truth tellers. Liars always lie and truth tellers always speak the truth, and each person can identify the type of others.

After the party is over, you ask each person, “How many truth tellers did you shake hands with?”

Each person gave a different whole number answer from 0 to 99 (the answers were 0, 1, 2, …, 98, 99).

How many liars were at the party?

Watch the video for a solution.

“Impossible” Logic Puzzle – How Many Liars Are At The Party?

Or keep reading.

.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
P
U
Z
Z
L
E
.
.
.
.
Answer To The Liars And Truth Tellers Party

The puzzle seems impossible because you do not know how many people each person shook hands with, and you do not know how many people are liars. But amazingly you can deduce the number of liars based on the answers everyone gave!

There are two keys to the puzzle. First, handshakes take place in pairs so if A shook B’s hand then both would have to count the handshake. Second, a truth teller always tells the truth, so if we can identify a logically false statement, then the person has to be a liar.

We will say person 99 is the person who said he shook hands with 99 truth tellers, person 98 is the person who said he shook hands with 98 truth tellers, and so on, so person 1 said he shook hands with 1 truth teller and person 0 said he shook hands with 0 truth tellers.

Start with person 99. If person 99 is a truth teller, then person 99 must have shaken hands with everyone else at the party, and everyone else must be a truth teller. This implies person 0, who said he shook hands with 0 truth tellers, would also have to a truth teller. So that 0 never shook hands with a truth teller, either 0 and 99 never shook hands (making 99 a liar), or 0 shook hands only with liars (also making 99 a liar). In either case, it’s impossible that 99 is a truth teller. Therefore person 99 is a liar.

We can use this information to figure out the next logical deduction.

Consider person 98. Since we know 99 is a liar, if person 98 is a truth teller, then 98 must have shaken hands with every person from 0 to 97, and persons 0 to 97 must be truth tellers. This implies 0 is a truth teller. So that 0 never shook hands with a truth teller, either 0 and 98 never shook hands (making 98 a liar), or 0 shook hands only with liars (also making 98 a liar). In either case, it’s impossible that 98 is a truth teller. Therefore person 98 is a liar.

We can proceed by to reason person 97 is a liar, then person 96 is a liar, and so on, all the way to proving person 1 is also a liar.

What about person 0? We have concluded everyone else at the party is a liar, so person 0 necessarily shook hands with only liars and 0 truth tellers. Either person 0 did not shake hands with anyone, or person 0 did shake hands with people who were liars. In either case, person 0 is telling the truth.

The party has 99 liars (persons 1, 2, …, 98, 99) and exactly 1 truth teller (person 0).

Source: problem slightly modified from Reddit Riddles
https://www.reddit.com/r/riddles/comments/4pt3o3/island_with_100_truth_sayers_and_liars/

Thanks to Patrons!

Kyle
Alberto Nishikawa
Brian M. Mooney

You can support me and this site at Patreon.

Link:
How Many Liars Are At The Party? Sunday Puzzle

The Viral 1 + 4 = 5 Puzzle. The Correct Answer Explained

This riddle was posted to Facebook with the claim that only one in a thousand will figure it out.

1 + 4 = 5
2 + 5 = 12
3 + 6 = 21
8 + 11 = ?

What do you think the answer is?

The problem went viral and generated over 3 million comments with people arguing about the correct answer. What do you think the correct answer is?

I explain what many believe to be the correct answer in the following video.

The Viral 1 + 4 = 5 Puzzle. The Correct Answer Explained

Keep reading for a text explanation.

.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
.
.
.
Answer To 1 + 4 = 5 Puzzle

A mathematician might take a literal approach.

1 + 4 = 5
2 + 5 = 12
3 + 6 = 21
8 + 11 = ?

The first equation is true, the second and third are false, and the answer to the equation should be 19.

But riddles like this are not about literally interpreting mathematical symbols. They are about identifying a pattern in the set of equations and applying it to the unknown.

The answer that jumped into my mind is to add the first number to the product of the two numbers to get the answer. That is:

a + b means a + ab

This works for the known equations.

1 + 4 means 1 + 1(4) = 5
2 + 5 means 2 + 2(5) = 12
3 + 6 means 3 + 3(6) = 21

Applying the pattern to the last equation gives the answer of 96.

8 + 11 means 8 + 8(11) = 96

The answer of 96 is valid according to this interpretation. Furthermore, many other IQ tests have this sort of pattern where you take two numbers and find a hidden equation that involves simple operations like addition, subtraction, multiplication, division, and exponentiation.

But some people interpreted the problem differently and arrived at a different answer.

Another interpretation: running total

Some people felt the pattern was a running total: add the result in the previous line to the new numbers to get the new answer.

The first line is valid mathematically.

1 + 4 = 5

For the next line, take this result of 5 and add it to the new numbers to get the new answer.

5 + 2 + 5 = 12

Do the same thing for the next line: add the previous line’s result of 12 to the new numbers to get the next result.

12 + 3 + 6 = 21

To solve the puzzle, do the same for the final line.

21 + 8 + 11 = 40

This pattern results in an answer of 40, and many people suggested this answer is more valid.

So what is the answer? Is it 40 or 96? While we cannot know for sure what the puzzle maker had in mind, there is a way to reconcile these two approaches. It turns out the running total can also lead to the answer of 96, if you decide to fill in the pattern a bit more.

Running total missing lines

Suppose the answer in each line is the running sum total of the previous result and the new numbers.

1 + 4 = 5
5 + 2 + 5 = 12
12 + 3 + 6 = 21

Notice that in each line the new numbers are incremented 1 more from the previous line. For example, 1 + 4 is turned into 2 + 5; so both the numbers 1 and 4 are increased by 1. Then 2 + 5 is increased to 3 + 6.

We can continue this pattern, so the next lines would be 4 + 7, then 5 + 8, then 6 + 9, then 7 + 10, and then 8 + 11.

What is the running total when we include these “missing” lines?

1 + 4 = 5
5 + 2 + 5 = 12
12 + 3 + 6 = 21
21 + 4 + 7 = 32
32 + 5 + 8 = 45
45 + 6 + 9 = 60
60 + 7 + 10 = 77
77 + 8 + 11 = 96

We once again get to the answer of 96, which is somewhat surprising!

In fact, the running total with the missing lines generates the same answer, line by line, as the algebraic result from the first approach:

a + b means a + ab = a(1 + b)

How can we see the two approaches are the same? On line 8, there are 7 previous lines. We can make 11 by pairing the first number of each line with the second number of another line: we can pair 1 with 10, 2 with 9, 3 with 8, 4 with 7, 5 with 6, 6 with 5, and 7 with 4. These are 7 pairs of 11. The final line has another 11. This means we need to take 8 and add 11 to it 8 more times, which is 8 + 8(11) = 96.

In general, line n has the equation n + (n + 3), which is equal to the result n + n(n + 3) = n(n + 4).

Let’s prove this formula holds by induction. Assuming the formula is true up to line n, we then consider the next line. In the next line n + 1, we add the numbers (n + 1) + (n + 4). The result in line n is n(n + 4), so when we add (n + 1) + (n + 4) we get:

n(n + 4) + (n + 1) + (n + 4)
= n2 + 6n + 5
= (n + 1)(n + 5)
= (n + 1)[(n + 1)) + 4]

And this completes the induction.

Most people believe the answer is either 96–with the equation a + ab–or 40–with a running total. Since the running total can also get to the answer of 96 when extending the pattern to missing lines, many believe that 96 is the answer that makes the most sense.

Facebook post source
https://www.facebook.com/randall.joneslatinjuggalo/posts/1048238075247858

Telegraph coverage
http://www.telegraph.co.uk/education/2016/04/22/this-maths-problem-has-thousands-of-people-baffled-can-you-work/

Reddit puzzles
https://www.reddit.com/r/puzzles/comments/4gbxst/how_to_come_up_with_the_most_correct_answer_on_a/

More here:
The Viral 1 + 4 = 5 Puzzle. The Correct Answer Explained

The Race To December 31 – Sunday Puzzle

Here’s a fun game you can play with another person.

The game starts on January 1. Each of two players takes turns calling out another date. The new date has to be a later date in the year with either the same month OR the same day (from January 1, a player can call out a later day in January or another month with the day 1 like February 1, March 1, etc.).

The person who calls out December 31 wins the game.

Who has the winning strategy, the first or second player? Does it matter if the game is played in a leap year?

This game was covered by Grey Matters in 2010, who communicated it to ScamSchool who made a video.

I have posted a video that explains the winning strategy.

Can You Solve The Race To December 31 Riddle?

Can you figure it out? Keep reading for my explanation.

.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
P
U
Z
Z
L
E
.
.
.
.
Answer To First To December 31 Wins

The winning strategy belongs to the first player, and it does not matter if it is a leap year.

The first player should call out January 20 on the first turn. The second player then names a later day in January or another month with the day 20.

Regardless, the first player can then name one of following dates (month/day), and continue to do so no matter what the second player does.

1/20 (first turn)
2/21
3/22
4/23
5/24
6/25
7/26
8/27
9/28
10/29
11/30
12/31

The pattern is:

day = month + 19

Played correctly, the first player always calls out December 31.

Solving the game

Understanding the strategy is easy enough. But how could one derive the strategy?

The game is an example of a well-known combinatorial game called Nim, in which two players remove objects from different piles of objects. Nim is a completely solved game for any number of objects and piles, so it is always possible to figure out a winning strategy for one of the players.

In specific games, we can use backwards induction, which means to think ahead and reason backwards. So let us start from the end of the calendar year.

Let’s start out by solving for winning dates. By rule, December 31 is a winning date.

12/31

If you name any other date in December, you would lose, as your opponent could then name 12/31. So all other dates in December are losing dates. You also want to avoid calling earlier months with the day value 31–as your opponent could then name 12/31.

What about November? The next date to analyze is 11/30. If you could call that out, there is no later date in November, so your opponent would have to name 12/30. This allows you to call 12/31 and win. So 11/30 is another winning date. If you can name it, you are sure to win.

11/30
12/31

Now we reason backwards. Similarly any earlier date in November is losing, as are the dates 10/31 and 10/30. So you want to name one day backwards, which is 10/29.

If you could name 10/29, your opponent would have to name 10/30, 10/31, 11/29, or 12/29. From 10/30 and 11/29 you can get to 11/30, and from 10/31 or 12/29 you can get to 12/31. In other words, if you can name 10/29, you can always get to a winning date.

10/29
11/30
12/31

Now we can extend the logic that the next winning date is 1 month backwards and 1 day backwards. So we get the winning date 9/28, then 8/27, and so on, until we get all of the winning dates.

1/20
2/21
3/22
4/23
5/24
6/25
7/26
8/27
9/28
10/29
11/30
12/31

The first player can name 1/20 on the first turn, and then keep naming a winning date for any choice that the second player is allowed to make.

The pattern in the dates is:

day = month + 19

Sources

Grey Matters
http://headinside.blogspot.com/2010/06/scam-school-meets-grey-matters.html

Scam School
https://www.youtube.com/watch?v=J3_XJtscvnQ

Go here to read the rest:
The Race To December 31 – Sunday Puzzle

The Friendship Theorem – Sunday Puzzle

In a group of 6 people, you might find that some people are friends with each other on Facebook, or you might find that no one is friends with each other on Facebook. There are many combinations for how people can be friends or not.

Show that there is always a group of 3 people in which either:

–All 3 people are mutual friends on Facebook.
–All 3 people are mutual strangers (no one is friends on Facebook).

Watch the video for a solution.

Can You Solve The Friendship Riddle?

Or keep reading.

.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
P
U
Z
Z
L
E
.
.
.
.
Answer To The Friendship Problem

Consider 1 person. That person is friends with 0, 1, 2, 3, 4, or 5 people, which pairs with not being friends with 5, 4, 3, 2, 1, or 0 people.

In every single case, either the person is friends with 3 or more people, or the person is not friends with 3 or more people.

Consider the first case of 3 or more friends and take 3 of those friends. If any of those are friends with each other, then that forms a group of 3 people who are mutual friends. If none of them are friends with each other, then that is a group of 3 people who are mutual strangers where no one is friends on Facebook.

The other case is similar. Suppose the person is not friends with 3 or more people and take 3 of those people. If any of those 3 people are not friends with each other, then that forms a group of 3 people who are mutual strangers. If all of them are friends with each other, then that is a group of 3 people who are mutual friends.

In every possible case, there is always a group of 3 people who are mutual friends or a group of 3 people who are mutual strangers.

The problem can also be visualized. Each person can be represented as a vertex of a graph. Draw a blue line between two vertices if the two people are friends, and a red line if the two people are not friends. No matter how the graph is colored, there will always be a monochromatic triangle–either a red triangle or a blue triangle. The video illustrates the proof using the colored graph.

Can You Solve The Friendship Riddle?

This problem is also known as the Friendship Theorem. It is an example of Ramsey Theory, a field that studies conditions under which certain properties must be true.

Further reading

Plus Magazine
https://plus.maths.org/content/friends-and-strangers

Wikpedia Theorem On Friends And Strangers
https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers

Math Garden blog
http://mathgardenblog.blogspot.com/2012/12/Ramsey33.html

View original post here:
The Friendship Theorem – Sunday Puzzle

Spies Sharing Secrets – Sunday Puzzle

On a successful mission, each spy obtains a unique secret. The n spies need to share all their secrets with each other, which they accomplish through a series of phone calls between 2 spies at a time. During a call, a spy can share all the secrets the spy knows, including secrets learned from previous calls.

What is the minimum number of phone calls needed so every spy learns all of the secrets? Solve the problem for the following two specifications of phone calls.

a) Each phone call is a 1-way call. Only the spy that makes the call can share secret information to the spy on the receiving end.

b) Each phone call is a 2-way call. Both spies can share their secret information with each other.

*Warning: it is very difficult to prove minimality for case b).

Watch the video for a solution.

Can You Solve The Spies Sharing Secrets Puzzle?

Or keep reading.

.
.
.
.
M
I
N
D
.
Y
O
U
R
.
D
E
C
I
S
I
O
N
S
.
P
U
Z
Z
L
E
.
.
.
.
Answer To Spies Sharing Knowledge

I will present the answer first and then justify why these are minimal procedures in the proof section later.

I will label the spies with letters in alphabetical order (A, B, C, etc.). I will write X→Y to indicate a 1-way call from X to Y, so spy X shares information to spy Y. I will write X↔Y to indicate a 2-way call between spies X and Y where both spies exchange information.

Here is an optimal procedure for 1-way calls. Call one of the spies the “the hub.” All of the other spies call the hub (n – 1 calls), and then the hub calls everyone back (n – 1 calls). If spy A is the hub, for example, the calling procedure with 3 spies would be B→A, C→A, A→B, A→C with the calls in that order.

spies-sharing-secrets-optimal-1-way-hub

For n spies, there are 2n – 2 calls made:

1-way calls
2 for 2 spies
4 for 3 spies
6 for 4 spies
2n – 2 for n ≥ 5 spies

The minimum number of 1-way calls is 2n – 2.

There can be other minimal methods too. Consider a “circular pattern” of calls. Imagine arranging the spies in a circle in alphabetical order. The spies first make a clockwise chain of calls starting and ending with A, which is n calls. At this point the last spy and spy A are fully informed. Now spy A starts a clockwise chain of calls which ends two calls before spy A; this is n – 2 calls.

spies-sharing-secrets-optimal-1-way-greedy

For example, with 4 spies the procedure would be A→B, B→C, C→D, D→A for the first clockwise chain (4 calls), and then A→B, B→C for the second clockwise chain (2 calls). This greedy algorithm has the advantage that the first call shares 1 secret, the second call shares 2 secrets, and so on until n secrets, so each call shares a maximum number of secrets. This method also requires n + (n – 2) = 2n – 2 calls.

With 2-way calls, you might expect that about half the number of calls are needed because both spies can share information during a call. Surprisingly this is not the case! With 2-way calls you can only save 2 calls, and the minimum number of calls is 2n – 4.

For 2 spies, only 1 call is needed: A↔B. For 3 spies, 3 calls are needed: A↔B, B↔C, C↔A. For 4 spies, 4 calls are needed: A↔B, C↔D, A↔C, B↔D. The pattern for 4 spies is particularly important. The graph shows the pattern and the number on each edge indicates the order of the call.

spies-sharing-secrets-proof-2-way-optimal-4

For 5 or more spies, the pattern can be generalized by adding 2 calls. The new spy calls A, B, C, or D at the beginning, and then the new spy gets a call from A, B, C, or D at the end. For example with spy A, the new spy calls A at the beginning, and the new spy calls A at the end. In this way the new spy shares information with A (which then gets shared with all other spies), and then A calls back at the end (so the new spies learns all the other secrets too). For 5 spies, for example, the calling pattern results in 6 calls: A↔E, A↔B, C↔D, A↔C, B↔D, A↔E.

The pattern continues like this, and we have the result:

2-way calls
1 for 2 spies
3 for 3 spies
4 for 4 spies
2n – 4 for n ≥ 5 spies

With 2-way calls, the efficient procedures for n > 4 have the following pattern. Designate 4 spies as hubs A, B, C, and D. Each of the other n – 4 spies calls one of the hubs. Then the 4 hubs share information in the “square” pattern for the case n = 4, which takes 4 calls. Finally, each of the n – 4 spies receives a call from exactly one hub spy. The total number of calls is (n – 4) + 4 + (n – 4) = 2n – 4, and this is the minimum number of calls. The key to the procedure is that 4 hub spies can share information efficiently in 4 calls. The general pattern looks like the following graph (here only spy B is being called by all other spies):

spies-sharing-secrets-optimal-2-way

This is the least number of calls needed with 2-way calls. Now compare the result with 1-way calls.

The surprising part is that sharing information is a fairly inefficient process! Although 2-way calls allow for twice the information exchange as 1-way calls, they only reduce the total number of calls by 2. The process of sharing secrets is not much better than everyone calling the hub, and then the hub calling everyone back.

The proofs that these formulas are minimal appear below.

Video with proofs

You can watch the proofs.

Spies Sharing Secrets Proof Minimum Number Calls

Or keep reading.

Proof for 1-way calls

For 1-way calls, each new spy adds on a minimum of 2 calls–one to share the secret and one to learn other secrets. From the base cases where 2n – 2 calls are necessary, it is intuitive that you need 2 more calls for each spy, hence the formula 2n – 2 makes sense.

Why is this minimal? The proof comes from Harary and Schwenk in 1974. Consider any n – 2 calls. It is impossible for any spy to be fully informed, as fully informing a single spy requires the transmission of n – 1 secrets in n – 1 calls. After n – 2 calls, it is possible that each subsequent call could fully inform 1 spy. To inform n spies means n additional calls. Therefore the minimum number of calls is (n – 2) + n = 2n – 2. The protocols of calling the hub and calling circularly do acheive this lower bound, and therefore they are minimal.

Proof for 2-way calls

For 2-way calls, it is not possible to get fewer than 2n – 4 calls when n ≥ 4. The formal proof involves many steps. The reason is that if you assume you could make fewer calls to inform everyone, that would force a specific condition on the calling procedure. The defining condition is that no spy can share his secret and then have that secret shared back to himself. This condition then leads to the conclusion, after a series of logical deductions, that each spy has to make at least 5 calls. This means the total number of 2-way calls is at least 5n/2 > 2n, which is more than 2n – 4 calls. To summarize: assuming fewer than 2n – 4 calls are possible leads to contradiction that more than 2n calls are needed. This proves that 2n – 4 is a lower bound on the calls needed. The procedure to call 4 hub spies above acheives this lower bound, so this is the theoretical minimal number of calls required.

This proof method is due to Brenda Baker and Robert Shostak “Gossips and Telephones” in Discrete Mathematics Volume 2 (1972), 191–193. There are other proofs of this problem; see the references at the end.

Assume that 2n – 4 is not the minimal number of calls for some n > 4. Let m be the smallest value, so that at most 2m – 5 calls are sufficient. The m spies call each other in some procedure.

Claim (NOHOI): The procedure obeys the principle that no one hears their own information (NOHOI) from another person. That is, no spy shares a secret and then has that secret told back to them by another person. If the calling procedure is drawn as an ordered graph (the spies are vertices and the edge number equals order of the call), then NOHOI means that there is no closed walk of edges in increasing order.

(Side note: the optimal method with 2n – 4 calls does not obey NOHOI–a spy calls the hub, and then the hub calls back, so that spy hears his own information.)

Proof (NOHOI): This is a proof by contradiction. If the procedure does not obey NOHOI, we will show we can share secrets with m – 1 spies in fewer than 2(m – 1) – 4 calls. This would be a contradiction because m is defined as the smallest value for which spies can share secrets in at most 2m – 5 calls.

Suppose there is a closed walk of edges in increasing order starting and ending with spy X. This is a sequence of calls X↔S1, S1↔S2, …, Sk↔X. If there are other people that call X, denote those calls by the grouped sets E0, E1, …, Ek+1, where Ei denotes all the calls made before Si↔X and Ek+1 is any calls made after X↔Sk.

Now let’s make a new procedure for m – 1 agents that shares all secrets in less than 2(m – 1) – 4 calls.

All calls that do not involve X remain the same (they are omitted in the diagrams below). Then we will eliminate all calls with X as follows. First, eliminate 2 calls X↔S1 and Sk↔X.

Next, keep all the remaining calls in the same order with the following adjustments. Replace E0↔X with the call E0↔S1, and also replace Ek+1↔X with the call Ek+1↔Sk. Also replace the remaining calls Ej↔X with the call Ej↔Sj.

This is a new calling procedure excluding spy X in which all the other spies share all their secrets. The adjustment process looks like the following:

spies-sharing-secrets-proof-2-way-nohoi1

spies-sharing-secrets-proof-2-way-nohoi2

The calling procedure with m spies had at most 2m – 5 calls. We eliminated 2 calls, so the reduced calling procedure with m – 1 spies has at most 2m – 7 = 2(m – 1) – 5 calls. If the original calling procedure informed all spies, then this adjusted calling procedure also informs all m – 1 spies excluding spy X.

But this means we have created a calling procedure with m – 1 spies that requires at most 2(m – 1) – 5 calls. This contradicts that m is the minimal value.

Therefore, we must have NOHOI in the minimal procedure.

Main proof of minimality: If NOHOI holds, then a call between two spies must be the last call for both, or for neither. Why? Suppose the call is A↔B. If it is the last call for spy A, then spy A is fully informed after the call. This means spy B will be be fully informed and knows all secrets. If spy B calls another spy (say C), then spy B will be sharing the secret of spy C to spy C. This contradicts NOHOI.

Similarly, a call between two spies must be the initial call for both, or for neither. Otherwise, imagine B↔C takes place and then A↔B, which is A’s initial call. Since spy A learns the secret of C, spy A’s information and spy C’s information will be paired together. Eventually spy C needs to learn spy A’s secret. But at that time spy C will learn the secret of C, which contradicts NOHOI.

The remaining calls are all intermediate calls between spies.

For the m > 4 spies, no initial call can be a final call. Each spy has to make an initial call and a final call, so there will be m calls that are either initial or final calls. This means there can be at most m – 5 intermediate calls to stay below the 2m – 5 limit of calls.

For a graph of m vertices, it takes a minimum of m – 1 edges for the graph to be connected. Since there can be at most m – 5 intermediate calls, the graph of intermediate calls has at most m – 5 edges, and so it must have at least 5 disjoint connected components.

Spy A is part of one component, spy A’s initial call might be with another component of intermediate calls, and spy A’s final call might be with a third component of intermediate calls at most. So at least 2 of the components are not involved, or are wasted, from spy A’s perspective of learning secrets. Write w(A) for the number of wasted calls for spy A.

It takes m – 1 calls for spy A to be informed, and it takes m – 1 calls for spy A’s secret to be shared with everyone. By NOHOI, the only calls that can do both involve spy A, which will be denoted as p(A).

The total calls for spy A to share the secret and learn others is at least 2m – 2 – p(A). Taking into account wasted calls, there are at least 2m – 2 – p(A) + w(A) total calls. The total number of calls must be less than or equal to the maximum number of calls, 2m – 5. So:

2m – 2 – p(A) + w(A) ≤ 2m – 5
p(A) ≥ 3 + w(A)

Because the number of wasted calls is non-negative, w(A) ≥ 0, this implies:

p(A) ≥ 3

This means spy A has to make at least 3 calls. Since spy A makes an initial call and a final call, spy A must also make at least one intermediate call. All of this logic is true for each spy, and so every spy makes an intermediate call.

There are at least 2 components in the graph of intermediate calls that are wasted from spy A’s perspective. Since each spy makes an intermediate call, each of the 2 components has to have at least 1 edge. This means w(A) ≥ 2.

Using this information with a previous inequality gives the following result:

p(A) ≥ 3 + w(A)
p(A) ≥ 5

This means each spy is involved in at least 5 calls. Since each call involves two spies, this means there are at least 5m/2 > 2m calls.

This results contradicts that the spies used at most 2m – 5 calls.

Therefore, 2n – 4 is the minimal number of calls for n spies to share their secrets.

Sources

This puzzle is known as the “gossiping problem” which is the primary name used in the references.

I first came across in Algorithmic Puzzles by Anany Levitin and Maria Levitin By Anany Levitin, Maria Levitin, “Rumor Spreading,” but the text does not include a proof.

The problem does appear with the above proof in in The Art of Mathematics: Coffee Time in Memphis by Béla Bollobás, “Gossiping Dons.”

MathWorld entry gossiping
http://mathworld.wolfram.com/Gossiping.html

One-way communications proof. Harary, F. and Schwenk, A. J. “The Communication Problem on Graphs and Digraphs.” J. Franklin Inst. 297, 491-495, 1974.
https://www.researchgate.net/publication/30825362_The_communication_problem_on_graphs_and_digraphs

Gossiping Dons (several proofs, including Brenda Baker and Robert Shostak “Gossips and Telephones” in Discrete Mathematics Volume 2 (1972), 191–193)
https://www.math.uni-bielefeld.de/~sillke/PUZZLES/gossips.pdf

Spreading Gossip Efficiently, C.A.J. Hurkens.
http://www.nieuwarchief.nl/serie5/pdf/naw5-2000-01-2-208.pdf

Gossiping problem proven
http://web.pdx.edu/~caughman/Gossip.pdf

Thanks to Patrons!

Kyle
Alberto Nishikawa
Brian M. Mooney

You can support me and this site at Patreon.

Visit link:
Spies Sharing Secrets – Sunday Puzzle


Page 11234..1020..»