Can you get full marks?

For students of class 6-8 (age 12 to 14)
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
Can you get full marks?

Unread post by Anindya Biswas » Sat Dec 12, 2020 9:38 pm

Ms. Watson is our new professor on mathematics. She is going to take an exam. The exam will contain $n$ problems and each problems have different positive integer marks. You can either get full marks on a problem or $0$ marks. She distributed the marks in such a way that from the total score of a student, we can figure out not only how much that student scored, but also exactly which problems that student correctly solved. What is the minimum possible full score of that exam?
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Can you get full marks?

Unread post by Mehrab4226 » Sat Dec 26, 2020 7:28 pm

I first thought that this was an NT problem. But later it became a Combi problem.
Solution:
--------------------------------------Begin--------------------------------------
We claim that the minimum highest mark possible is $2^n-1$
It is easy to understand why it works. We give the $n$ problems the marks $2^0,2^1,\cdots 2^{n-1}$
This works. See conversion to binary from decimal to get why. There is also a popular riddle about it. I hope that I don't have to prove why this works.

Now the proof that no other smaller integer can the minimum highest marks:

Let, There is an integer $k$ such that $k<2^n-1$ and the marks for the problems are $a_1,a_2,a_3 \cdots a_n$

To hold the special property of Ms.Watson(probably not the wife of John Watson) sum of elements of each subset of the set $\{a_1,a_2, \cdots a_n\}$ should have a different value. And we know that there are $2^n $ number of subsets of that set. So there must be 2^n non-negative integers $\leq k$. But if $k<2^n-1$ then it is not possible. A contradiction!!
Thus the minimum highest mark possible is $2^n-1$
-------------------------------------End----------------------------------------
Some parts of the solution may be hard to understand. Because I am a very bad solution writer. If there are some parts somebody didn't understand, please feel free to point them out and I will try to do what I can to make it more understandable. Thank you.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Can you get full marks?

Unread post by Anindya Biswas » Sat Dec 26, 2020 8:56 pm

Mehrab4226 wrote:
Sat Dec 26, 2020 7:28 pm
I first thought that this was an NT problem. But later it became a Combi problem.
Solution:
--------------------------------------Begin--------------------------------------
We claim that the minimum highest mark possible is $2^n-1$
It is easy to understand why it works. We give the $n$ problems the marks $2^0,2^1,\cdots 2^{n-1}$
This works. See conversion to binary from decimal to get why. There is also a popular riddle about it. I hope that I don't have to prove why this works.

Now the proof that no other smaller integer can the minimum highest marks:

Let, There is an integer $k$ such that $k<2^n-1$ and the marks for the problems are $a_1,a_2,a_3 \cdots a_n$

To hold the special property of Ms.Watson(probably not the wife of John Watson) sum of elements of each subset of the set $\{a_1,a_2, \cdots a_n\}$ should have a different value. And we know that there are $2^n $ number of subsets of that set. So there must be 2^n non-negative integers $\leq k$. But if $k<2^n-1$ then it is not possible. A contradiction!!
Thus the minimum highest mark possible is $2^n-1$
-------------------------------------End----------------------------------------
Some parts of the solution may be hard to understand. Because I am a very bad solution writer. If there are some parts somebody didn't understand, please feel free to point them out and I will try to do what I can to make it more understandable. Thank you.
Exactly, I was particularly interested in the second part where you proved that we can't do better than $2^n-1$, the first part that we can achieve this minimum is pretty obvious.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Can you get full marks?

Unread post by Asif Hossain » Thu Apr 01, 2021 6:53 pm

Mehrab4226 wrote:
Sat Dec 26, 2020 7:28 pm
I first thought that this was an NT problem. But later it became a Combi problem.
Solution:
--------------------------------------Begin--------------------------------------
We claim that the minimum highest mark possible is $2^n-1$
It is easy to understand why it works. We give the $n$ problems the marks $2^0,2^1,\cdots 2^{n-1}$
This works. See conversion to binary from decimal to get why. There is also a popular riddle about it. I hope that I don't have to prove why this works.

Now the proof that no other smaller integer can the minimum highest marks:

Let, There is an integer $k$ such that $k<2^n-1$ and the marks for the problems are $a_1,a_2,a_3 \cdots a_n$

