quote:

Originally posted by DigiNut I'm not sure if this was clarified earlier, but does the genie rotate it completely arbitrarily, or one position at a time?

Completely arbitrarily. (Equivalently, he is omniscient, and completely maliciously). As for the set problem, I cannot believe what I did. It was originally listed as [1, 100], and then I edited it to be [1, 1000]. I've fixed it. :-P

quote:

Originally posted by Flyboy217 Completely arbitrarily. (Equivalently, he is omniscient, and completely maliciously). As for the set problem, I cannot believe what I did. It was originally listed as [1, 100], and then I edited it to be [1, 1000]. I've fixed it. :-P

Ahh okay. So for part (b) I think the answer should be 113 (highest elements sum to 1085, 1085 - 55 = 1030, which is greater than 1024).

I still can't get the genie one, gah.

___________________
My party schedule:
2009-02-21 - DJ Attention @ I'm So Popular
2009-06-18 - DJ Annoying @ People Need To Know Where I'll Be
2012-11-32 - DJ Insufferable ɸ Or At Least the Stalkers I Complain About
2048-06-66 - Spastic & Whocares ¶ Although I'm Actually Flattered
9999-45-81 - Tweaker Gimp ☼ I Probably Won't Even Go To This But I Have To Make Sure I Fill Up All The Available Space Here

quote:

Originally posted by DigiNut Ahh okay. So for part (b) I think the answer should be 113 (highest elements sum to 1085, 1085 - 55 = 1030, which is greater than 1024). I still can't get the genie one, gah.

Nope . What your reasoning shows is why Dirichlet's principle ("the pigeonhole principle") cannot be used to prove part (a) with the interval [1,113]. If it were this simple, I wouldn't have suggested 2 hours .

As for the genie one, here's a hint. Try for the case n=2. You can do it in 3 steps worst-case. That should get you started.

quote:

Originally posted by Flyboy217 3a) You are blindfolded with a round table in front of you. It is marked with 4 positions (1, 2, 3, and 4), one in each quadrant. There are 4 cups on the table, one per quadrant, each initially randomly either face up or face down (which you cannot see). On each turn, you may instruct the genie to flip the cups in whichever numbered positions you wish. He will oblige, and then rotate the cups around the table as he wishes, so that the cups are (potentially) all in new positions, but in the same rotational order. Your goal is for all the cups to be face up. The genie will tell you if you've won. Can you give a solution that will always win the game, regardless of his sneaky rotations? [30 min]

following algorithm:

flip all
flip any random cup
flip all
flip any random cup

you are BOUND to win, because you are exhausting the space of possibilities. Explanation -somewhat shitty-
if all cups are down and you flip them all, you win. - easy
if they are NOT all down and you flip them all, you ELIMINATE that possibility. By flipping a SINGLE cup, you are eliminating the possibility that THIS one cup was down and the others were up. But that elimination is only true for this one cup in that one spot. It does not matter which cup you flip, since the genie can arbitrarily rotate them, but since the ORDER does not change, you will -eventually- test every cup.
Next you flip all cups again. If you don't win, flip a random single cup again. then flip all, flip single.

at leas that is what i came up with. Eventually you should win, unless the genie HAPPENS to rotate the cups so that you always pick the same cup to flip as a single cup. SO i guess this isn't right, but i think i am on the right way to getting there. Maybe you need to alternate somewhat more like:
flip all
flip first
flip all
flip 2-3
flip all
flip 4-2
flip all
flip 1-4
flip all

so that eventually you will have flipped all pairs and triplets of cups.

___________________

get font

I see your 4 Crushs and raise you 3 As The Rush Comes. - Yan from PvD's first summerstage event in '03

quote:

Originally posted by DJ-Fuq imo, these r badly worded mostly

dude i totally agree

quote:

Originally posted by drizzt81 so that eventually you will have flipped all pairs and triplets of cups.

thought some more:

you definetely need to flip two adjacient ones and then two 'across' ones like 1-2, 1-3, between flipping all four so that you are _guaranteed_ to flip at least one different cup every time, since they are in he same rotational order.

edit:

so I am getting there:

1. flip all -either we win, or we know that there are 1-3 down cups
options:
DUUU
DUDU
DDUU
DDDU

