NorCal Melee Power Rankings - Summer '15 Update - In Sickness and In Filth

[Leruinoir]

Yo shroomed, i heard you played a kid named sage in san fran. that guy is my good friend from hawaii, I want to smash with you. lol. how can we make this happen. HIT ME UP SHROOMED. MKDAMASO23@GMAIL.COM. I am free most of the time, I live in berkeley, if you ever managed to bring a setup down here, i have a living room that can host a small tv and set up!

 

[shehehe11]

lolwtf I'm not traveling outside of the UCB campus to smash with ppl. only traveling for tournies.

 

[Fly_Amanita]

Spoiler

The second student knows the sum but not the product. He also knows that it is impossible to deduce the sum from the product. This means that whatever sum he knows, he is able to use it to deduce that knowledge of the product (which he doesn't know) does not lead to knowledge of the sum. This means that the sum must be such that ALL ways of splitting it into two numbers give numbers whose product is such that it has at least two ways of factoring it. There is only one such number, which is 11. For a while I was hung up on the fact that 4*7=28 and the only alternate way of factoring it is 2 and 14 which sum to 16. But the second student doesn't know that the first student knows the sum is less than 14, so this is OK.

Spoiler

You essentially claim that 11 is the only integer greater than 3 that can't be written in the form p+q or p+p^2, where p, q are primes. I am dubious of this and want a proof.

 

[KILLA.FOR.CASH.]

how you guys are so proficient in math is way beyond me.

1+1 = window

 

[pockyD]

Spoiler

You essentially claim that 11 is the only integer greater than 3 that can't be written in the form p+q or p+p^2, where p, q are primes. I am dubious of this and want a proof.

well you can also just consider that it's the only integer greater than 3... and less than 14 for which that is true

 

[PHIL07]

update the rankings. atleast before the next cgc
thanks

 

[pockyD]

it hasn't even been 2 months!

 

[Shroomed]

i feel like crap for not figuring out this math puzzle

 

[choknater]

do it after cgc ehhehe

 

[HomeMadeWaffles]

this picture actually made me laugh out loud

http://www.facebook.com/?ref=logo#!/photo.php?pid=7056195&fbid=483538755992&id=602460992

 

[Brian]

jeff is so gangster
i see him sometimes around campus
we have moments

 

[choknater]

L M A O

how can u not laugh at that

 

[ConnorTheKid]

is that Dajuan holding a cup of kool-aid?! LOL

 

[Shroomed]

i knew people would assume that's kool-aid

racists

 

[tarheeljks]

it's purple drank right (i didn't even see the pic)

 

[pockyD]

it's actually red drank

 

[pockyD]

sheridan do you have the tio for gsg? aib seems to be having trouble showing the pools results

 

[DarrellD]

