6
$\begingroup$

You are a Book lender who strangely lends books of equal length and difficulty ever time. You have people who you lend your books to, but you want to find out who is the fastest reader of the group and who is the slowest reader of the group.

This is the situation.

There are ten people who all read books at different speeds and they will always read the books you give them in the same amount of time that they read all the other books.

-

When you lend a book because of the way your book lending system is set up, the book is shared between three people. Meaning when the first person receives the book they will read it in the time it takes them, then give it to the next person to read, then they will give the third and last person the book to read and they will return it to you.

-

You as the book keeper get to choose which three people get the book at anytime. The only information you are given is the amount of time it took all three of your selected people too read the book(the sum of all three of their reading times)

-

All of the people are perfect actors so they will never change the amount of time that it takes them to read a book and there will be no transition time between giving the book to each other.

-

You have an infinite amount of books to lend so you can take as many steps as you would like in which you select three of ten each time and see the sum of those three's reading time.


Remember you are trying to find the fastest and the slowest reader by lending these books.

So how would you do it?

$\endgroup$
  • $\begingroup$ The speed of solution would depend on the precise times for each levels of reading. $\endgroup$ – Brandon_J Jan 25 at 4:00
  • $\begingroup$ Ah, you have to understand the prompt is for the "fastest" and "slowest" meaning the exact speeds are not important as these two would be relative. and the solution is not who but how. @Brandon_J $\endgroup$ – robert gibson Jan 25 at 4:04
5
$\begingroup$

Okay, I'll start with a correct but not great answer:

The problem is, we have ten positive numbers A,B,C,D,E,F,G,H,I,J and we are allowed to ask for the sums of any groups of three of them.
* With 4 steps: A+B+C, A+B+D, A+C+D, B+C+D
* Then we know A,B,C,D: because ((A+B+C)+(A+B+D)+(A+C+D)-2(B+C+D))/3 = A, and so on.
* With 6 more steps: A+B+E, A+B+F, A+B+G, A+B+H, A+B+I, A+B+J.
* Then (A+B+E)-(A+B+D) = E-D, and we know D, so we know E, and the rest.
* So, in 10 steps, we can tell how long each person in the group takes to read a book.
* Conversely, to find out how long each person in the group takes to read a book, it looks like we would need at least 10 steps, since there are 10 numbers to find out.

So this is correct, and "optimal" in its own way, but not the way we want because

we don't actually need to know how long each person in the group takes to read a book, we just need to know who is fastest and who is slowest in the group.

But I have a funny feeling that,

you might need ten steps anyway, so I will "win" ;-)

but I don't know.


(EDIT TO ADD:) Here's an example to substantiate that feeling:

Let's say our 9 steps are A+B+C, B+C+D, C+D+E, D+E+F, E+F+G, F+G+H, G+H+I, H+I+J, and I+J+A. Now suppose A=B=D=E=G=H=J=-1 and C=F=I=2. Then all 9 sums will come out zero.
(-1 -1 2 -1 -1 2 -1 -1 2 -1) is an "eigenvector with eigenvalue zero". What I mean by that is, even though it has negative numbers, we can add it to a sufficient large set of ten numbers to get a second set of ten numbers which is 'indistinguishable' from the first, as far as those 9 steps are concerned. Like so:
( 2 3 4 5 6 7 8 9 10 11)
(-1 -1 +2 -1 -1 +2 -1 -1 +2 -1)
-----------------------------
( 1 2 6 4 5 9 7 8 12 10)
And indeed, for (2 3 4 5 6 7 8 9 10 11) and (1 2 6 4 5 9 7 8 12 10), the nine sums are the same in both cases: (9 12 15 18 21 24 27 30 23). But in one case the largest is J=11, and in the other, I=12. So this can't work.

Now here's some voodoo:

Imagine we make a 10x10 matrix of ones and zeros. The first 9 rows each have 3 ones and 7 zeros. The last row has 10 zeros. This represents taking 9 (or fewer) steps. But this matrix has determinant zero. No matter what, it must have a zero eigenvector. Like above, we can use that eigenvector to construct a pair of examples which are indistinguishable to those 9 steps, but where the largest and/or smallest number is in a different place.

So it looks like

nine steps or fewer doesn't work, I "win"! ;-)

$\endgroup$
  • $\begingroup$ I really do like your answer. Let us see if someone can beat it. $\endgroup$ – robert gibson Jan 25 at 21:59
  • $\begingroup$ @robertgibson I added some voodoo to it. $\endgroup$ – deep thought Jan 26 at 2:58
  • $\begingroup$ @deepthought why a 10x10 matrix? Don’t we end up with a 10x9, so each variable can be represented as a vector with components dependent on the other variables and a constant component? I get that every method has to have a zero eigenvector, but it is always possible that the method’s zero eigenvector changes the values of the variables but not the highest and lowest, isn’t it? $\endgroup$ – Krad Cigol Jan 26 at 3:21
  • $\begingroup$ @KradCigol Right, but any multiple of the eigenvector is also an eigenvector .. the scales have to tip at some point! (yeah, this is a lot of handwaving, it needs more explaining before being called a proof.. but I think it works.) $\endgroup$ – deep thought Jan 26 at 3:28
  • $\begingroup$ Seems like it... but could you test my edited method? I think it might work now. (Btw: take my upvote! You deserve it!) $\endgroup$ – Krad Cigol Jan 26 at 3:31
