You sit on ESOC all day puzzling! You know nothing of hard life!

This is for discussions about news, politics, sports, other games, culture, philosophy etc.
User avatar
Korea South Vinyanyérë
Retired Contributor
Donator 06
Posts: 1839
Joined: Aug 22, 2016
ESO: duolckrad, Kuvira
Location: Outer Heaven
Clan: 팀 하우스

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by Vinyanyérë »

ovi12 wrote:
Vinyanenya wrote:
ovi12 wrote:Ok 1 more. I would type it up but I'm not at computer:

https://imgur.com/a/T94Ae


This is probably possible or impossible depending on how we define the words "any" and "fact", as well as the sample space of the professors' salaries. For example, if salaries are required to be strictly positive, then knowing the average salary x means that you know that no professor's salary can be larger than 2nx. I'm guessing that the intended solution is somewhere along the lines of:

[spoiler]The professors arrange themselves in a circle. One of them takes their salary, select some arbitrary number in secret, and adds it to their salary, then writes it down and passes their paper to the next professor. The next professor picks a secret number, then writes the sum of the number they received, their salary, and their secret number on their paper, then passes it down. This continues until the process reaches the first professor, who subtracts their secret number from the total, writes that number on the unused side of their paper, and passes the piece of paper down. Every professor in turn subtracts their secret number from the number they received until everyone's done so, at which point the last professor wrote down the total sum of their salaries.[/spoiler]


My solution had the same idea, but now that I read Humman's answer I think he is the correct one. There are two reasons:

1) Since whatever the method they would all know the average at the end, so they would know no professor makes more than the average * n. This contradicts the last sentence in the riddle. But the last sentence in the riddle explicitly forbids them knowing such an information. This problem is from a very good math book, and this is too a contradiction for the author to not have caught (sadly I didn't catch it).

2) Being a math book, it is proof-oriented. The idea of getting them in a circle and plus minus a random number is good, but I have no idea how you would go about proving that they cannot derive any information whatsoever (I'd actually be very interested if you knew how) from performing this proccess. Therefore I think Humann's answer is correct, because it is a proof that it's impossible.


This question is actually way deeper than I expected so I'll have to get back to you on whether or not it's actually possible. Essentially, every professor has a salary represented by some random variable X_i and can generate their own random variable Y_i. On the first pass through, the first professor does some sort of transformation Z_1 = f_1(X_1, Y_1), and in general, the ith professor does a transformation Z_i = f_i(Z_{i-1}, X_i, Y_i). On the second pass, the first professor does some transformation g_1(Z_n, X_1, Y_1) = Q_1 and in general everyone does g_i(Q_{i-1}, X_i, Y_i) = Q_i. The key is that the mutual information I(X_i; Z_i) and I(X_i; Q_i) must be 0 at every step and that at the end, Q_n = n*E[X_1 + ... + X_n]. Enforcing both of these together is not easy and might not be possible; I have to think about it for a while longer.

Fortunately, if any solution works, it'll probably be one where all the X's are i.i.d., all the Y's are i.i.d., all the f's are the same, and all the g's are the same. I originally proposed that f and g be addition and subtraction; unfortunately I'm not sure that those are going to work. I had something promising going where X_i and Y_i were both uniform distributions on the set {0, 1} and f and g were the binary XOR operations, but that doesn't give the average in the end.

I'm assuming here that "can't derive any information" really means "the mutual information between the r.v. that any professor receives and the r.v. of any other professor's salary is always zero", which seems like the only good interpretation that doesn't make the question trivially impossible. That formalizes the problem and makes it possible to construct a rigorous proof.
duck
:mds:
imo
User avatar
No Flag Jaeger
Jaeger
Posts: 4492
Joined: Feb 28, 2015

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by Jaeger »

Vinyanenya wrote:
ovi12 wrote:
Show hidden quotes


My solution had the same idea, but now that I read Humman's answer I think he is the correct one. There are two reasons:

1) Since whatever the method they would all know the average at the end, so they would know no professor makes more than the average * n. This contradicts the last sentence in the riddle. But the last sentence in the riddle explicitly forbids them knowing such an information. This problem is from a very good math book, and this is too a contradiction for the author to not have caught (sadly I didn't catch it).

2) Being a math book, it is proof-oriented. The idea of getting them in a circle and plus minus a random number is good, but I have no idea how you would go about proving that they cannot derive any information whatsoever (I'd actually be very interested if you knew how) from performing this proccess. Therefore I think Humann's answer is correct, because it is a proof that it's impossible.


This question is actually way deeper than I expected so I'll have to get back to you on whether or not it's actually possible. Essentially, every professor has a salary represented by some random variable X_i and can generate their own random variable Y_i. On the first pass through, the first professor does some sort of transformation Z_1 = f_1(X_1, Y_1), and in general, the ith professor does a transformation Z_i = f_i(Z_{i-1}, X_i, Y_i). On the second pass, the first professor does some transformation g_1(Z_n, X_1, Y_1) = Q_1 and in general everyone does g_i(Q_{i-1}, X_i, Y_i) = Q_i. The key is that the mutual information I(X_i; Z_i) and I(X_i; Q_i) must be 0 at every step and that at the end, Q_n = n*E[X_1 + ... + X_n]. Enforcing both of these together is not easy and might not be possible; I have to think about it for a while longer.

Fortunately, if any solution works, it'll probably be one where all the X's are i.i.d., all the Y's are i.i.d., all the f's are the same, and all the g's are the same. I originally proposed that f and g be addition and subtraction; unfortunately I'm not sure that those are going to work. I had something promising going where X_i and Y_i were both uniform distributions on the set {0, 1} and f and g were the binary XOR operations, but that doesn't give the average in the end.

I'm assuming here that "can't derive any information" really means "the mutual information between the r.v. that any professor receives and the r.v. of any other professor's salary is always zero", which seems like the only good interpretation that doesn't make the question trivially impossible. That formalizes the problem and makes it possible to construct a rigorous proof.


I have to spend some more time (tomorrow I think) to understand your response, but before I do that I wanted to point out a couple things:

1) I said a proof was expected, but for sure it was not such a rigorous proof. This problem is a "warm-up" from a problem-solving book; the book in general is not really focused on rigour and for sure doesn't have knowledge of R.V.'s as a prerequisite

