There is a number N
If N is divided by 7 the remainder is 1, it can be shown as mod operator.
N%7=1
N%9=2
N%11=3
What is N?
the way to find the answer is the trail and error method. for that start with the 7 .check the 7+1 =8, 7*7+1=50, and 7*7*7+1=344. check the number 344 with 9 and 11 it gives the remainders 2 and 3 respectively. so 344 is the one of the required number . to calculate the remaining numbers the formula is lcm(7,9,11)*any real number + 344.
so the answer is the numbers 693*x+344. where x=0,1,2,……
Friday, February 25, 2011
BBoxes & N Dollers
“You have b boxes and n dollars. If I want any amount of money from 0 to n dollars, you must be able to hand me 0 to b boxes so that I get exactly what I request.” The two questions were “What are the restrictions on b and n, and how is money distributed among the boxes?”
The trick is of Binary Numbers
2^0=1
2^1=2
2^2=4
2^3=8
2^4=16
….
…
2^7=128
…
..
The formula is [log n to base 2] + 1 = b e.g b=logn+1 with base 2
where [] denote integral part of the log base 2 of n
Example
So if we want 0 to 15 dollars
[log of 15 to base 2] + 1 = [3.90] + 1 = 3 + 1 = 4 boxes
we need to have 4 boxes each having 1,2,4,8, dollars respectively.Now we know from binary numbers that any amount from 0 to 15 can be formed with this boxes.
For 0 to 6 dollars
[log of 7 to base 2] + 1 = [2.58] + 1 = 2 + 1 = 3 boxes
we need to have 3 boxes each having 1,2,4, dollars respectively
For 0 to 100 dollars
[log of 100 to base 2] + 1 = [6.64] + 1 = 6 + 1 = 7 boxes
we need to have 7 boxes each having 1,2,4,8,16,32,64 dollars respectively
Correct me if Anything wrong
The trick is of Binary Numbers
2^0=1
2^1=2
2^2=4
2^3=8
2^4=16
….
…
2^7=128
…
..
The formula is [log n to base 2] + 1 = b e.g b=logn+1 with base 2
where [] denote integral part of the log base 2 of n
Example
So if we want 0 to 15 dollars
[log of 15 to base 2] + 1 = [3.90] + 1 = 3 + 1 = 4 boxes
we need to have 4 boxes each having 1,2,4,8, dollars respectively.Now we know from binary numbers that any amount from 0 to 15 can be formed with this boxes.
For 0 to 6 dollars
[log of 7 to base 2] + 1 = [2.58] + 1 = 2 + 1 = 3 boxes
we need to have 3 boxes each having 1,2,4, dollars respectively
For 0 to 100 dollars
[log of 100 to base 2] + 1 = [6.64] + 1 = 6 + 1 = 7 boxes
we need to have 7 boxes each having 1,2,4,8,16,32,64 dollars respectively
Correct me if Anything wrong
Wednesday, February 16, 2011
Fairness in Carpooling
A group of n people decide to form a carpool. Each day a subset of these people will arrive to a (fixed) gathering point and one of them should drive. A method for determining which person should drive on any given day is required. The algorithm should be perceived as fair by all members so as to encourage their continued participation. Before discussing the scheduling algorithm, suggest a criterion for fairness
Comparing Information Without Leaking It
Bob comes to Ron, a manager at his company, with a complaint about a sensitive matter; he asks Ron to keep his identity confidential. A few months later, Moshe (another manager) tells Ron that someone has complained to him, also with a confidentiality request, about the same matter.
Ron and Moshe would like to determine whether the same person has complained to each of them, but, if there are two complainers, Ron and Moshe want to give no information to each other about their identities.
The protocol typically used in a situation like this one is akin to the game ``twenty questions,'' but goes by the name of ``delicate conversational probing.'' Ron might ask Moshe if Moshe's complainer is male, and if the answer is ``yes'' Moshe might then ask Ron if Ron's complainer's surname begins with a letter preceding ``M'' in the alphabet. This goes on until Ron and Moshe have ascertained whether they have the same person in mind. When they do not, however (particularly when the first ``no'' occurs late in the game) a great deal of information may have been exchanged.
What can Ron and Moshe do in order not leak more information than necessary?
Ron and Moshe would like to determine whether the same person has complained to each of them, but, if there are two complainers, Ron and Moshe want to give no information to each other about their identities.
The protocol typically used in a situation like this one is akin to the game ``twenty questions,'' but goes by the name of ``delicate conversational probing.'' Ron might ask Moshe if Moshe's complainer is male, and if the answer is ``yes'' Moshe might then ask Ron if Ron's complainer's surname begins with a letter preceding ``M'' in the alphabet. This goes on until Ron and Moshe have ascertained whether they have the same person in mind. When they do not, however (particularly when the first ``no'' occurs late in the game) a great deal of information may have been exchanged.
What can Ron and Moshe do in order not leak more information than necessary?
Nuts & Bolts
A disorganized carpenter has a mixed pile of bolts and nuts and would like to find the corresponding pairs of bolts and nuts. Each nut matches exactly one bolt (and vice versa). By trying to match a bolt and a nut the carpenter can see which one is bigger, but she cannot compare two bolts or two nuts directly. Can you help the carpenter match the nuts and bolts quickly?
The "media power" riddle or the importance of being well-connected
The riddle:
In each node of a simple unweighted n-node graph G there lives a citizen. Tomorrow morning, the citizens of G are about to vote "Yes/No" on a critical and highly controversial proposition whose details I could never really figure out.
Out of curiosity and boredom, each citizen of G spends the afternoon amusing himself by conducting a private poll among his neighbors (including himself), in order to get a sense of the outcome of this all-important election. The alarming and disappointing result found by each "Yes" voter is an astounding 3:1 majority for the "No" voters in his neighborhood.
Should the "Yes" voters be worried?! Should the "No" voters rejoice?! Can all these polls lie?? In short: What can be said with certainty about the minimum guaranteed number of "No" voters in tomorrow's election, given these poll results?
2nd variant:
The result of a 3:1 majority for the "No" voters in the neighborhood, was found by EACH and EVERY voter (not just the "Yes" voting ones).
What can be guaranteed now about the minimum number of "No" voters in the election?
3rd variant:
In order to strengthen the validity of the polls, each citizen performs his poll among all citizens in distance up to 4 from himself. Alas, the poll results remain the same.
What can be deduced now, in both previous cases?
In each node of a simple unweighted n-node graph G there lives a citizen. Tomorrow morning, the citizens of G are about to vote "Yes/No" on a critical and highly controversial proposition whose details I could never really figure out.
Out of curiosity and boredom, each citizen of G spends the afternoon amusing himself by conducting a private poll among his neighbors (including himself), in order to get a sense of the outcome of this all-important election. The alarming and disappointing result found by each "Yes" voter is an astounding 3:1 majority for the "No" voters in his neighborhood.
Should the "Yes" voters be worried?! Should the "No" voters rejoice?! Can all these polls lie?? In short: What can be said with certainty about the minimum guaranteed number of "No" voters in tomorrow's election, given these poll results?
2nd variant:
The result of a 3:1 majority for the "No" voters in the neighborhood, was found by EACH and EVERY voter (not just the "Yes" voting ones).
What can be guaranteed now about the minimum number of "No" voters in the election?
3rd variant:
In order to strengthen the validity of the polls, each citizen performs his poll among all citizens in distance up to 4 from himself. Alas, the poll results remain the same.
What can be deduced now, in both previous cases?
Applied Kid Cryptography
``Where's Waldo?'' is a puzzle book where each page contains a very detailed picture with many different characters (click here for ``Where's Waldo?'' on the WEB). The goal is to find Waldo, a predefined character . As the following true story will reveal, in these pictures also lies an interesting cryptographic problem.
Our story involves two characters; for the sake of anonymity and following a long cryptographic tradition we shall call them Alice and Bob. One day, while Alice and Bob were playing ``Where's Waldo?'', Alice suddenly claimed: ``I know where Waldo is!''. Bob responded with a baffling riddle: ``Alice, do you know what a liar is?''. Worried about her reputation (both as an honest person and as a qualified cryptographer), Alice wondered: ``How can I prove to Bob that I know where Waldo is without revealing his location?''
Can you help Alice and propose a simple solution that does not require complex computation and is low-tech in terms of the required resources?
Our story involves two characters; for the sake of anonymity and following a long cryptographic tradition we shall call them Alice and Bob. One day, while Alice and Bob were playing ``Where's Waldo?'', Alice suddenly claimed: ``I know where Waldo is!''. Bob responded with a baffling riddle: ``Alice, do you know what a liar is?''. Worried about her reputation (both as an honest person and as a qualified cryptographer), Alice wondered: ``How can I prove to Bob that I know where Waldo is without revealing his location?''
Can you help Alice and propose a simple solution that does not require complex computation and is low-tech in terms of the required resources?
Subscribe to:
Posts (Atom)