Challenge Riddles and Puzzles: Extend the following to a valid equation

[mfb]

I need more than a second to verify that this is indeed a Fibonacci sequence - to check that every number is the sum of the previous two.

Not a solution for 56:

Spoiler

I wrote an Insights article about it. Well, not exactly this problem, but I'll leave it to others.

 

[fresh_42]

Less than a second ? Hats off !

(what's the icon for incredulity?)

For the multiplication, not the rule.

 

[jbriggs444]

56. Marcy, Henry and Esther have decided to do something for their fitness and are therefore organizing a small jogging race each morning. In the past month of June, Marcy ran in front of Henry more often than he did before her, and Henry ran more often in front of Esther than she did before him.

Could it be that Esther ran in front of Marcy more often than Marcy did in front of Esther?

The problem statement was a bit jarring. One would ordinarily expect the winner of a race where the runners start even to have been in front of each competitor exactly one more time than he or she was behind.

But a situation where a runner barely draws even and then falls behind without passing is possible and would allow the number of times ahead or behind to increment beyond one.

Spoiler

Marcy could play the "let him catch up but then pull away" game with Henry, racking up arbitrarily many "is ahead" events relative to Henry while Esther was either well ahead or well behind.

Henry could play the "let her catch up but then pull away" game with Esther, racking up arbitrarily many "is ahead" events relative to Esther while Marcy was either well ahead or well behind.

Esther could play the "let her catch up but then pull away" game with Marcy, racking up arbitrarily many "is ahead" events relative to Marcy while Henry was either well ahead or well behind

It is possible that "more often" is intended to be interpreted as "for a duration of more than half the race". Rock, paper, scissors works for that interpretation as well.

 

[fresh_42]

It is possible that "more often" is intended to be interpreted as "for a duration of more than half the race". Rock, paper, scissors works for that interpretation as well.

The poor wording is probably due to Google translate. I didn't change all of it. "run before / after" means "crosses the finish line ahead of / after". Sorry.

Correction 56.:

So the final results count:

#MH > #HM and #HE > #EH

At the finish line:
Marcy was ahead of Henry more often than he was ahead of her, and Henry was ahead of Esther more often than she was ahead of him.

Could it be that Esther was ahead of Marcy more often than Marcy was ahead of Esther?

 

[jbriggs444]

So the final results count:

#MH > #HM and #HE > #EH

Ok, so the race is run repeatedly and the daily results are tallied. My mistake for not realizing that.

Spoiler

Say there are 30 races. Rename Henry, Marcia and Esther to A, B and C to preserve sanity.
In 10 of them, A > B > C
In 10 of them B > C > A
In 10 of them C > A > B

A beats B 20 to 10
B beats C 20 to 10
C beats A 20 to 10

 

[fresh_42]

57. Two shepherds rest in a meadow. One has 5 pieces of cheese and the other 3 pieces. A hiker comes over and asks if he can eat the cheese with them. The two agree. At this common meal, all three people eat the same amount of cheese. After the meal when all cheese was eaten, the hiker gets up and gives $8 as compensation for the cheese.

How should this amount be divided among the herdsmen so that their contribution of 5 or 3 pieces of cheese is taken into account fairly?

D76

 

[BvU]

Spoiler

Each eats $2{2\over 3}$ pieces of cheese, so fiver contributes $2{1\over 3}$ and threepee ${1\over 3}$.
Ratio is $7:1$: fiver gets 7 bucks , the other guy only one.

 

[fresh_42]

58. How many matches are minimally needed to construct four equilateral triangles.

D76

 

[BvU]

Spoiler

I need 9

 

[jbriggs444]

Spoiler

Can do it with six.

 

[fresh_42]

Spoiler

Can do it with six.

View attachment 245851

Ok, ugly but possible.

Can someone do it without crossings?

 

[BvU]

#259 ? or are we allowed to chop them up ?

 

[fresh_42]

#259 ? or are we allowed to chop them up ?

Nope.

 

[jbriggs444]

#259 ? or are we allowed to chop them up ?

Oh, *doh*. Obvious.

Spoiler

Tetrahedron

 

[fresh_42]

59. The village of Brownlee has exactly 100 inhabitants. The oldest was born in 1900 and all inhabitants were born a different year, but all on January 1st. In 1999, the sum of the four digits of John's year of birth is equal to his age.

How old is John?

D77

 

[lpetrich]

#59:

Spoiler

Since the oldest was born in 1900, and since John's age was measured in 1999, we have
$$ 1900 \le \text{(John's birth year)} \le 1999 $$
That means that John birth year has digits 1, 9, t, and u, where t and u are between 0 and 9 inclusive. That gives it value $1900 + 10t + u$. His age in 1999 is thus 1999 - (birth year) = $99 - 10t - u$. The sum of the digits is $10 + t + u$, Their equality is thus
$$ 99 - 10t - u = 10 + t + u \\ 89 = 11t + 2u $$
Trying the possible values of u, {0 ,1,2 ,3, 4, 5, 6, 7, 8, 9}, gives possible values of 11t {89, 87, 85, 83, 81, 79, 77, 75, 73, 71}. The only integer solution for t is 7, for u = 6.

Thus, John's birth year is 1976, making him 23 years old in 1999.

The sum of his age's digits is 1+9+7+6 = 10+13 = 23.

 

[fresh_42]

60. The King on a chessboard is in the lower left corner (A1). He can move from field to field, but due to a lost bet he can only move according to the following rules:

• a field to the right (B1)
• a field upwards (A2)
• a field diagonally to the top right (B2)

How many different ways are there into the upper right corner (H8)?

D77

 

[BvU]

Direct answer: No moves possible: there are no G8, H9 or G9

But you want to know how any different ways there are to reach H8 from A1, right ?

And the rules are to be taken as OR rules (not in sequence: right, then up, then diagonal, right etc) ? Must be quite a heap of possible routes ...

 

[fresh_42]

Direct answer: No moves possible: there are no G8, H9 or G9

But you want to know how any different ways there are to reach H8 from A1, right ?

And the rules are to be taken as OR rules (not in sequence: right, then up, then diagonal, right etc) ? Must be quite a heap of possible routes ...

Less than 100,000. I am personally rather bad at combinatorics, I always count wrong. This question has chances to remain unanswered, or to figure out whom I can call if a question about combinatorics occurs in the set theory forum. The solution I have distinguishes between diagonal moves and others, i.e. counting without diagonals on an $n \times n$ board, then $k$ diagonals, and then partitioning ways into these two possibilities.

 

[jbriggs444]

Less than 100,000. I am personally rather bad at combinatorics, I always count wrong. This question has chances to remain unanswered, or to figure out whom I can call if a question about combinatorics occurs in the set theory forum. The solution I have distinguishes between diagonal moves and others, i.e. counting without diagonals on an $n \times n$ board, then $k$ diagonals, and then partitioning ways into these two possibilities.

Spoiler

Sensible. So one can catalogue the ways of doing it with 0, 1, 2, 3, 4, 5, 6 and 7 diagonal moves:
$$\frac{14!}{7! 7! 0!} + \frac{13!}{6! 6! 1!} + \frac{12!}{5! 5! 2!} + \frac{11!}{4! 4! 3!} + \frac{10!}{3! 3! 4!} + \frac{9!}{2! 2! 5!} + \frac{8!}{1! 1! 6!} + \frac{7!}{0! 0! 7!}$$
$$= 3432 + 12012 + 16632 + 11550 + 4200 + 756 + 56 + 1$$
$$=48639$$

Or one could brute force it with a kind of Pascal's triangle variant. w(x+1,y+1)=w(x,y) + w(x+1,y) + w(x,y+1)

     1     1     1     1     1     1     1     1
     1     3     5     7     9    11    13    15
     1     5    13    25    41    61    85   113
     1     7    25    63   129   231   377   575
     1     9    41   129   321   681  1289  2241
     1    11    61   231   681  1683  3653  7183
     1    13    85   377  1289  3653  8989 19825
     1    15   113   575  2241  7183 19825 48639

 

[lpetrich]

#60

Spoiler

The king moves from position (0,0) to (n,n) where n is 7 for a standard chessboard, and moves with combinations of horizontal, (1,0), vertical, (0,1), and diagonal, (1,1) moves.

For k diagonal moves, the number of horizontal moves needed is (n-k), and the number of vertical moves needed is likewise (n-k). This gives a total of (2n-k) moves.

The total number of permutations with all distinct is (2n-k)!. However, all the horizontal moves look alike, meaning that one must divided by the factorial of their number, (n-k)!. Likewise for vertical moves, (n-k)!, and diagonal moves, k!. Thus giving
$$ N(n,k) = \frac{(2n-k)!}{k! (n-k)! (n-k)!} $$
The total number of permutations is added up over k = 0 to n, giving
$$ N(n) = \sum_{k=0}^n N(n,k) $$
Doing this calculation for n = 7 gives 48639.

I looked for patterns for N(n) as a function of n, without much success. By numerical calculation, I found an asymptotic limit of C₀*Cⁿ, for C near 5.8.

 

[fresh_42]

Spoiler

Sensible. So one can catalogue the ways of doing it with 0, 1, 2, 3, 4, 5, 6 and 7 diagonal moves:
$$\frac{14!}{7! 7! 0!} + \frac{13!}{6! 6! 1!} + \frac{12!}{5! 5! 2!} + \frac{11!}{4! 4! 3!} + \frac{10!}{3! 3! 4!} + \frac{9!}{2! 2! 5!} + \frac{8!}{1! 1! 6!} + \frac{7!}{0! 0! 7!}$$
$$= 3432 + 12012 + 16632 + 11550 + 4200 + 756 + 56 + 1$$
$$=48639$$

Or one could brute force it with a kind of Pascal's triangle variant

     1     1     1     1     1     1     1     1
     1     3     5     7     9    11    13    15
     1     5    13    25    41    61    85   113
     1     7    25    63   129   231   377   575
     1     9    41   129   321   681  1289  2241
     1    11    61   231   681  1683  3653  7183
     1    13    85   377  1289  3653  8989 19825
     1    15   113   575  2241  7183 19825 48639

#60

Spoiler

The king moves from position (0,0) to (n,n) where n is 7 for a standard chessboard, and moves with combinations of horizontal, (1,0), vertical, (0,1), and diagonal, (1,1) moves.

For k diagonal moves, the number of horizontal moves needed is (n-k), and the number of vertical moves needed is likewise (n-k). This gives a total of (2n-k) moves.

The total number of permutations with all distinct is (2n-k)!. However, all the horizontal moves look alike, meaning that one must divided by the factorial of their number, (n-k)!. Likewise for vertical moves, (n-k)!, and diagonal moves, k!. Thus giving
$$ N(n,k) = \frac{(2n-k)!}{k! (n-k)! (n-k)!} $$
The total number of permutations is added up over k = 0 to n, giving
$$ N(n) = \sum_{k=0}^n N(n,k) $$
Doing this calculation for n = 7 gives 48639.

I looked for patterns for N(n) as a function of n, without much success. By numerical calculation, I found an asymptotic limit of C₀*Cⁿ, for C near 5.8.

Not sure whether I should congratulate you. You just won the position of:

"If there's something to count,
and it don't look good:
Who you going to call?"

 

[fresh_42]

61. What is the formula of the number of (connected) squares on a $n\times n$ chess board.

D77

 

[lpetrich]

For #61, what counts as connected?

 

[fresh_42]

Path connected. Not a square in each corner which combined is again a square. That was just an insurance.

 

[BvU]

Spoiler

8x8 of area 1 square, 7x7 of area 2² etc. $$\sum_{n=1}^8 n^2 = 204 $$not as many as I would have guessed

 

[fresh_42]

61.

For the record: It was asked for the formula for the number of squares on a $n\times n$ chess board, so the answer is
$$
\sum_{k=1}^n k^2 = \dfrac{n(n+1)(2n+1)}{6}
$$

 

[fresh_42]

62.

43 Lothers befether the Jolice.
41 Lothers sprungle the Leesand.
49 Lothers delorkle the Gmelt.

17 Lothers befether the Jolice and sprungle the Leesand.
27 Lothers befether the Jolice and delorkle the Gmelt.
21 Lothers sprungle the Leesand and delorkle the Gmelt.

6 Lothers do all three.
8 Lothers do nothing at all.

How many Lothers are there?

D78

 

[jbriggs444]

62.

43 Lothers befether the Jolice.
41 Lothers sprungle the Leesand.
49 Lothers delorkle the Gmelt.

17 Lothers befether the Jolice and sprungle the Leesand.
27 Lothers befether the Jolice and delorkle the Gmelt.
21 Lothers sprungle the Leesand and delorkle the Gmelt.

6 Lothers do all three.
8 Lothers do nothing at all.

How many Lothers are there?

D78

Spoiler

Likely there is a clever inclusion/exclusion formula that applies. But just as easy do it exhaustively.

6 do all three.

Given this, then of the 21 that both sprungle and delorkle, 15 do only those two things.
Given this, then of the 27 that both befether and delorkle, 21 do only those two things.
Given this, then of the 17 that both befether and sprungle, 11 do only those two things.

Given the above, then of the 49 that delorkle, 7 only delorkle while 15+21+6 also do something else.
Given the above, then of the 41 that sprungle, 9 only springle while 11+15+6 also do something else.
Given the above, then of the 43 that befether, 5 only befethers while 21+11+6 also do something else.

8 do nothing.

The exhaustive catalogue of Lothers then includes 8 who do nothing, 5+9+7 = 21 who do exactly one thing, 15 + 21 + 11 = 47 who do exactly two things and 6 who do three things.

For a total of 8 + 21 + 47 + 6 = 82 Lothers.

 

[BvU]

For the record: It was asked for the formula for the number of squares on a $n\times n$ chess board

Aint'no *&&^% chess boards other than with 8x8 squares !

 

[mfb]

Likely there is a clever inclusion/exclusion formula that applies.

People who do nothing + sum of the people for one activity - sum of the people for two activities + people for three activities
8+(49+41+43)-(21+27+17)+6 = 82

Aint'no *&&^% chess boards other than with 8x8 squares !

Are you sure?

 

[fresh_42]

Are you sure?

How disappointing: this one was missing at the link

 

[fresh_42]

63. On how many ways can parentheses be set in a product of $n$ numbers, such that always at most two numbers are multiplied?

D78

 

[jbriggs444]

D78

Infinitely many unless n=0.
x, (x), ((x)), (((x)))...

[Waits for the wet noodle]

 

[fresh_42]

Infinitely many unless n=0.
x, (x), ((x)), (((x)))...

[Waits for the wet noodle]

... oh, those mathematicians ... you almost never can use words ... I start to understand what Bourbaki has driven.

Corrected.

 

[jbriggs444]

... oh, those mathematicians ... you almost never can use words ... I start to understand what Bourbaki has driven.

So, rephrasing, you want to know how many (finite) binary trees there are with n leaf nodes with the understanding that each node in the tree is either a leaf node with zero children or an root/intermediate node with exactly two sub-trees, each of which is required to have at least one leaf node.

Let t(n) be the number of such trees with n leaf nodes.

t(0) = 1 -- the empty tree (which can never be a sub-tree hanging off of an intermediate node)
t(1) = 1 -- the tree with one leaf.
t(n) = $\sum_{i=1}^{n-1} t(i) t(n-i)$ -- adding up for the possible left hand and right hand sub-trees.

Unfortunately, that's as far as I can drive toward a solution

And the above is incomplete -- it applies to an ordered list of numbers parenthesized in place. For an arbitrary set of n unique numbers, one would need to multiply by n factorial.

Spoiler

Google says Catalan numbers

 

[fresh_42]

So, rephrasing, you want to know how many (finite) binary trees there are with n leaf nodes with the understanding that each node in the tree is either a leaf node with zero children or an root/intermediate node with exactly two sub-trees, each of which is required to have at least one leaf node.

Let t(n) be the number of such trees with n leaf nodes.

t(0) = 1 -- the empty tree (which can never be a sub-tree hanging off of an intermediate node)
t(1) = 1 -- the tree with one leaf.
t(n) = $\sum_{i=1}^{n-1} t(i) t(n-i)$ -- adding up for the possible left hand and right hand sub-trees.

Unfortunately, that's as far as I can drive toward a solution

And the above is incomplete -- it applies to an ordered list of numbers parenthesized in place. For an arbitrary set of n unique numbers, one would need to multiply by n factorial.

If the numbers are not unique then the problem is not well-posed since the answer depends on the number and multiplicity of the duplicates.

Well, Leonhard said it is $\displaystyle{ \prod_{k=1}^{n-1}\dfrac{4k-2}{k+1}}$

but Catalan defined it as $\displaystyle{t_n=C_{n-1}=\dfrac{1}{n}\binom{2(n-1)}{(n-1)}}$ or better $\displaystyle{t(n+1)=C_n=\binom{2n}{n}-\binom{2n}{n+1}}$

 

[fresh_42]

64. "Yahtzee" is a game of 5 dice, in which certain combinations must be achieved. For this you have 3 rolls free and can choose with at each roll, which dice you leave and with which you want to continue to roll.

A "long street" is one of the following two combinations:
1 2 3 4 5 or 2 3 4 5 6
I only had to roll this combination in a game and got in the first roll:
2 3 3 4 6
That's a hopeful start. But how to continue playing? Take one of the two threes and try to throw the missing 5 with the two remaining throws? The chance to win I call G1.

I had the vague feeling that it could be smart to put the 6 in the dice cup and then fill in the remaining formation 2 3 4 with two dice. After all, the combinations 1 + 5 and 5 + 6 can provide a "long street". The chance here is called G2.

Since it must go fast in the game, I opted for the second variant and had bad luck. Afterwards I wanted to know more about it and started to calculate.

Was I smart or not?

D78

 

[jbriggs444]

D78

[bungled]

Spoiler

Smart.

Original strategy:

With only the single die in the cup there are two consecutive chances to roll a winning 5. Probability of success is 11 in 36.

Chosen alternate strategy:

With two dice in the cup the result of the first roll can be an outright win with a 1+5 (4 of 36) or a 5+6 (4 of 36). [The possibilities are non-intersecting, so the probabilities add]. That's a success rate of 8 in 36 immediately.

The result of the second roll (if needed) can be a success at a rate of 8 in 36. Of course, the second roll attempt is conditional on a first roll failure. So it only adds $\frac{28}{36}$ of 8 in 36. Still, that's better than the 3 in 36 you needed to make it a smart play.

We did not even need to examine the possibility of rolling a 1, 5 or a 6 on the first roll.

 

[fresh_42]

What is it that you calculated for G2? Smart means G2 > G1 = $\frac{11}{36}$.

 

[jbriggs444]

What is it that you calculated for G2? Smart means G2 > G1 = $\frac{11}{36}$.

Question does not ask for G2. It only asks whether G2 > G1. I answered yes. Edit: And bungled it. *sigh*.

 

[fresh_42]

Other opinions out there?

 

[fresh_42]

65. Two people play the following game:

On the blackboard is the number $2.$
Who is to move, replaces the number $n$ on the blackboard by a number $n + d$, where $d$ is an arbitrary divisor of $n$ with $1 \leq d <n.$
The one who first has to write a number greater than $1991$ on the blackboard will have lost.

Who wins the game assuming an optimal strategy, the first player or his opponent?

D80

 

[mfb]

Going back to the dice:
- There is a 2/36 chance to roll 1,5 and a 2/36 chance to roll 5,6, for a 4/36 chance to win with the second roll.
- If we don't win then there is a 7/36 chance of 5,x where x is not 1 or 6. We keep the 5 and reroll the last die, for a 1/3 chance to win (with either 1 or 6) -> 7/36*1/3 chance to win
- If we do not get a 5 there is a 9/36 chance to get a 1 and a 7/36 chance to get a 6 but no 1, combined 16/36. In both cases we reroll one die for a 1/6 chance with the third roll.
- If we don't get 1, 5 or 6, which means just 2,3,4 (9/36 chance) then we reroll both and have a 4/36 chance with the second roll.
All cases are mutually exclusive. Sum: 4/36 + 7/36*1/3+16/36*1/6+9/36*4/36 = 5/18 = 10/36
Rerolling 3 and 6 is a little bit worse than rerolling 3 alone.

 

[mfb]

Who wins the game assuming an optimal strategy, the first player or his opponent?

This is a nice puzzle. You excluded n from being added, therefore the first player must add 1. 3 is a prime again, the second players adds 1 and we get 4. This first player now can add 1 or 2, reaching 5 or 6. If the first player goes to 5 then the second player must go to 6.

If 6 is a winning position, the first player will play 4->5 and win.
If 6 is a losing position, the first player will play 4->6 and win.

We don't even have to consider larger numbers. The first player has a winning strategy, although I have no idea how that strategy looks like.

 

[fresh_42]

We don't even have to consider larger numbers. The first player has a winning strategy, although I have no idea how that strategy looks like.

The winner is the one who finds a number $n$ with $1991-n \,|\, n$, because then he can write directly $1991$ and the opponent must choose a larger number.

For odd $n$, $1991-n$ is even, so $n$ can not divide it. The first player can now ensure that his opponent always gets to deal with odd numbers less than $1991$. (His opponent always leaves him an even number less than $1991$, since the divisors of his odd number are all odd and the sum is even, so he can always choose at least $1\,.)$

 

[fresh_42]

66. To move very heavy loads you sometimes use rolls under the load. Such a roll has a circumference of $50\, \text{cm}$. How far has the load been moved when the rolls have turned once?

D80

 

[BvU]

Spoiler

$200\pi$ cm

 

[fresh_42]

Nope.

 

[BvU]

Ah, 100, of course, darn, I should read better (50 is not the radius)