2) Maybe I will understand this when I spend more time on your response, but why even bring R.V.'s into this? Why not just call them functions? Is it because you're just very used to statistics so you sometimes use the word R.V. where others would use function? (I know R.V.'s are functions anyway)

3) Do you agree with me that if we follow the problem strictly as written, HUMMAN is right?
last time i cryed was because i stood on Lego
User avatar
Turkey HUMMAN
Lancer
Posts: 817
Joined: Apr 16, 2017
ESO: HUMMAN

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by HUMMAN »

Nevermind i ask the question: 4 aoe3 players meet up and they found 1000 dolar in street. Diaruga, mitoe, jerom, and interjection. They agree to share money by democracy instead of split, because their currency is not dollar in home country. However they cant decide who will propose an option first. Diarouga said " lol i am pr 40 so we have to offer by pr rank, if at least %50 accepts it should be accepted. If the offer is rejected, let other guy offer a proposition to rest." First Jerom got salty a little but they eventually agree. For example if dia's offer cant pass or be exact(edited)%50 mitoe will propose and will be voted by 3 people, since dia sucked he wont vote. Same for others. Order is dia mitoe jerom interjection. All players are smart and know best option in order to get money, and know others will choose best too. There is no chance involved. What should dia propose and get the max money he can; since it would be a consolation after aizamk beats him?

For example in a scenario where dia splits by 500 500 0 0, it wont be accepted.
Image
User avatar
Sweden Gendarme
Gendarme
Donator 03
Posts: 5132
Joined: Sep 11, 2016
ESO: Gendarme

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by Gendarme »

Jerom can't propose anything because Interjection will say no to everything and take all the money himself. Jerom will say yes to Mitoe's proposition as long as he gets one dollar because at that point it is his best bet. Interjection will vote against anything Mitoe says because Jerom is powerless and Interjection will hence get all the money.

Assuming an equal split of votes means the proposition is rejected, Mitoe is completely powerless too and would be happy with one dollar as well.

Diarouga knows all this so he gives Mitoe and Jerom one dollar each, and takes 998 dollars himself.
Pay more attention to detail.
User avatar
Turkey HUMMAN
Lancer
Posts: 817
Joined: Apr 16, 2017
ESO: HUMMAN

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by HUMMAN »

Close but i said at least %50 meaning 2 yes votes is enough for dia.
Image
User avatar
Sweden Gendarme
Gendarme
Donator 03
Posts: 5132
Joined: Sep 11, 2016
ESO: Gendarme

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by Gendarme »

Ok, so Mitoe would give Jerom 1 dollar and 999 dollars to himself on his turn, and Interjection would get nothing.

