the BIG riddle topic [part IX]

Lucid Lounge
41

It took me a few days to get it, and an hour or so to write it out, but here’s my solution:

Solution

1st WEIGH: Separate the balls into 3 groups with 4 balls each. Weigh two of the groups, group A against group B. Group C is not weighed.

  • Case 1: They weigh the same. In this case, you now know the eight balls from groups A and B are normal, and the odd ball is one of the 4 balls in group C.

    2nd WEIGH: Separate group C into 3 sub-groups: 2-1-1. Weigh the group of two balls (group a) against a third ball and one of the normal balls (group b). Make sure you remember which is the normal ball. The remaining ball from the group C would not be weighed.

    • Case 1.1: They weigh the same. All balls on the scale are normal. [Color=449721]The remaining ball from group C is the odd ball.[/color] No need to use the scale again, unless you want to find out if it’s heavier or lighter than the normal balls.

    • Case 1.2: They weigh differently. In this case, note which group was heavier. [Color=449721]The odd ball is either one of the three balls.[/color]

      3rd WEIGH: Weigh the two balls from group a against each other.

      • Case 1.2.1: They weigh the same. [Color=449721]The odd ball is the one from group b.[/color]

      • Case 1.2.2: They weigh differently. You now know the odd ball was from group a. [Color=449721]If group a was heavier, then the odd ball is the heavier one. Otherwise, the odd ball is the lighter one.[/color]

  • Case 2: They weigh differently. You now know that the 4 balls in group C are all normal. The odd ball is either in group A or B. You also know which group is heavier.

    2nd WEIGH: Split group A into two groups of two. Add a normal ball to the first group, and a ball from group B to the second group; thus weigh two balls from group A + one normal ball (group a) against the remaining two balls from group A + one ball from group B (group b). Three balls from group B will be left over.

    • Case 2.1: They weigh the same. The odd ball is one of the three remaining balls from group B. Since you know whether group B was heavier or lighter, you now know if the odd ball is heavier or lighter.

      3rd WEIGH: Weigh two of the three balls in the leftover group.

      • Case 2.1.1: They weigh the same. [Color=449721]The odd ball is the third ball.[/color]

      • Case 2.1.2: They weigh differently. [Color=449721]If group B was heavier, then the odd ball is the heavier one. Otherwise the odd ball is the lighter one.[/color]

    • Case 2.2: They weigh differently.

      • Case 2.2.1: Group A was heavier and group a is now lighter (or vice-versa). You now know that the odd ball was one of the two balls from group A which were in group b, and that the odd ball is heavier (or lighter).

        3rd WEIGH: Weigh those two balls against each other. [Color=449721]The heavier (or lighter) ball is the odd ball.[/color]

      • Case 2.2.2: Group A was heavier and group a is still heavier (or lighter). There are two possibilities, either one of the two balls in group A that were also in group a is the odd ball and is heavier than normal, or the ball from group B which was added to group b is the odd ball and it is lighter.

        3rd WEIGH: Weigh the two balls from group A that were also in group a against each other.

        • Case 2.2.2.1: They weigh the same. [Color=449721]The odd ball is the ball from group B which was added to group b.[/color]

        • Case 2.2.2.2: They weigh differently. [Color=449721]The heavier (or lighter) ball is the odd ball.[/color]

42

Haha. I had to search my own posts with ‘balls’ as a keyword to find my old post again. Wow. That was from five years ago. Time sure does fly. I did a quick check in that part to see if my riddle was solved. That doesn’t seem to be the case.

I had forgotten the solution to the riddle myself so I decided to work it out again. Happy to say I managed to solve it so I can compare my solution with yours. Reading up on it, all I can say is… Your solution is complicated :rolleyes: At least, it is definitely different from mine. I’ll post my solution later and you can check that too.

After spending a longer than anticipated time understanding your solution with a pen and paper, I can confidently say that you are correct :content: Thanks for solving a 5 year old post.

:hugs:

43

Here’s my solution to my riddle.

[spoiler][code]Group the balls into three groups of four. We’ll call these groups A, B, C.
Additonal notes: A[1] would stand for the first ball in group A. A[1,2] would stand for balls 1 and 2 of group A. ‘=’ would stand for an equal reading while ‘!=’ stands for not equal.