To hold the special property of Ms.Watson(probably not the wife of John Watson) sum of elements of each subset of the set $\{a_1,a_2, \cdots a_n\}$ should have a different value. And we know that there are $2^n $ number of subsets of that set. So there must be 2^n non-negative integers $\leq k$. But if $k<2^n-1$ then it is not possible. A contradiction!!
Thus the minimum highest mark possible is $2^n-1$
-------------------------------------End----------------------------------------
Some parts of the solution may be hard to understand. Because I am a very bad solution writer. If there are some parts somebody didn't understand, please feel free to point them out and I will try to do what I can to make it more understandable. Thank you.
ok couldn't resist asking why giving the weight $2^k$ was helpful? (most of the problems in combii is solved by giving variables weight either $2^k$ or $\frac{1}{2^k}$ why is that)
Hmm..Hammer...Treat everything as nail

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Can you get full marks?

Unread post by Anindya Biswas » Thu Apr 01, 2021 7:18 pm

Asif Hossain wrote:
Thu Apr 01, 2021 6:53 pm
Mehrab4226 wrote:
Sat Dec 26, 2020 7:28 pm
I first thought that this was an NT problem. But later it became a Combi problem.
Solution:
--------------------------------------Begin--------------------------------------
We claim that the minimum highest mark possible is $2^n-1$
It is easy to understand why it works. We give the $n$ problems the marks $2^0,2^1,\cdots 2^{n-1}$
This works. See conversion to binary from decimal to get why. There is also a popular riddle about it. I hope that I don't have to prove why this works.

Now the proof that no other smaller integer can the minimum highest marks:

Let, There is an integer $k$ such that $k<2^n-1$ and the marks for the problems are $a_1,a_2,a_3 \cdots a_n$

To hold the special property of Ms.Watson(probably not the wife of John Watson) sum of elements of each subset of the set $\{a_1,a_2, \cdots a_n\}$ should have a different value. And we know that there are $2^n $ number of subsets of that set. So there must be 2^n non-negative integers $\leq k$. But if $k<2^n-1$ then it is not possible. A contradiction!!
Thus the minimum highest mark possible is $2^n-1$
-------------------------------------End----------------------------------------
Some parts of the solution may be hard to understand. Because I am a very bad solution writer. If there are some parts somebody didn't understand, please feel free to point them out and I will try to do what I can to make it more understandable. Thank you.
ok couldn't resist asking why giving the weight $2^k$ was helpful? (most of the problems in combii is solved by giving variables weight either $2^k$ or $\frac{1}{2^k}$ why is that)
Maybe the property Mehrab proved about $2^k$ is one of the reasons $2^k$ is important.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Can you get full marks?

Unread post by Asif Hossain » Thu Apr 01, 2021 8:27 pm

BUT WHY EVEN WEIGHTS ARE IMPORTANT CAN'T WE PROVE WITHOUT GIVING WEIGHTS? MEANS WHAT IS THE MOTIVE OF GIVING WEIGHT TO SOME VARIABLES??
Hmm..Hammer...Treat everything as nail

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Can you get full marks?

Unread post by Mehrab4226 » Thu Apr 01, 2021 8:37 pm

Asif Hossain wrote:
Thu Apr 01, 2021 6:53 pm
Mehrab4226 wrote:
Sat Dec 26, 2020 7:28 pm
I first thought that this was an NT problem. But later it became a Combi problem.
Solution:
--------------------------------------Begin--------------------------------------
We claim that the minimum highest mark possible is $2^n-1$
It is easy to understand why it works. We give the $n$ problems the marks $2^0,2^1,\cdots 2^{n-1}$
This works. See conversion to binary from decimal to get why. There is also a popular riddle about it. I hope that I don't have to prove why this works.

Now the proof that no other smaller integer can the minimum highest marks:

Let, There is an integer $k$ such that $k<2^n-1$ and the marks for the problems are $a_1,a_2,a_3 \cdots a_n$

To hold the special property of Ms.Watson(probably not the wife of John Watson) sum of elements of each subset of the set $\{a_1,a_2, \cdots a_n\}$ should have a different value. And we know that there are $2^n $ number of subsets of that set. So there must be 2^n non-negative integers $\leq k$. But if $k<2^n-1$ then it is not possible. A contradiction!!
Thus the minimum highest mark possible is $2^n-1$
-------------------------------------End----------------------------------------
Some parts of the solution may be hard to understand. Because I am a very bad solution writer. If there are some parts somebody didn't understand, please feel free to point them out and I will try to do what I can to make it more understandable. Thank you.
ok couldn't resist asking why giving the weight $2^k$ was helpful? (most of the problems in combii is solved by giving variables weight either $2^k$ or $\frac{1}{2^k}$ why is that)
There was a riddle my school friend gave me, which states,"You have 64 coins each valued 1tk. Now you put the 64 coins in 7 bags in such a way that If you want to buy something then you can just give one or more bags, you don't need to take any coins from other bags. How did you arrange those coins."
And this riddle is kinda the same of what the question said, so I thought maybe this is the most efficient way of doing this. And I went ahead to prove it and succeeded. And yes $2^k$ has this special property.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Can you get full marks?

