







CTK Exchange
reidan
guest

Sep0408, 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 QUESTIONasking 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(x1) 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 
Printerfriendly page 
Reply 
Reply With Quote  Top 


alexb
Charter Member
2275 posts 
Sep0508, 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 QUESTIONasking 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(x1) questions I wonder. Every such question removes one candidate for the celebrity status leaving 1 fewer persons to check. Why does it take 3(x1) steps to get from x to 1? 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



Pierre Charland
Member since Dec2205

Sep0508, 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 6587
If 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 
Printerfriendly 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 © 19962018 Alexander Bogomolny