So diarouga gives 2 dollars to Jerom, 1 dollar to Interjection, and takes 997 dollars himself.
Pay more attention to detail.
User avatar
Turkey HUMMAN
Lancer
Posts: 817
Joined: Apr 16, 2017
ESO: HUMMAN

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by HUMMAN »

Nah, jerom gets 1000 dollar if he rejects mitoes offer.
Image
User avatar
Sweden Gendarme
Gendarme
Donator 03
Posts: 5132
Joined: Sep 11, 2016
ESO: Gendarme

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by Gendarme »

Oh, you can vote on your own proposition? Well then...
Pay more attention to detail.
User avatar
Sweden Gendarme
Gendarme
Donator 03
Posts: 5132
Joined: Sep 11, 2016
ESO: Gendarme

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by Gendarme »

...Interjection is powerless, so he'll be happy with one dollar. Mitoe can offer one dollar to Interjection and take 999 dollars himself, and Jerom would get nothing, so Jerom is happy with one dollar as well.

diarouga gives one dollar to Jerom, two dollars to Interjection, and takes 997 dollars himself.
Pay more attention to detail.
User avatar
Turkey HUMMAN
Lancer
Posts: 817
Joined: Apr 16, 2017
ESO: HUMMAN

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by HUMMAN »

Yeah dia doesnt need to give interject jerom is enough for pass, sorry couldnt explain clear. Also most people say like 200 300 300 200 lol
In last 2 jerom wins anyway, so mitoe would offer 999 for him 1 for inter. So jerom doesnt want mitoe to offer, 1 dollar from dia is enough for him.
Image
User avatar
Sweden Gendarme
Gendarme
Donator 03
Posts: 5132
Joined: Sep 11, 2016
ESO: Gendarme

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by Gendarme »

Oh yeah, of course. My bad. I forgot about the 50% again.
Pay more attention to detail.
Netherlands momuuu
Ninja
Posts: 14237
Joined: Jun 7, 2015
ESO: Jerom_

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by momuuu »

Im pretty sure jerom would take the gamble that mitoe is a socialist and refuse the one dollar haha.

I think offering either one dollar to jerom or interjection makes diarouga win right. Mitoe would reject an offer of one dollar, because he would get to offer interjection one dollar, which interjection has to accept (otherwise jerom offers himself 1000 dollar). Jerom wont get money from mitoes offer so he would want to accept this one, and interjectin actually has a choice. I guess itd be safer to go with one dollar for jerom then.
No Flag ssaraf
Dragoon
Posts: 208
Joined: Jun 19, 2015
ESO: robinhood_xing

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by ssaraf »

@HUMMAN , Can one vote on his own preposition? If yes , then why is (500 , 500 , 0 , 0) NOT accepted?
User avatar
Turkey HUMMAN
Lancer
Posts: 817
Joined: Apr 16, 2017
ESO: HUMMAN

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by HUMMAN »

Yes one can vote to his proposition if dia goes for 500 500 0 0 other three refuses, jerom and inter refuse because they got nothing, and mitoe refuses because in his turn 999 0 1 wins for him.
Image
No Flag ssaraf
Dragoon
Posts: 208
Joined: Jun 19, 2015
ESO: robinhood_xing

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by ssaraf »

Then as jerom suggested : (999 , 0 , 1 , 0). Rite?
User avatar
Turkey HUMMAN
Lancer
Posts: 817
Joined: Apr 16, 2017
ESO: HUMMAN

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by HUMMAN »

Yeah it is 999 0 1 0 democracy rules!
Image
No Flag ssaraf
Dragoon
Posts: 208
Joined: Jun 19, 2015
ESO: robinhood_xing

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by ssaraf »

Left alone, I'm a word with five letters.
I'm honest and fair, I'll admit.
Rearranged, I'm of no use to trains.
Again, and I'm an overt place, warm and well lit.
What am I?


