Forum
  Classifieds
  News
  Localband
  Shows
  Show Pics
  Polls

  OT Threads
  Other News
  Movies
  VideoGames
  Videos
  TV
  Sports
  Gear
  /r/
  Food

  New Thread
  New Poll

E-mail

New site? Maybe some day.

Username:

SPAM Filter: re-type this

(values are 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E, or F)

Message:

UBB enabled. HTML disabled Spam Filtering enabledIcons: (click image to insert) Show All - pop

b i u add: url image video(?)

:	post by ShadowSD at 2006-06-22 11:40:42

I'm going to take a crack at this... number 1:

Let's say k=2, that means 3 numbers must be chosen from the set (1,2,3,4).

Before we choose them, the following values of y would have x as a multiple:

if y=1 then x=2 OR x=3 OR x=4.
if y=2 then x=4.

So no matter if the three numbers we choose are 1,2,3 or 1,2,4 or 1,3,4 or 2,3,4, you can always find at least one pair in those three numbers where one can be x and one can be y according to the equations in the above two sentences.

Let's say k=3, that means 4 numbers must be chosen from the set (1,2,3,4,5,6):

if y=1 then x=2 OR x=3 OR x=4 OR x=5 OR x=6.
if y=2 then x=4 OR x=6.
if y=3 then x=6.

So no matter if the four numbers picked are 1,2,3,4 or 1,2,3,5 or 1,2,3,6, or 1,2,4,5 or 1,2,4,6 or 1,2,5,6 or 1,3,4,5 or 1,3,4,6 or 1,4,5,6, or 2,3,4,5 or 2,3,4,6 or 2,3,5,6 or 3,4,5,6 you can always find at least one pair in those four numbers where one can be x and one can be y according to the equations in the above three sentences.

As we can see, going over the lower numbers like 1 and 2 each time that we increase k is a bit redundant, since those scenarios have already been proven. Clearly, the only questionable area to be solved are the new numbers that appear at the top of the list everytime k is increased by one.

With that in mind: If you take k+1 numbers out of a list of consecutive integers from 1 to 2k, and try to take the highest numbers possible, you end up taking the top half of the list as well as the next lowest integer, which HAS to be k. Since k is always going to be half of 2k, there is always a scenario where x is a multiple of the y.

In otherwords, the sets we were looking at earlier could also be looked at as (1,k,3,2k), (1,2,k,4,5,2k), etc. No matter what k is, the fact that the list ends with 2k guarantees that one will always be a multiple of the other.

I don't know if I'm wording this as a "proof" by the standards her math professor may set, but this is the logic behind solving the problem. Hope it helps...

[default homepage]

[print][

11:32:40am Apr 28,2024
load time 0.01948 secs/10 queries]

[search]

[refresh page]