CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "difficult mathematics induction proofing"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #693
Reading Topic #693
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)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail Pierre%20Charland Click to send private message to Pierre%20Charland Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK