|
|
|
|
|
|
|
|
CTK Exchange
reidan
guest
|
Sep-04-08, 06:57 AM (EST) |
|
"difficult mathematics induction proofing"
|
hai, i just knew this web yesterday, while searching some clue to finish my discrete mathematics homework,, and i really need help..please.. cause it have 2 b done by saturday.. theres 2 question and each of it was equipped with a hint,,here we go -------------------------------------------------------------------- 1. Show that it is possible to arrange the numbers 1,2,3,...,n in a row so that the average of any two of these numbers never appears between them.. --------------------------------------------------------------------- 2. a guest at a party is a celebrity if this person known by every other guest,and knows none of them. there is at most 1 celebrity at party,for if there were 2,they would know each other.a particular party may have NO celebrity.. the assignment is : find the celebrity,if one exist,by asking ONE TYPE QUESTION-asking a guest whether they know the second guest(it could be any1 at the party) use mathematical induction to show that if there are x people at the party,then we can find the celebrity with 3(x-1) questions --------------------------------------------------------------------- if the hint make it more complicated please just ignore it.. cause i just need the answer,and it isn't have to be the same way as the hint..
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
alexb
Charter Member
2275 posts |
Sep-05-08, 09:09 AM (EST) |
|
1. "RE: difficult mathematics induction proofing"
In response to message #0
|
>and i really need help..please.. >cause it have 2 b done by saturday.. It's a pity you mentioned this. I would have answered earlier. Now had to wait a little. >1. Show that it is possible to arrange the numbers >1,2,3,...,n in a row so that the average of any two of these >numbers never appears between them.. For n = 4, 2143 does the job. Similarly, 6587 works for 5678. You should probably think of a recursive procedure that shuffles such two together. >2. a guest at a party is a celebrity if this person known by >every other guest,and knows none of them. >there is at most 1 celebrity at party,for if there were >2,they would know each other.a particular party may have NO >celebrity.. >the assignment is : > find the celebrity,if one exist,by >asking ONE TYPE QUESTION-asking a guest whether they know >the second guest(it could be any1 at the party) >use mathematical induction to show that if there are x >people at the party,then we can find the celebrity with >3(x-1) questions I wonder. Every such question removes one candidate for the celebrity status leaving 1 fewer persons to check. Why does it take 3(x-1) steps to get from x to 1? |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
Pierre Charland
Member since Dec-22-05
|
Sep-05-08, 09:18 PM (EST) |
|
2. "RE: difficult mathematics induction proofing"
In response to message #1
|
1. Show it is possible to arrange 1,2,3,...,n in a row so that the average of any two of these numbers never appears between them. Your n=4 example shows the way. 2143 6587If n=2^0 or 2^1, it is trivially true. If true for n=2^m, with sequence a(1), a(2), .., a(2^m+1). Then true for n=2^(m+1), with sequence 2a(1)-1, 2a(2)-1, .., 2a(2^m+1)-1, 2a(1), 2a(2), .., 2a(2^m+1). If true for n=4, with sequence 1, 3, 2, 4. Then true for n=8, with sequence 1, 5, 3, 7, 2, 6, 4, 8. so 1,2 to 1,3,2,4 to 1,5,3,7,2,6,4,8 to 1,9,5,13,3,11,7,15,2,10,6,14,4,12,8,16 to ... is one sequence possible (not the only one).
AlphaChapMtl
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Copyright © 1996-2018 Alexander Bogomolny
|
|