1st Weigh: A and B
IF =
We know that the odd ball is in C

2nd Weigh: C[1] and C[2] 
IF =
	We know that the odd ball is in C[3,4]

	3rd Weigh: C[1] and C[3]
	IF =
		We know that C[4] is the odd ball
	IF !=
		We know that C[3] is the odd ball

IF !=
	We know that the odd ball is in C[1,2]

	3rd Weigh: C[1] and C[3]
	IF =
		We know that C[2] is the odd ball
	IF !=
		We know that C[1] is the odd ball

IF !=
We know that the odd ball is in A or B
For simplicity’s sake, assume that the lighter group is A

2nd Weigh: A[1]+B[1,2] and A[2]+B[3,4]
IF =
	We know that the odd ball is in A[3,4]
	We know that the odd ball is lighter than the others
	(Remember that A was the lighter group)
	
	3rd Weigh: A[3] and A[4]
		We know that the lighter ball is the odd ball

IF !=
	Take note of which group is lighter and which group is heavier
	We know that the odd ball is either one of the B balls in the heavier side or the A ball in the lighter side
	(Remember that the A group was lighter group in the 1st Weigh)

	IF A[1]+B[1,2] is lighter
		We know that the odd ball is in B[3,4] or is A[1]

		3rd Weigh: B[3] and B[4]
		IF =
			We know that A[1] is the odd ball
		IF !=
			We know that the heavier ball is the odd ball
			(Remember that A[2]+B[3,4] weighed heavier in the 2nd Weigh)
	
	IF A[2]+B[3,4] is lighter
		We know that the odd ball is in B[1,2] or is A[2]

		3rd Weigh: B[1] and B[2]
		IF =
			We know that A[2] is the odd ball
		IF !=
			We know that the heavier ball is the odd ball
			(Remember that A[1]+B[1,2] weighed heavier in the 2nd Weigh)

[/code][/spoiler]

44

^^ very nice solution Alvin!
Very elegant :content:

45

There are 25 race horses that each run at different speeds. You can only race 5 horses at a time, but you have no stopwatch or any way to time them. However, you know that all the horses always run at constant speeds. (i.e. The fastest horse will always be the fastest in every race.)

What is the minimum number of races you need to determine the fastest 3 horses?

Sample way of determining the fastest 3 horses (but not necessarily the optimal way):

Sample

Race 1: race 5 horses
Race 2: race the fastest three horses from Race 1 with 2 new horses
Race 3: race the fastest three horses from Race 2 with 2 new horses
Continue until all 25 horses have been raced. The fastest 3 in the last race are the fastest 3 of all.

Total races needed: 11 <-- correct answer is less than or equal to 11

46

I’m tentatively thinking 7.
Divide horses into 5 groups.

  1. Race the 5 sets of horses.
  2. Race winners together.
  3. Race the best 3 of winners race with runners up in fastest of the first 2 races.

:peek: I think I need to rethink this. Oh 8 races should be enough. :confused:

Please pm me Alot before I go crazy…

47

I think 9 races.

The races are conducted in 3 rounds. The first round, the horses are divided up into 5 groups of 5 horses. Each group runs a race, making 5 races in this round.

The second round has 3 races. All of the first-place horses from each of the first-round races run against each other, all of the second-place horses run against each other, and all of the third-place horses run against each other. The fourth- and fifth-place horses are eliminated.

The horse that comes in first out of all the first-place horse is the fastest overall, and need not run in another race.

Out of the horses that came in first place in the first round, the ones that came in second and third in the next round go on to the final round. The fourth- and fith-place horses are again eliminated.

Out of the horses that came in second in the first round, the ones that came in first and second in the next round go on to the finals. The third place is eliminated because that horse had been beaten by 3 other horses already: one in the first round and 2 other horses in the second. Fourth- and fifth-place are eliminated, as before.

Finally, out of the horses that came third in the first round, only the horse that came first in the second round goes on to the finals. The other horses were already outrun by 2 horses in the first round, and 1 or 2 horses in the second round. Fourth- and fifth-place are eliminated, as before.

Thus, the horses that run in the final race are the second and third place out of the first-placers, the first and second out of the second-placers, and the first out of the third-placers. The winner and runner-up from this round are the second and third ranked overall, joining the winner of the first-placers’ race in the top 3.

