Puzzles with numbers and things

[snookersfun]

I just got there as well, sorry!!! It is only 4 calls for n=4. Have to think a bit more about the rest (especially uneven numbers)
doing that while trying to feed kids, the washing mashine, giving biology lessons +++
you are not the only one busy
So you earned another point! Congrats

[davis_greatest]

Don't think it matters whether n is odd or even, as long as it's >=4.

I'm trying to see how to show that you can't do it in fewer than 2n-4 calls (it's easy to see that not more than 2n-4 are needed), but can't seem to see an easy way to show this at all...

[snookersfun]

well, if you can't, I won't even try.... The proofs are always the hard parts, aren't they.
Just blew my head trying to find the combinations for 5 and 6 (and yes, strangely enough I could).
Somehow it is strange, that one shouldn't need even less phone calls with even higher numbers like 8,16,...

[davis_greatest]

Well, yes, the proofs are the hard part, but I don't think one can understand a problem without understanding the proof.

If you've shown that for 4 people you can do it in 4 calls (which is easy), then you can see that each time you add one more person, 2 extra calls will suffice.

Suppose that with n=N (>=4), it can be done in 2N-4 calls.

Then when n=N+1,

get the (N+1)st person to speak to the 1st person : 1 call
get the N people to spread the scores among themselves: 2N-4 calls
get the (N+1)st person to speak to the 1st person again: 1 call

Total 2N-2 = 2(N+1) - 4 calls.

So, by induction, we know that the lower bound is no greater than 2n-4 (for n>=4). Now prove it is no less!

[elvaago]

How do you do 4 matches in 4 calls?

[snookersfun]

I can do that:
1-2
3-4
2-3
1-4

[davis_greatest]

I can do that:
1-2
3-4
2-3
1-4

....
Yes!

[snookersfun]

So, no proof yet?

Meanwhile, I found another little puzzle:

given two integers m and n (both bigger than 1 and m Charlie: I couldn't tell the numbers yet.
Gordon: I knew that.
Charlie: Now I can.
Gordon: So can I.

(and as usual, we need the proof, that no other pairings are possible )

[davis_greatest]

snookersfun, can this be done without a computer (or writing a lot of numbers out by hand)?

And robert602, no, I haven't managed to prove that 2n-4 is the minimum possible in your question (for n>=4). Do you have a proof or counterexample?

[snookersfun]

I started to work on my own problem and you definitely need some computer-help. Excel will do, I think.
Also, having read up on Robert's stuff, there (quite amazingly- as one only saves that one call) is no counter example (but there are indirect proofs in that direction (not that I understand them); do you want some references?)

[davis_greatest]

Yes, please send them. I think robert has had to give his homework in by now, so he won't be cheating

[Robert602]

Yeah my efforts were handed in last week. I had a class on it today in which 2n-4 (n>4) was confirmed as the correct answer, but the good doctor gave us another couple of days to think about a proof (for curiosity's sake) before it's revealed to us. He did say the proof was 'the difficult bit'.

1 point to DGE for getting the right result, and I'll offer a bonus point for a proof should anyone manage to come up with one.

[abextra]

Meanwhile, I found another little puzzle:

given two integers m and n (both bigger than 1 and m Charlie: I couldn't tell the numbers yet.
Gordon: I knew that.
Charlie: Now I can.
Gordon: So can I.

(and as usual, we need the proof, that no other pairings are possible )

Maybe m=2 , n=6 ?

[Robert602]

I'll chip in with 9 and 2, although thinking about it I can't see a problem with 8 and 3 either...

Don't think it's 6 and 2 because if it was, Gordon couldn't know that Charlie wouldnt know (as for all Gordon knows, Charlie has the product 15 and therefore would know). If you get me .

[davis_greatest]

I make it 4 and 13. I don't know how to show a proof though, other than by sending the few columns of Excel that calculated it for me. My spreadsheet shows that that's the only possibility, but I think there are too many pairs of numbers to write something out that is short and elegant by hand to show that nothing else works?