Mine: You have a box containing 20 strings. At every step, you select two available ends of the strings at random and tie them together (an end is considered unavailable if it's already tied to another end, and available otherwise). You continue to do this until no more ends remain. On average, how many loops (a set of at least 1 string where the first string is tied to the second, the second to the third, ..., and the last string back to the first) do you make by doing this?

Bonus question: How many loops do you make on average with n strings?


Did anyone solve these 2 puzzles?

My attempt at 20 strings problem : Min number of loops = 1 BIG LOOP , Max number of loops = 20 (each string is tied to itself). Now lets see what other loops are possible. We make a loop with 1 string , then the other 19 strings can make a BIG LOOP , so we have 2 loops. Similarly, we can make 2 loops with 2 strings and the other 18 strings can make a BIG LOOP (giving us a total of 3 loops in this case). Hence, we can make any number of loops from 1 to 20 with 20 strings. Thus we have :

Total Number of loops = T = Summation from 1 to 20 = 210 [using (n).(n+1)/2]
Number of loops possible = C = Count = 20 [As we saw, we can make every number of loops from 1 to 20, Thus for the general case its 'n'].
Average = T/C = 210/20 = 10.5 [For the General case --------> (n).(n+1)/2.n ==> (n+1)/2]
User avatar
Korea South Vinyanyérë
Retired Contributor
Donator 06
Posts: 1839
Joined: Aug 22, 2016
ESO: duolckrad, Kuvira
Location: Outer Heaven
Clan: 팀 하우스

Re: You sit on ESOC all day puzzling! You know nothing of hard life!

Post by Vinyanyérë »

ovi12 wrote:
Vinyanenya wrote:
Show hidden quotes


This question is actually way deeper than I expected so I'll have to get back to you on whether or not it's actually possible. Essentially, every professor has a salary represented by some random variable X_i and can generate their own random variable Y_i. On the first pass through, the first professor does some sort of transformation Z_1 = f_1(X_1, Y_1), and in general, the ith professor does a transformation Z_i = f_i(Z_{i-1}, X_i, Y_i). On the second pass, the first professor does some transformation g_1(Z_n, X_1, Y_1) = Q_1 and in general everyone does g_i(Q_{i-1}, X_i, Y_i) = Q_i. The key is that the mutual information I(X_i; Z_i) and I(X_i; Q_i) must be 0 at every step and that at the end, Q_n = n*E[X_1 + ... + X_n]. Enforcing both of these together is not easy and might not be possible; I have to think about it for a while longer.

Fortunately, if any solution works, it'll probably be one where all the X's are i.i.d., all the Y's are i.i.d., all the f's are the same, and all the g's are the same. I originally proposed that f and g be addition and subtraction; unfortunately I'm not sure that those are going to work. I had something promising going where X_i and Y_i were both uniform distributions on the set {0, 1} and f and g were the binary XOR operations, but that doesn't give the average in the end.

I'm assuming here that "can't derive any information" really means "the mutual information between the r.v. that any professor receives and the r.v. of any other professor's salary is always zero", which seems like the only good interpretation that doesn't make the question trivially impossible. That formalizes the problem and makes it possible to construct a rigorous proof.


I have to spend some more time (tomorrow I think) to understand your response, but before I do that I wanted to point out a couple things:

1) I said a proof was expected, but for sure it was not such a rigorous proof. This problem is a "warm-up" from a problem-solving book; the book in general is not really focused on rigour and for sure doesn't have knowledge of R.V.'s as a prerequisite

2) Maybe I will understand this when I spend more time on your response, but why even bring R.V.'s into this? Why not just call them functions? Is it because you're just very used to statistics so you sometimes use the word R.V. where others would use function? (I know R.V.'s are functions anyway)

3) Do you agree with me that if we follow the problem strictly as written, HUMMAN is right?


1) Hmm, it might then depend on how the author feels about drawing from all real numbers uniformly at random (not a mathematically rigorous thing to do), and if that's not allowed, how the author feels about the distinction between negligibly small amounts of information vs. truly zero information. If we can sample from a uniform distribution on all real numbers, then the adding + subtracting strategy should provably give no information to any professor.

2) Random variables are technically functions but don't really behave in the same way as general functions do. Functions are mappings from domains to ranges, and so the word "function" would imply that we care about both the domain and range. Oftentimes with random variables - including this time with professors' salaries and the random numbers that they generate - we don't care about the domain, only the range. That said, I brought random variables into the picture out of a need to start discussing mutual information between two of them, which models how much one professor can figure out about others' salaries based on what they receive.

3) Maybe. I've seen a similar problem to this one before (don't remember the exact details) where I think the idea was to do some sort of adding everything up with random numbers to hide information. It seems like the author would be making an interesting problem trivially impossible with a technicality. Still, if you allow negative salaries and truly arbitrary random numbers, the adding/subtracting strategy should be able to give the average salary without any professor knowing anything more than the average salary and their own.
duck
:mds:
imo

Who is online

Users browsing this forum: No registered users and 7 guests

Which top 10 players do you wish to see listed?

All-time

Active last two weeks

Active last month

Supremacy

Treaty

Official

ESOC Patch

Treaty Patch

1v1 Elo

2v2 Elo

3v3 Elo

Power Rating

Which streams do you wish to see listed?

Twitch

Age of Empires III

Age of Empires IV