So, there are 5 races in the first round, 3 race in the second, and one final race, making 9 in total.

48

Considering this further: No, I was wrong, and moogle’s solution was closer than mine. It is 7 races.

As before, in the first round, each group of horses runs a race, making 5 races in the second round.

Then, in the next round, there is just one race, with the first-place winner from each group from the first round. As before, the first-place winner from this race is first-place overall, and need not run another race.

In the final round, both the second-place and third-place winners from the first-round group that the overall first place ran in need to run, because all of the top 3 might have ended up in that group.

The second place horse from the second round, and the runner up to that horse from the second round also need to compete in the final round. The lower places don’t need to run, because the third-place horse is slower than the second-place horse from the first round, which is slower than the first-place horse from that round, which is slower than the first-place horse from the second round. Thus, we know there are 3 horses that are faster than those horses.

Likewise, the the third-place horse from the second round is, at best, third-place overall, so none of the runner-ups which that horse beat in the second round need to compete in the final round.

Therefore, in the final round, the 5 horses are the second- and third-place horses from the second round, the second- and third-place horses that the overall first-place horse outran, and the runner-up from the first-round to the horse that came in second-place in the second round. The top 2 horses from the final round are second- and third-place overall.

So, there are 5 races in the first round, one in the second round, and one in the final round, for 7 races in all.

49

^this is the same answer I got, and I’m pretty sure it can’t be done in 6… (is there a mathematical way to prove this?)
@moogle, you were close, just need to rethink #3 a tiny bit :wink:

50

Yes, dawned on me later. Fastest horse is found in race 6. So only 2nd and 3rd need to be found.

So race 7 needs
horse 2nd and 3rd from ‘fastest horse’ first race.
horse 1st and 2nd from ‘second fastest horse’ first race.
3rd horse in all winner race.

51

horse race part 2 ðŸŽðŸŽðŸŽ

the manager of Timeless Horse Races Inc. thanks you all for helping with her horse racing problem. however she has one concern. after she knows which three horses are fastest she plans to have a big showcase race between them and she doesnt want anyone to know which horse will win beforehand.

can you give her a way to race the 25 horses to find the fastest 3 but without finding out which is the fastest of them all?

she also would like you to help her bookie set the odds for the showcase race.

52

From initial analysis, I would say it’s not guaranteed to be possible to find the three fastest without knowing which is fastest, since you might get lucky (or unlucky) and race the three fastest in one of the initial races. However, the odds of that would be 231/53130 or approx 0.43% if I managed to get my probabilities right… (22C2 over 25C5?)

Anyway, there’s still a higher probability that it will be possible, so here’s how I would propose to proceed:

Rough solution

Round 1: Same as before, group the horses into 5 groups of 5, and have the preliminary races, numbered 1 to 5. Immediately, the 4th and 5th place finishers of each race are eliminated. 15 horses are left.

For easier reference, let us call each horse as (n,r) where n is the race number that the horse was grouped into in Round 1 and r is the rank of the horse in that race. n is from 1 to 5, and r is from 1 to 3.

For example, horse (4,1) was in race 4 of the preliminaries, and came in first place.

Round 2: Group the remaining horses into 3 match-ups of 5 such that no five horses in the same group had previously raced against each other in the preliminaries. To even things up, I would split them in this pattern:

Race 1: (1,1) vs (2,2) vs (3,3) vs (4,2) vs (5,1)
Race 2: (1,2) vs (2,3) vs (3,1) vs (4,1) vs (5,3)
Race 3: (1,3) vs (2,1) vs (3,2) vs (4,3) vs (5,2)

From the results of the 2nd round, I think a maximum of two more rounds would be needed depending on the results. Odds can be determined accordingly based on whether the three finalists had raced against each other in the previous two rounds, and perhaps based on the performance of the other horses as well, however that might get more complicated.

Results of Round 2:
Note: Any horse that comes third is automatically out of the running.

Proof: Since each race has a maximum of two first placers from the previous round, at least one of the top three finishers in any given race has at least one horse faster that raced in another match. Therefore at least three horses are faster than the third place finisher of any given race.

With only 6 horses left in the running, at least two have raced against each other in the previous round, therefore we would be able to determine the three fastest with at most one final round. However, to lessen the possibility of knowing which of the horses is the fastest, we should minimize the number of horses that race against each other in Round 3, and thus a fourth round may also be needed.

