|
|
|
|
|
|
|
|
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
|
|
Printer-friendly copy
Email this topic to a friend