[Archive!] Pure mathematics, physics, chemistry, etc.: brain-training problems not related to trade in any way - page 369

New comment
 
Mathemat >>:

Конечно, можно - если противник тоже владеет оптимальной стратегией. И от того, кто ходит первым, тоже зависит, похоже.

I remember in the army one friend liked to fool people with this game, so he said the basic commandment - leaving the opponent two rows means losing! In other words, you have to lead your opponent to leave two rows, no matter how many matches there are in each row!
 

Yes, yes, two rows is the key point. But not just any two rows, but with the qualification:

- if you left him 1,1, you lost

- if you left him equal to n,n (n>1), he lost.

- if you left him any two unequal numbers, he wins.

The problem is how to make optimal moves to these two rows.

 
Yes! How to get to two rows and still be under the right conditions - there are many options! And after each opponent's move, calculate the options based on the specified

Mathemat's limitations! Well at least the intermediate variant is known to which one must strive!
 
drknn >>:

Ухххх, Парни, ТАКУЮ штуку сегодня поймал - закачаетесь :)))))))))

A bearded game. It's called "Nim". The strategy is that the number of matches on each 'floor' is converted into a binary number and then the parity-oddness for the individual columns of zeros and ones is counted.
 

I doubt the man was converting numbers to binary when he was drunk... Well, for small numbers, it's easy. What if he's already had three pints of beer on his chest?

 
Reshetov >>:
Бородатая игра. Называется "Ним". Стратегия заключается в том, что количество спичек на каждом "этаже" преобразуется в двоичное число, а потом считается четность-нечетность для отдельных колонок нулей и единиц.

Is there a solution?
 
On wikipedia https://ru.wikipedia.org/wiki/Ним_(game) there is a description of a winning strategy. To be honest, I still don't get the gist of it. It's kind of vaguely written.
 
drknn >>:
На википедии https://ru.wikipedia.org/wiki/Ним_(игра) есть описание выигрышной стратегии. Честоно говоря, я так и не понял, в чём суть. Как-то мутно написано.

It's very clear in there. Convert the number of matches into binary numbers, then perform bitwise operations on the numbers through modulo 2 logical addition - which is the full equivalent of calculating parity and odd. We get a strategy, i.e. the number we want to zero out. Take the "floor" in which the number of matches is greater than or equal to the number of strategies. If it is equal, then we draw all the matches of the floor.

If it is not equal, then we add the number of matches on the floor to the number-strategy using binary addition modulo 2. We get the result, i.e. how many matches should remain on the "floor" for the next player's move to be a sure loser. Take away the extra matches from the "floor".


Mathemat >>:

I doubt this guy was converting numbers to binary when he was drunk

...

Well, for small numbers, it's easy. What if he's already had three litres of beer on his chest?


Everything is much simpler. For such number of matches all winning combinations can be easily memorized and remembered even in drunkenness. As a student I did exactly that and beat my fellow students. That's why I say it's a bearded game.

 

Let's try to parse the example given on wikipedia.

Пример: предположим, в игре три кучки, в них соответственно 2 (0010 в бинарном представлении), 8 (1000) и 13 (1101) предметов. Ним-сумма этой позиции — 7 (0111).
Следовательно, выигрышная стратегия состоит в том, чтобы взять 3 предмета из третьей кучки — там останется 10 (1010) предметов, и ним-сумма позиции станет 0 (0000).
Предположим, после вашего хода противник забирает все предметы из первой кучки — выигрышная стратегия будет заключаться в том, чтобы забрать 2 предмета из третьей
кучки. В таком случае после вашего хода в кучках будет соответственно 0 (0000), 8 (1000) и 8 (1000) предметов, ним-сумма по прежнему будет равняться 0.

Add up the numbers:

0010+1000+1101 = 0111 if we do not take into account the transfer of units to higher digits. Agreed. Once the nim-sum has been calculated, the author states that it is necessary to take three items from the third pile. That's what I don't understand. Why did he take that it's necessary to take only three items, and why from the third pile? Because in order for the sum to be 0 you have to subtract 0111, i.e. subtract seven from the number 0111.

 
drknn >>:

Попробуем разобрать пример, который приведён на википедии.

Складываем числа:

0010+1000+1101 = 0111 если не учитывать перенос единиц в старший разряд. Согласен. Как только ним-сумма была вичислена, автор утверждает, что нужно взять три предмета из третьей кучки. Вот этого-то я и не понял. С чего он взял что брать нужно только три предмета и почему именно из третьей кучки? Ведь для того, чтоб ним-сумма стала равна 0 нужно из числа 0111 вычесть 0111, то есть, вычесть семь.

0010

1000

1101

-----

0111 is the result, i.e. the first column has an even number of matches and the rest have an odd number of matches.


third floor 1101 = 13

Add up the number of third floor piles with the result:

1101

0111

----

1010 = 10


13 - 10 = 3, i.e. it is necessary to take away 3 matches from the third floor, and then there will remain 10 matches, that in binary system = 1010


We check what is left:

0010

1000

1010

-----

0000 is the winning strategy

1...362363364365366367368369370371372373374375376...628
New comment