Unread post by Mehrab4226 » Thu Apr 01, 2021 8:50 pm

Asif Hossain wrote:
Thu Apr 01, 2021 8:27 pm
BUT WHY EVEN WEIGHTS ARE IMPORTANT CAN'T WE PROVE WITHOUT GIVING WEIGHTS? MEANS WHAT IS THE MOTIVE OF GIVING WEIGHT TO SOME VARIABLES??
Actually what happened here is that I already had gotten a conjecture. And so I went ahead and tried to prove it where I succeeded. In many problems when we already know a solution, we just need to prove that this is the solution. Which is kinda easier in this problem. I'll give you an example,
Let, you are really new to math, but you do know some tricks like induction, contradiction, etc. But only proving tools, no fancy math stuff. And yeah you know basic arithmetic too.
I give 2 questions,
1st,
Find, $1+2+3+\cdots +n=?$
You are gonna first try a few values, and experiment, and try to solve the problem from the ground up. In the end, probably you will use the gaussian pairing tool, and get the sum, but what if you tackled the 2nd question,
2nd,
Prove, $1+2+3+\cdots +n=\frac{n(n+1)}{2}$,
You will just try induction and get the solution quickly. This is kinda the exact thing that happened to me in the problem. There might be a solution where you do not need to use $2^k$, but that is a for another day.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: Can you get full marks?

Unread post by Asif Hossain » Thu Apr 01, 2021 10:30 pm

Mehrab4226 wrote:
Thu Apr 01, 2021 8:37 pm
Asif Hossain wrote:
Thu Apr 01, 2021 6:53 pm
Mehrab4226 wrote:
Sat Dec 26, 2020 7:28 pm
I first thought that this was an NT problem. But later it became a Combi problem.
Solution:
--------------------------------------Begin--------------------------------------
We claim that the minimum highest mark possible is $2^n-1$
It is easy to understand why it works. We give the $n$ problems the marks $2^0,2^1,\cdots 2^{n-1}$
This works. See conversion to binary from decimal to get why. There is also a popular riddle about it. I hope that I don't have to prove why this works.

Now the proof that no other smaller integer can the minimum highest marks:

Let, There is an integer $k$ such that $k<2^n-1$ and the marks for the problems are $a_1,a_2,a_3 \cdots a_n$

To hold the special property of Ms.Watson(probably not the wife of John Watson) sum of elements of each subset of the set $\{a_1,a_2, \cdots a_n\}$ should have a different value. And we know that there are $2^n $ number of subsets of that set. So there must be 2^n non-negative integers $\leq k$. But if $k<2^n-1$ then it is not possible. A contradiction!!
Thus the minimum highest mark possible is $2^n-1$
-------------------------------------End----------------------------------------
Some parts of the solution may be hard to understand. Because I am a very bad solution writer. If there are some parts somebody didn't understand, please feel free to point them out and I will try to do what I can to make it more understandable. Thank you.
ok couldn't resist asking why giving the weight $2^k$ was helpful? (most of the problems in combii is solved by giving variables weight either $2^k$ or $\frac{1}{2^k}$ why is that)
There was a riddle my school friend gave me, which states,"You have 64 coins each valued 1tk. Now you put the 64 coins in 7 bags in such a way that If you want to buy something then you can just give one or more bags, you don't need to take any coins from other bags. How did you arrange those coins."
And this riddle is kinda the same of what the question said, so I thought maybe this is the most efficient way of doing this. And I went ahead to prove it and succeeded. And yes $2^k$ has this special property.
Actually i saw another problem of Newzealend MO which had to do something with cookies distribution pranav in his book just created a monovariant out of thin air giving cookies weight of $\frac{1}{2^i}$ i was left thinking how did it came up to his mind of even weighting the cookies let alone $\frac{1}{2^i}$ any help??(you can find the prob in pranav's combii book)
Hmm..Hammer...Treat everything as nail

Post Reply