I made a spreadsheet to illustrate my solution, though it’s not fully done yet, and only based on scenarios. Basically I numbered the horses from 1 to 25 with 1 being the fastest, and randomly grouped them for Round 1. Orange colored cells are the horse numbers. White colored cells refer to their respective rank from Round 1 races. Press F9 or edit any cell to generate another scenario.

Example scenario 1

908×1053

Round 2 results (top 2 of each match-up):
Race 1: (5,1) and (1,1) - (horses 2 and 4)
Race 2: (5,3) and (1,2) - (horses 5 and 6)
Race 3: (2,1) and (5,2) - (horses 1 and 3)

Solution:
(1,2) is out, because (1,1), (5,1), (5,3) and (5,2) are all faster.
(5,3) is out because (5,2), (5,1) and (2,1) are all faster.

Round 3: (1,1) vs (5,2) --> whoever wins is in the top 3 with (2,1) and (5,1). Either (5,1) or (2,1) is the fastest, but the winner won’t be known until after the finals :trophy:

Example scenario 2

903×1051

Round 2 results (top 2 of each match-up):
Race 1: (5,1) and (1,1) - (horses 1 and 2)
Race 2: (4,1) and (3,1) - (horses 3 and 4)
Race 3: (2,1) and (3,2) - (horses 5 and 7)

Solution:
(3,2) is out, because (3,1), (4,1) and (2,1) are all faster.

Round 3: (1,1) vs (3,1) vs (2,1)
Results: (1,1) beats (3,1) beats (2,1) --> (4,1), (1,1) and (5,1) are in the top 3. Either (5,1) or (4,1) is the fastest, but the winner won’t be known until after the finals :trophy:

Example scenario 3

918×1054

Round 2 results (top 2 of each match-up):
Race 1: (5,1) and (1,1) - (horses 1 and 6)
Race 2: (4,1) and (3,1) - (horses 3 and 5)
Race 3: (5,2) and (2,1) - (horses 2 and 4)

Solution:
All horses are still in the running.

Round 3: (1,1) vs (3,1) vs (5,2)
Results: (5,2) beats (3,1) beats (1,1) --> (1,1) is out, because (3,1), (5,2) and (5,1) are faster.
(3,1) is out because (4,1), (5,2) and (5,1) are all faster.
(5,2) and (5,1) are in the top 3. We will need a Round 4 to determine if (4,1) or (2,1) is our last contender.

Alternate Round 3 (1,1) vs (3,1) vs (2,1)
Results: (2,1) beats (3,1) beats (1,1) --> (1,1) and (3,1) are out, because (2,1), (5,2) and (5,1) are faster.
Same result, (5,2) and (5,1) are in the top 3. We will need a Round 4 to determine if (4,1) or (2,1) is our last contender.

Round 4: (4,1) vs (2,1)
If (4,1) wins, then we have our top 3, and either (4,1) or (5,1) is the fastest but the winner won’t be known until after the finals :trophy:
However, if (2,1) wins, then we already know that (5,1) is the fastest, followed by (5,2) then (2,1) :sad:

EDIT v2 of spreadsheet here (with odds)

So, finally managed to work out the program until Round 3 (Edited the terminology a bit so that Round 4 is now called Round 3 race 2), and realized my original computation of Top 3 meeting in the first round was off. It should be .43%*5, or roughly 2.2%, still small enough.

However, it seems that the probability of successfully determining the top 3 without knowing which is the fastest is only about 75% using the method above, and only about 10-11% that it will be an evenly anyone’s-game 3-way race. This still could be improved, as I think there’s still a bug with the rules on how to determine the Round 3 match ups, and it doesn’t always give the best solution (for example, by wasting a race by choosing 2 horses whose rankings against each other are already known).

Anyway, I’ve identified five cases based on known Win-Loss data after Round 3. Two of the cases end up as failures (Fastest horse is already known at the end of Round 3). Corresponding theoretical and simulated probabilities are shown below.

Illustration of simulation and probabilities

757×726

Edit: Added Sim2 to address the bug of wasting Round 3 match ups. Even three-way race odds has increased to about 14% in the simulation.

957×685