3
$\begingroup$

Proof that ten steps are the minimum necessary:

Ten steps are the minimum required. Credit:@deep thought.
Let us assume there is a method with 9 steps, that solves this puzzle.
Then the 9 equations can be represented as a 10x9 matrix, where each row has 3 ones and 7 zeroes.
When it is converted to reduced row echelon form, there will be only nine pivot variables. This means that only nine of their values can be nailed down, whereas the tenth value will not be found. This can lead to interesting contradictions, including identical totals when adding a zero eigenvector to the numbers.
This leads to a contradiction, completing our proof.

Old answer:

Edit: never mind, I’m wrong. Ten steps is the minimum.

I think the answer is

9.
Though we need 10 to establish absolute reading speeds, we need only 9 to establish the ratio between them.

Method:

We start off by passing a ‘window’ over the reading speeds, but we take a in each group. So let us list our groups:
a, b, c.
a, c, d.
a, d, e.
a, e, f.
a, f, g.
a, g, h.
a, h, i.
a, i, j.
a, j, b.
Next, we see that a is common in all, so if their values were t1 through t9, we can change them into b + c = t1 + a, and so on.
Now, we add them all up, but we take the first positive, second negative, and so on, stopping at a,i,j.
We find that we get an absolute value for b-j. Adding this to the a-dependent value of b+j, we find a value for b dependent on a, and can derive one for j as well.
In similar fashion, we find the values for b through j relative to a.
What about a? Well, since we found b and c relative to a, we can substitute into a+b+c to get a value for a.
Since we only need to find who is fastest and slowest, not individual speeds, this hound be sufficient.

$\endgroup$
  • $\begingroup$ Well you need Proof for this to be a valid answer. $\endgroup$ – robert gibson Jan 26 at 1:34
  • $\begingroup$ Very well. I’ll add a method. $\endgroup$ – Krad Cigol Jan 26 at 1:35
  • $\begingroup$ I’m having a bit of trouble. Can I use matrices? @robertgibson $\endgroup$ – Krad Cigol Jan 26 at 2:02
  • $\begingroup$ Don't think this works. (2 3 4 5 6 7 8 9 10 11) and (1 2 6 4 5 9 7 8 12 10) will give the same 9 sums (9 12 15 18 21 24 27 30 23)... so it doesn't matter what you do with those sums $\endgroup$ – deep thought Jan 26 at 2:15
  • $\begingroup$ @deepthought I know. I’m thinking of a different method at the moment. And I think I got it! $\endgroup$ – Krad Cigol Jan 26 at 2:22
0
$\begingroup$

Answer:

10. Probably optimal due to solving 10 unknowns takes 10 equations.

My approach:

ABC, ABD, ACD, BCD, EFG, EFH, EGH, FGH, ABI, ABJ.

$\endgroup$
0
$\begingroup$

I think the number of lends required is

8

For example, let's call customers "a b c...j", and call the time each "lend" takes a "result"

By passing a moving window over the list of customers, you perform 8 lends, yielding 8 results
[a b c] d e...
a [b c d] e...
a b [c d e]..

You can then calculate an average of each customer's results, (sum of results divided by number of lends)
av(a) = a+b+c
av(b) = a+2b+2c+d / 2
av(c) = a+2b+3c+2d+e / 3

While A's result includes equal parts B and C, it's outweighed by the 3C in C's result and the 2B in B's result. Their results each include more of their own value, relative to other customer's averages.

Which is fine - we never needed a correct value, just a sort order, so we can find the fastest and slowest ^_^

Apologies for the awkward explanation! Hope you can follow it :)

$\endgroup$
  • 2
    $\begingroup$ I don't think this works. Take for example the reading times 1,2,3,4,5,6,7,8,10,9. Your method gives the last reader as the slowest reader with score 27, and not the one before that, which gets score 26. $\endgroup$ – Reinier Jan 25 at 13:51
0
$\begingroup$

Naive Answer

Lets label the time it takes our readers to read a book as $r_0$ through $r_9$. We will place them in a circle clockwise and lend 10 times, once for each reader with the two readers to their left (i.e. going clockwise). The time it takes to get the book back will the $R_i$.

So, we will get 10 equations of the form $R_i = r_i + r_{i+1 \text{ mod } 10} + r_{i+2 \text{ mod } 10}$. For example, $R_4 = r_4 + r_5 + r_6$.

Now, we can solve for any $r_i$ since we have 10 equations and 10 unknowns which is easily solvable.

$\endgroup$
  • $\begingroup$ Probably want to spoiler that. $\endgroup$ – robert gibson Jan 25 at 20:48
  • $\begingroup$ This procedure works here because it happens to produce independent equations, but it woudn't if there were for example 9 people. $\endgroup$ – Jaap Scherphuis Jan 26 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.