Whats norcal without sheridan =(

 

[HyugaRicdeau]

Yes I do have the tio file. I think I have also emailed it to Lucien. If you want me to email you a copy, give me your address.

P.S. Hi from Zakopane. It snowed here a couple days ago, everything is beautiful. Tomorrow I'm going to Stockholm. I'm coming back to the US on the 12th, so perhaps I'll see some of you guys the following weekend, which happens to contain my birthday, so maybe I'll have a get-together somewhere.

 

[joeplicate]

is that the weekend of the tournament?

are we gonna go to your house to celebrate your bday?? =D

 

[pockyD]

another riddle! taken from here

I think I have the answer, but I didn't send my solution in or anything, so I don't 'know' if it's the answer they're looking for; my solution would save all of them 100% of the time though, I believe, so I'm fairly confident it's "correct"

A hundred prisoners are gathered together by their warden. Each prisoner gets two gloves: one black and one white. They are told that they have one night in order to plan a strategy, after which no communication between them will be possible. In the morning, they are told, each prisoner will have a distinct real number painted on his forehead. Each prisoner will be able to see the numbers painted on all other prisoners, but not his own. What each prisoner needs to do is to decide which glove to put on which hand. Once all prisoners have donned all gloves, they will be placed in a long line, one beside the other, ordered according to the value of the number on their foreheads, and will be asked to hold hands. If the pairs of hands holding each other all have same-colored gloves, all 100 prisoners will be set free.
Your goal is to design a strategy that will maximize the probability of this happening.



...and yeah, my solution is definitely, 'mathy', not really a trick or tricks

 

[TaFoKiNtS]

However, I will refrain from answering for a few days.

 

[pockyD]

don't give hints!

 

[MacD]

man, these puzzles make me realize how much i don't know about math

 

[Violence]

Yeah, I think I'll work on this too. Looks fun.

 

[Fly_Amanita]

I'll give this a shot tomorrow/tonight.

edit: Okay, I found something that I'm pretty sure works, but I don't have a proof yet.

 

[Doc King]

How come HMW has a question as his main(s), he mains Doc and Fox.

 

[KoRoBeNiKi]

How come HMW has a question as his main(s), he mains Doc and Fox.

he has been using a whole lotta characters.

Marth, Falcon, Jiggs (lolwut) for example

 

[Fly_Amanita]

Alright, here's what I've got.

Spoiler

Number the prisoners from 1, 2, ..., n (I'm going to do this more generally; in the case of this particular problem, take n = 100). For each prisoner k, where k is odd, define a function f_k that maps the ordered (n-1)-tuples of elements in {1, 2, ..., n}\{k} into {0,1}, where f_k maps an (n-1)-tuple to the parity of the number of times you would switch two coordinates in the given n-tuple in order to get (1, 2, ..., k-1, k+1, ..., n); this doesn't necessarily have to be the most efficient way of switching coordinates; you can switch them however you like. That this function is well-defined is a consequence of that the number of such necessary flips will always be even or odd (I have a goofy proof of this that basically implies that the determinant of the a certain (n-1)x(n-1) matrix would have to be both 1 and -1 if you could do both). For even k, define f_k essentially the same way, but return 1 minus the parity instead.

In accordance with the real numbers painted on the people's heads, define a permutation of {1, 2, ..., n} σ, where the number on σ(i)'s forehead (call this r(σ(i)) is less than that of σ(i+1)'s for 1<=i<n. Any prisoner σ(i) can see that r(σ(1)) < r(σ(2)) < ... < r(σ(i-1)) < r(σ(i+1)) < ... < r(σ(n)). Have him look at the image of (σ(1), σ(2), ..., σ(i-1), σ(i+1), ..., σ(n)) under f_σ(i). If it's zero, have him wear the white glove on his left hand; otherwise, have him wear it on his right.

Note that we want each prisoner in the line to have made the opposite decision of how to wear the gloves as the person to his right for each person other than the last, i.e. the number the prisoner σ(i) gets him from his function is different from the number σ(i+1) gets from his function for 1<=i<n.

In order to prove this works, consider f_σ(i)(σ(1), ..., σ(i-1), σ(i+1), σ(i+2), ..., σ(n)) and f_σ(i+1)(σ(1), ..., σ(i-1), σ(i), σ(i+2), ..., σ(n)). Suppose that it takes k switches of pairs of σ(1), ..., σ(i-1), σ(i+1), σ(i+2), ..., σ(n) to get 1, 2, ..., σ(i)-1, σ(i)+1, ..., n. Note that if we apply essentially the same switches to σ(1), ..., σ(i-1), σ(i), σ(i+2), ..., σ(n), but with σ(i) in the role of σ(i+1), we get 1, 2, ..., σ(i)-1, σ(i)+1, ..., n, but with σ(i) in the position that σ(i+1) would occupy. Now, number the positions of each of the prisoners in this list of n-1 people from least to greatest; say p1 is the spot that 1 is in, p2 is the spot that 2, is in, ...., p(σ(i)-1)=σ(i)-1, p(σ(i)+1)=σ(i), ..., σ(n)=n-1.

Suppose σ(i+1) > σ(i).

Suppose σ(i+1) and σ(i) are odd. Then σ(i) is an even-indexed position (this is because of the skip from σ(i)-1 to σ(i)+1), and σ(i)+1 is an odd position. If we want to move σ(i) to its proper location, we can translate it with its element to the left over and over again until we get it where we want it to be. This will take p(σ(i))-p(σ(i)+1)) translations, which is an odd number, so f_σ(i+1)(σ(1), ..., σ(i), σ(i+2), ..., σ(n)) is the parity of k plus an odd number, while f_σ(i)(σ(1), ..., σ(i-1), σ(i+1), ..., σ(n)) is the parity of k; these parities are different, so the prisoners will make the correct decisions.

Now suppose σ(i+1) and σ(i) are both even. Then σ(i) is in an odd position and σ(i)+1 is in an even position. By essentially the same logic as above, we see that the parities of the numbers of translations are different (note that in this case the functions return one minus the parity, but the prisoners still make opposite decisions).

Assume σ(i+1) is odd and σ(i) is even. Then σ(i) is in an even position and σ(i)+1 is in an even position. Then the number of translations to get the natural order from here is now even, so the numbers of parities of the two numbers of translations are now the same; however, since the even dude returns one minus the parity, his function returns a different output as the other guy. Yay.

Assume σ(i+1) is even and σ(i) is odd. Then σ(i) is an odd position, as is σ(i)+1. Then the number of translations from here to the usual position is even. Blah, blah, same as above.

The case where σ(i+1) < σ(i) is probably similar, but a little easier since you don't have that goofy skip from σ(i)-1 to σ(i)+1 doing weird things to the parity of the positions. I'm not going to write it out.

So, yeah. Adjacent prisoners make different decisions. Woohoo.

I didn't proofread this. I might do that later. Maybe not.

Probably not.

edit: I did it! I accidentally typed an "m" in place of a "k" in one place, but I think that's all that was wrong.

 

[pockyD]

i'll post the solution i found later tonight if i remember

it's similar but simpler/more well defined

Spoiler

in my version, person 1 acts, then everyone else acts simultaneously, if you care to try and simplify/adapt your solution

 

[Fly_Amanita]

I'm pretty sure all of the concepts I used were well-defined, although I probably worded them terribly since I usually just wrote the first thing that came to mind when typing my post. Plus, precisely stating what the exact mathematical objects I was dealing with would have only made my post longer. </johns>

Spoiler

I tried tinkering around with things where one person initially chose what he was going to do and the others were aware of that, but I don't think it worked, at least for some similar case with a small number of prisoners. Knowing myself, I probably made a careless error somewhere along the way. I'll revisit the idea once I'm willing to think about this problem again.

 

[pockyD]

Spoiler

well, your flipping function seemed inherently ill-defined given that you specified the user could use whatever system he wanted

my count is simpler; it counts the number of total order inversions between any two numbers that a person sees... that is to say, any pair of numbers that is the opposite order of what it should be

i.e.
123 = 0,
132 = 1 (2 and 3),
312 = 2 (1 and 3, 2 and 3),
321 = 3 (1 and 3, 2 and 3, 1 and 2)

edit: simpler may not have been the right word, but for any permutation, there is a single value that you would derive from this approach, which to me makes it easier to understand and compute

and other people should post fun riddles/puzzles too!

 

[Fly_Amanita]

Spoiler

My function returns the parity of the number of coordinate switches necessary to get the natural order of the coordinates. e.g. with 132, you can switch 2 and 3 and be done (1 switch), but you could also do something like switch 1 and 2, then switch 2 and 3, then switch 1 and 3 (3 switches). The point is that regardless of what transpositions you decide to make, the number of transpositions will always have the same parity; e.g., every way of deriving 123 from 132 requires an odd number of coordinate switches. If it weren't for that, then yes, the function wouldn't be well-defined. The proof is essentially the same as the linear algebra approach to showing that any permutation is even or odd, but not both.

edit:

Spoiler

I might as well post that proof here. Suppose you have some n-tuple of elements. It doesn't particular matter what they are as long as they are distinct, so let's work with the standard basis of R^n. Let f be a permutation of {1, 2, ..., n} and consider the n-tuple (e_f(1), e_f(2), ..., e_f(n)). Suppose you can get (e_1, ...., e_n) from this via both an even number of coordinate transpositions, m, and an odd number, k. Now let M be the matrix whose ith row is e_f(i). We see that we can obtain I_n by making m certain row interchanges, or k. Since switching two rows of a matrix negates the determinant of the new matrix, we see that det(M)=((-1)^m)det(I_n)=(-1)^m=1. On the other hand, det(M)=((-1)^k)det(I_n)=(-1)^k=-1. Thus, any two ways of obtaining (1, 2, ...., n) from (f(1), ...., f(n)) by switching pairs of coordinates repeatedly will always require that the number of coordinate switches of both have the same parity.

 

[DarrellD]

Two serious IC's going at it on this one

 

[Violence]

Puzzle: Suppose you have an infinite number of L-Trinominoes(Picture an L shape in tetris, only with three blocks, instead of four).

The goal is to fill up a square grid board as much as possible by putting the Trinominoes onto the board.

Please prove that on any square board of size n by n, where n is a power of two, there will always be exactly one space left over.

 

[Brian]

i feel like i did that in my discrete math class
i cant remember how though

 

[Fly_Amanita]

Alright.

Spoiler

In the case where n=0, note that there is already only one space left. Incidentally, note that it is a corner space. Suppose that for some n>=0, you can fill a 2^n by 2^n grid with trinominoes such that there is only space left empty and it is in the corner. Consider a 2^(n+1) by 2^(n+1) grid. Partition it into four 2^n by 2^n grids. In one of these four, fill up the grid with trinominoes such that the corner that coincides with a corner of the 2^(n+1) by 2^(n+1) grid is left empty. In each of the other three, leave the corner closest to the center of the 2^(n+1) by 2^(n+1) grid empty. There are now three empty spaces near the center in the shape of a trinomino, that you can fill in with one. Now, the 2^(n+1) by 2^(n+1) grid is entirely filled with trinominoes except for one spot in the corner.

Done.

edit: Is trinomino actually the word for those shapes?

 

[pockyD]

mathy stuff i didn't read

i don't doubt that what you're saying is true (if it's not clear yet, I'm not really bothering to verify its accuracy)

I am just saying it would have been simpler to define it my way and not NEED to perform such a proof

Anyways,

Spoiler

Create an arbitrary ordering of your prisoners, 1-100. Some Patient Zero selects an orientation (say Left-Black/Right-White) to denote an odd number of inversions, while the opposite (Left-White/Right-Black) denotes an even number. Patient Zero can be any of them, but just pretend they are 1.

After the numbers have been painted, every single person counts the number of inversions, defined in my earlier post, they see (in the group of 99 people visible to them). Patient Zero then dons his gloves.

For people that are the same evenness/oddness as Patient Zero in the arbitrary numbering system in the first step (If Patient Zero is 1, then persons 3, 5, 7, etc.), if their inversion count is the same evenness/oddness as Patient Zero's count, they mimic his glove orientation. Otherwise, they do the opposite orientation.

For people of the opposing evenness oddness as Patient Zero (If Patient Zero is 1, then persons 2, 4, 6, 8), they do the opposite; if their inversion count is the same as Patient Zero's, then they reverse his orientation; otherwise, they mimic it.

I'm not feeling up to doing the proof right now, but aside from citing the underlying mathematical principles that would make it work (I don't know them anymore, but there's definitely a lot of science behind inversions), I would start from a 'correct' arbitrary numbering system (for which this approach is trivially correct), then explore introducing inversions one at a time, evaluating the cases where a person and/or Patient Zero is between the inversion, outside the inversion, or part of the inversion - a sort of induction

The intuition seems very similar to Fly's answer; I didn't delve too deeply into Fly's math, but it seems to me that everyone except Patient Zero is capable of acting at the same time with my strategy; feel free to correct me; as I've said, I haven't had this answer verified anywhere

 

[Fly_Amanita]

Okay, that's fine. I have a bad habit of pursuing the first thing that I think I can make work, regardless of how ugly it is.

 

[pockyD]

it kills me that the plural of aquarium isn't aquaria