2. now we flip an ADJACENT pair which gives us the following options for each:
DUUU -> DUUU or DDDU (or rotation thereof)
DUDU -> UDDU
DDUU -> DDDD or UUUU (win) or DUDU
DDDU -> DDDU or UUUD (or rotation)

3. now we flip all again, which eliminates the 'red' option above and leaves us with these:
DUUU
DDUU
DUDU
UUUD

4. because we do not know how the geenie has rotated them, we cannot just continue repeating step 2+3, which would always kill two opportunities, so we need to be a little inventive and now flip a NON-adjacient pair to eliminate another oppotunity:
DUUU -> DDUD or UUDU
DDUU -> UDDU or DUDU
DUDU -> UUUU(we win) or DDDD
DDDU -> UDUD or DUDD

5. flip all, to once again eliminate the red option. this COMPLETELY eliminates that ROW! that means that we have 'killed' of this brach of our 'options tree'.
If we keep operating with this routine, we will win. Each time that we complete step 2-5 we will reduce the problem size, since we will eliminate one branch. Therefore, by induction, this algorithm will terminate by us winning.

___________________

get font

I see your 4 Crushs and raise you 3 As The Rush Comes. - Yan from PvD's first summerstage event in '03

Last edited by drizzt81 on Oct-11-2003 at 22:48

quote:

Originally posted by drizzt81 thought some more: you definetely need to flip two adjacient ones and then two 'across' ones like 1-2, 1-3, between flipping all four so that you are _guaranteed_ to flip at least one different cup every time, since they are in he same rotational order.

Impressive. You've got all the right ideas. I imagine it wouldn't take you long to formulate a complete winning strategy if you tried. In fact, it's close enough that I'll give one solution.

SPOILER







1 = Flip cups that are across
2 = Flip adjacent cups
3 = Flip any three
4 = Flip all

4, 1, 4, 2, 4, 1, 4, 3, 4, 1, 4, 2, 4, 1, 4

Can you find another?

quote:

Originally posted by Flyboy217 Impressive. You've got all the right ideas. I imagine it wouldn't take you long to formulate a complete winning strategy if you tried. In fact, it's close enough that I'll give one solution. SPOILER 1 = Flip cups that are across 2 = Flip adjacent cups 3 = Flip any three 4 = Flip all 4, 1, 4, 2, 4, 1, 4, 3, 4, 1, 4, 2, 4, 1, 4 Can you find another?

oops read this 'after' i devised the post above :/

I was thinkin whether i need to flip three cups, just to make sure that i am not flipping two adjacient cups again. I understand that the problem will be that you can be caught in a loop for a while, if you happen to retiterate the same set of cup flips over and over again, but i though -for some reason- that you would always reduce the problem size.

now I am back to my REAL work.. I 'hate' you for giving me these problems, i should have been coding instead of trying to solve "tea party" problems

j/k

___________________

get font

I see your 4 Crushs and raise you 3 As The Rush Comes. - Yan from PvD's first summerstage event in '03

quote:

Originally posted by Flyboy217 b) For what values of N is this possible (in part a, N=4)? [No limit.]

only for integers
I think it might actually fail for N=6 already, because 2 and four have a GCF of >1, but i am going on a hunch here.

___________________

get font

I see your 4 Crushs and raise you 3 As The Rush Comes. - Yan from PvD's first summerstage event in '03

quote:

Originally posted by drizzt81 only for integers I think it might actually fail for N=6 already, because 2 and four have a GCF of >1, but i am going on a hunch here.

It in fact fails for n=3. Not sure where you're going with the GCF of 2 and 4, but since I myself never solved this one, I can't comment . I'm told the solution is non-trivial. I'll get on it soon .

quote:

Originally posted by Flyboy217 Okay, I can give you a proof. The cardinality of the set of rational numbers is countably infinite. The cardinality of the set of irrational numbers is uncountably infinite. The division of a countable infinity by an uncountable one yields zero. I promised you a link: http://mathforum.org/library/drmath/view/52145.html

wow, i cant believe we argued all this time just for this.

ok the very first thing i said in response to this was that ur using limits, and that the answer would tend to be zero, BUT truly it is really really small (which is stated in the article btw).

___________________
it was the greatest feeling of nothingness i have ever experienced...

heres the quote from the proof you gave:

Now, that doesn't mean choosing a rational number is impossible, but it just means it's VERY unlikely if you're truly choosing at random.

___________________
it was the greatest feeling of nothingness i have ever experienced...